Aus ProgrammingWiki

Inhaltsverzeichnis 1 TM-Codierung 1.1 Aufgabe 1.1.1 Grammatik: 1.2 Lösung

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:

Folgende TM soll aus der Codierung entstehen:

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