BuK/IIm10/BuK-Kreativaufgabe06 G1
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
=TM-Codierung=
==Aufgabe==
Verwenden Sie kfG Edit aus AtoCC, um die folgende kontextfreie Grammatik G für die Sprache der TM-Codierungen zu definieren. G = (N, T, P, s)
===Grammatik:===
N = {T Mcodierung, Endzustaende, Delta, Uebergang, Kopfbewegung,
L, R, N, Zeichen, Null, Eins, B, Zustand, Einsenfolge}
T = {0, 1}
P = {T Mcodierung → Delta Trenner Endzustaende
Endzustaende → Zustand 0 Endzustaende | Zustand
Delta → Uebergang 0 Delta | Uebergang
Uebergang → Zustand 0 Zeichen 0 Zustand 0 Zeichen 0 Kopfbewegung
Kopfbewegung → N | R | L
L → 1
R → 1 1
N → 1 1 1
Zeichen → B | Eins | Null
Null → 1
Eins → 1 1
B → 1 1 1
Zustand → Einsenfolge
Einsenfolge → 1 | 1 Einsenfolge
}
s = T Mcodierung
Die TM ist folgender Maßen codiert:
[[Bild:Simaschi_Codierung.PNG]]
Folgende TM soll aus der Codierung entstehen:
[[Bild:Simaschi_Automat_m-compiler.PNG]]
Als nächstes soll ein Compiler entwickelt werden, der ein syntaktisch korrektes Wort aus L(G), also eine korrekte TM-Codierung, in eine TM in der AtoCC-Repräsentation übersetzt. Beginnen Sie mit der Generierung eines LALR(1)-Parsers für G.
==Lösung==
Einen Compiler, der mit AtoCC entwickelt wurde finden Sie hier:
http://michael-hielscher.de/compilerwiki/index.php/Compiler_37822_1_Demo
Einen Compiler, der von Hand programmiert wurde finden Sie hier:
<code>
public class Main {
/**
* @param args
* @throws IOException
*/
static String text="";
static String zustand;
static String zielzustand;
static String read;
static String richtung;
static String write;
static String mitteltext;
static String finalstate1="false";
static String finalstate2="false";
static String finalstate3="false";
static String finalstate4="false";
static String finalstateend;
static String eingang3_ziel="";
static String text5="";
static Boolean gram;
public static void main(String[] args) throws java.io.IOException {
// TODO Auto-generated method stub
mitteltext="";
java.io.FileReader fr = new java.io.FileReader("C:/Users/Snookerms/Desktop/Ablage/input.txt");
java.io.BufferedReader br = new java.io.BufferedReader(fr);
String zeile1 = br.readLine();
System.out.println(zeile1);
br.close();
if(zeile1.startsWith("000")&zeile1.endsWith("000")){
String bestandteile = zeile1.substring(4, zeile1.length()-3);
String [] delta = bestandteile.split("00");
for(int y=0; y<delta.length;y++){
if(delta[y].replaceAll("1", "").length()==4|delta[y].replaceAll("1", "").length()==0){
gram=true;
}
}
}
String eingang = zeile1.substring(3, zeile1.length()-3);
System.out.println(eingang);
String []eingang2 = eingang.split("00");
for(int i=0; i<eingang2.length;i++){
System.out.println(eingang2[i]);
}
int z = eingang2.length;
for (int t=0; t<eingang2.length;t++){
java.util.Pattern p = java.util.Pattern.compile("[0]");
java.io.Matcher m = p.matcher(eingang2[t]);
boolean b = m.matches();
if(b == true){
} else{
if(eingang2[t].equals("1")){
finalstate1="true";
}
if(eingang2[t].equals("11")){
finalstate2="true";
}
if(eingang2[t].equals("111")){
finalstate3="true";
}
if(eingang2[t].equals("1111")){
finalstate4="true";
}
}
}
String text0 = "<?xml version=\"1.0\" encoding=\"utf-8\"?><AUTOMATON><TYPE value=\"TM\"/><ALPHABET><ITEM value=\"0\"/><ITEM value=\"1\"/></ALPHABET><TAPEALPHABET><ITEM value=\"$\"/><ITEM value=\"0\"/><ITEM value=\"1\"/></TAPEALPHABET>";
for(int u=0; u<z-2;u++){
String [] eingang3 = eingang2[u].split("0");
if(eingang3[0].equals("1")){
zustand = "q_0";
if(eingang3_ziel.equals(zustand)){
text="";
}
else{
if(finalstate1.equals("true")){
finalstate1="true";
}
eingang3_ziel="q_0";
text = "<STATE name=\""+ zustand + "\" finalstate=\""+ finalstate1 +"\">";
}
}
if(eingang3[0].equals("11")){
zustand = "q_1";
if(eingang3_ziel.equals(zustand)){
text="";
}
else{
if(finalstate2.equals("true")){
finalstate2="true";
}
eingang3_ziel="q_1";
text = "</STATE><STATE name=\""+ zustand + "\" finalstate=\""+ finalstate2 +"\">";
}
}
if(eingang3[0].equals("111")){
zustand = "q_2";
if(eingang3_ziel.equals(zustand)){
text="";
}
else{
if(finalstate3.equals("true")){
finalstate3="true";
}
eingang3_ziel="q_2";
text = "</STATE><STATE name=\""+ zustand + "\" finalstate=\""+ finalstate3 +"\">";
}
}
if(eingang3[0].equals("1111")){
zustand = "q_3";
if(eingang3_ziel.equals(zustand)){
text="";
}
else{
if(finalstate4.equals("true")){
finalstate4="true";
}
eingang3_ziel="q_3";
text = "</STATE><STATE name=\""+ zustand + "\" finalstate=\""+ finalstate4 +"\">";
}
}
if(eingang3[1].equals("1")){
read = "0";
}
if(eingang3[1].equals("11")){
read = "1";
}
if(eingang3[3].equals("11")){
write = "1";
}
if(eingang3[3].equals("1")){
write = "0";
}
if(eingang3[4].equals("1")){
richtung = "LEFT";
}
if(eingang3[4].equals("11")){
richtung = "RIGHT";
}
String text3 = "<LABEL read=\""+ read +"\" direction=\""+ richtung +"\" write=\""+ write +"\"/></TRANSITION>";
if(eingang3[2].equals("1")){
zielzustand = "q_0";
}
if(eingang3[2].equals("11")){
zielzustand = "q_1";
}
if(eingang3[2].equals("111")){
zielzustand = "q_2";
}
if(eingang3[2].equals("1111")){
zielzustand = "q_3";
}
String text2 = "<TRANSITION target=\""+ zielzustand +"\">";
mitteltext=mitteltext+text+text2+text3+text5;
}
String text4 = "</STATE><INITIALSTATE value=\"q_0\"/><TAPEINITIALCHAR value=\"$\"/></AUTOMATON>";
String endtext = text0+mitteltext+text4;
if(gram=true){
System.out.println("Eingabe entspricht der Grammatik!");
String dateiName = "C:/Users/Snookerms/Desktop/Ablage/ergebnis.xml";
java.io.FileOutputStream schreibeStrom =
new java.io.FileOutputStream(dateiName);
for (int i=0; i < endtext.length(); i++){
schreibeStrom.write((byte)endtext.charAt(i));
}
schreibeStrom.close();
}
else{
System.out.println("Eingabe entspricht nicht der Grammatik!");
}
}
}
</code>
Dabei ist zu beachten, dass der handgeschrieben Compiler nur bis zu maximal 4 Zuständen geht und folgende Codierung verwendet:
<run>
000101101101101100110101010100110110110110110011101101011010010011000</run>