TM-Compiler für die GOTO virtual machine
In Kapitel 14 werden verschiedene Programmiersprachen konstruiert um herauszufinden, welche Eigenschaften einer Programmiersprache zu Turing-Vollständigkeit führen. Für die Sprache GOTO wird ein Turing-Maschinencompiler beschrieben, der Turing-Maschinenbeschreibungen in GOTO-Programme übersetzen kann. Der Compiler ist mit den Werkzeugen flex(1) und bison(1) realisiert, welche in den Kapiteln 4 und 7 besprochen werden und auch im Calculator-Projekt illustriert werden.
Ganzes Paket: gvm-1.1.tar.gz herunterladen. Instruktionen zur Kompilation finden sich im README file im Paket.
- Der Turing-Maschine-Compiler
- tmc.h: Definition der Datenstrukturen für die interne Darstellung der Turing-Maschine.
- tmc.c: main() Funktion für den Compiler und einige Hilfsfunktionen, die im Parser oder Scanner gebraucht werden.
- tmc-tokens.l: Mit flex(1) erzeugter Scanner, der die Turing-Maschinenbeschreibung in einzelne Tokens zerlegt, die der Parser interpretieren kann.
- tmc-grammar.y: Mit bison(1) erzeuger Parser, der jede einzelne Turing-Maschinenregel in einen Eintrag in einer Tabelle verwandelt. Bei der Erzeugung des Codes durch die Funktion tmc_compile wird jeder Knoten der Tabelle in ein Fragement von GOTO-Code verwandelt, wie dies in Abschnitt 14.4.4 beschrieben wird.
- tokens.l: Mit flex(1) erzeuger Scanner für GOTO-Programme.
- grammar.y: Mit bison(1) erzeuger Parser für GOTO-Programme. Der Parser verwandelt die Zeilen des GOTO-Programms in eine interne Darstellung, die für die Ausführung durch die Funktion gvm_run() in utils.c verwendet wird.
- gvm.h: Definition der Datenstrukturen für die interne Darstellung des GOTO-Programms.
- gvm.c: main() Funktion für die virtuelle Maschine.
- utils.c: Implementation der virtuellen Maschine. Die Funktion gvm_run() interpretiert die einzelnen Einträge in der internen Darstellung und führt die dort codierte Anweisung aus.
- utils.h: Deklaration der in utils.c implementierten Funktionen.