IIm18-Kreativaufgabe5

Wiki-Quelltext dieser Seite.

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.

<popup name="Umsetzung">
    ''1.'' mit AToCC: Definition der Grammatik aus der Aufgabenstellung.
    [[Bild:S3fagawa_Definition_kfgEdit.png]]
    ''2.'' mit FLACI: Definition der Grammatik.
    Die Definition in FLACI erfolgte analog.
</popup>

==Teilaufgabe 2==
Definition der Übergangsfunktion der Turingmaschine M.

<popup name="Umsetzung">
    Die Definition der TM wurde mittels AutoEDIT von AtoCC vorgenommen.
    [[Bild:S3fagawa_Definition_M.png]]
</popup>

==Teilaufgabe 3==
Codierung von M per Hand und Verifizierung von <M> und Variationen von <M>.

<popup name="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    
</popup>


<popup name="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.
    [[Bild:S3fagawa_Ableitung_m.png]]
    ''2'' Bei der Verifizierung mittels FLACI wurde die <M> richtig abgeleitet.
    [[Bild:S3fagawa_Ableitungsbaum_von_M.png]]
    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.
</popup>


<popup name="Ableitungsbäume von Variationen von der Codierung von M">
    ''0'' <M>:10110110110111011101011101101011011011101101110110111011010100110111 ohne Abänderungen

    ''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.
</popup>

==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.

<popup name="Erstellung des LALR(1)-Parser">
    Der Scanner und der Parser wurden mittels FLACI erstellt. Im folgenden Bild ist die Definition des Scanners zu sehen.
    [[Bild:S3fagawa_BUK_SCANNER.png]]   

    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.
    [[Bild:S3fagawa_BUK_PARSER.png]]

    <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>



<popup name="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
</popup>