IIm18-Kreativaufgabe5
Aus ProgrammingWiki
Inhaltsverzeichnis |
Die Kreativ Aufgabe 5 befasst sich mit der der Codierung dem Parsen und Übersetzen von UTM´s.
Teilaufgabe 1
Definition der kfG mittels der TI-Werkzeuge Atocc oder FLACI.
Umsetzung
1. mit AToCC: Definition der Grammatik aus der Aufgabenstellung.
2. mit FLACI: Definition der Grammatik.
Die Definition in FLACI erfolgte analog.
Teilaufgabe 2
Definition der Übergangsfunktion der Turingmaschine M.
Umsetzung
Die Definition der TM wurde mittels AutoEDIT von AtoCC vorgenommen.
Teilaufgabe 3
Codierung von M per Hand und Verifizierung von <m> und Variationen von <m>.</m></m>
Umsetzung der Codierung
Mittels der Grammatik und der vorgegebenen Kodierungsregeln der Aufgabenbeschreibung, wurde die Automatendefinition aus Aufgabe 2 in eine Folge von Einsen und Nullen übersetzt.
Übergang 1 Ü-Trenner 1 0 11 0 11 0 11 0 11 0 Übergang 2 Ü-Trenner 11 0 1 0 1 0 1 0 1 0 Übergang 3 Ü-Trenner 11 0 11 0111 0 11 0 11 0 Übergang 4 111 0 11 0 1 0 11 0 1 Trenner-Übergänge 00 Endzustand 1 E-Trenner Endzustand 2 1 0 11
<m>: 10110110110111011101011101101011011011101101110110111011010100110111 </m>
Verifizierung der Codierung
1 Bei der Verifizierung mittels kfgEdit muss <m> vollständig aufgebaut werden können. Hierbei tritt jedoch bei kfgEdit ein Fehler auf, dieser sagt, dass die eingegebene Satzform nicht ableitbar ist.<em>2</em> Bei der Verifizierung mittels FLACI wurde die <m> richtig abgeleitet.
Auf der Abbildung ist nicht der vollständige Ableitungsbaum zu sehen dieser kann aber mittels der Definition aus Teilaufgabe 1 und <m> aus Teilaufgabe 2 von FLACI generiert werden. Aufgrund der Tatsache, dass AtoCC den Ableitungsbaum nicht erstellen kann wurde der Rest der Kreativaufgabe mit FLACI fortgesetzt.</m></m></m>
Ableitungsbäume von Variationen von der Codierung von M
0 <m>:10110110110111011101011101101011011011101101110110111011010100110111 ohne Abänderungen</m>
1 Variation:110101011101101101101101101011011011101101110110111011010100111011 Dies ist eine zulässige Variation, die ohne Weiteres von FLACI abgeleitet werden kann.
2 Variation:1101001001110011011001101101101011011011101101110110111011010100111011 Diese Variatiion konnte nicht abgeleitet werden da es hier zu eine Verletzung der Regeln von Grammatik kommt.
3 Variation:1110110101101001 Die folgende TM-Codierung enthält nur einen Übergang ist jedoch richtig definiert und kann mittels FLACI abgeleitet werden.
Teilaufgabe 4
Entwicklung eines Compiler der syntaktisch Korrekte Codierung von M in AtoCC(FLACI) Representation übersetzt. Als Parser soll ein LALR(1)-Parser für G entwickelt werden.
Erstellung des LALR(1)-Parser
Der Scanner und der Parser wurden mittels FLACI erstellt. Im folgenden Bild ist die Definition des Scanners zu sehen.
Im nächsten Schritt werden die Regeln für den Parser definiert. Hierzu kann man die Tokens und die Regeln nutzen. Aus der Aufgabenstellung geht hervor das ein LALR(1)-Parser erstellt werden soll.
Ein Auszug der definierten Regeln ist im folgenden zu sehen.
<popup name="Exkurs LALR(1)-Parser"> Ein LALR(1)-Parser liest das zu analysierende Wort von links ein und das zu parsende Wort wird von rechts erweitert. Um Konflikte zu vermeiden welche Regel genutzt werden kann, für den Fall das mehrere zutreffend sind, wird genau ein weiteres Zeichen gelesen und die passende Regel ermittelt. </popup>
Konstruktion des Compilers
In der Aufgabenstellung wird zwar explizit die AtoCC-Repräsentation erwähnt doch AtoCC erwies sich beim bearbeiten der Aufgabe als unpraktischer und fehleranfälliger, sodass FLACI genutzt wurde.
JSON-Beispiel einer FLACI-Representation
"name": "",
"description": "",
"type": "TM",
"automaton": {
"simulationInput": [],
"Alphabet": [
"0",
"1"
],
"StackAlphabet": [
"0",
"1"
],
"States": [
{
"ID": 1,
"Name": "q0",
"x": 200,
"y": 200,
"Final": true,
"Radius": 30,
"Transitions": [],
"Start": true
}
]
},
"GUID": "j53k7nz7"Analyse des JSON-File: o die ersten drei Informationen sind Meta-Informationen o dann werden die Eingaben für die Simulation, das Eingabealphabet und das Bandalphabet definiert o dann folgt ein Struktur von Zuständen, welche die Übergänge enthält