Computer Science
System Software
Cover
Hanspeter Mössenböck
Compilerbau
Grundlagen und Anwendungen
dpunkt.verlag, 2024
ISBN 978-3-98889-008-5

Das Buch behandelt die praxisrelevanten Grundlagen des Compilerbaus, von der lexikalischen Analyse, über die Syntaxanalyse bis zur Semantikverarbeitung und zur Codeerzeugung. Weitere Themen sind die Beschreibung von Übersetzungsprozessen durch attributierte Grammatiken sowie der Einsatz des Compilergenerators Coco/R zur automatischen Generierung der Kernteile eines Compilers. Als durchgängiges Beispiel wird ein Compiler für MicroJava – eine einfache Java-ähnliche Programmiersprache – entwickelt, der ausführbaren Bytecode – ähnlich dem Java-Bytecode – erzeugt.

Vorlesungsfolien

Das Buch entstand aus einer Compilerbau-Vorlesung, die der Autor seit vielen Jahren an der Johannes Kepler Universität Linz sowie an der Oxford Brookes University in England hält. Es kann als begleitende Unterlage zu einer einführenden Compilerbau-Vorlesung oder zum Selbststudium verwendet werden. Als Ergänzung zum Buch finden Sie hier die Vorlesungsfolien im Powerpoint-Format (unter der Creative Commons Lizenz CC BY-NC-SA 4.0).

  1. Überblick
  2. Scanning
  3. Parsing
  4. Semantikanschluss und Attributierte Grammatiken
  5. Symbolliste
  6. Codeerzeugung
  7. Der Compilergenerator Coco/R
  8. Exkurs: Bottom-up-Syntaxanalyse

Für den Fall, dass Sie die Folien nicht im Powerpoint-Format öffnen können, weil Sie auf Ihrem Computer weder MS Office noch ein anderes kompatibles Programm (z.B. OpenOffice, LibreOffice, Keynote) installiert haben, finden Sie hier die entsprechenden PDF-Dateien der Folien.

Der MicroJava-Compiler

Als durchgängiges Beispiel wird in diesem Buch die Implementierung eines Compilers für MicroJava beschrieben. MicroJava ist eine einfache Java-ähnliche Programmiersprache, aus der Bytecode (ähnlich zum Java-Bytecode) erzeugt wird. Der Quellcode des Microjava-Compilers sowie der MicroJava-VM kann von hier heruntergeladen werden.

  • Download: Laden Sie die Datei Compiler.zip herunter, expandieren Sie sie, wechseln Sie ins Verzeichnis Compiler und führen Sie dort die Batch-Datei build.bat aus, die den MicroJava-Compiler übersetzt.
  • Compilation: Um ein MicroJava-Programm zu compilieren, führen Sie im Verzeichnis Compiler die Batch-Datei MJ.bat aus (z.B. MJ Eratos.mj). Der Compiler erzeugt eine Objektdatei (z.B. Eratos.obj) und gibt den erzeugten Bytecode zur Kontrolle auf der Konsole aus. Eratos ist ein Beispielprogramm, das die Primzahlen bis zu einer gewissen Obergrenze berechnet und ausgibt.
  • Ausführung: Um das compilierte MicroJava-Programm auszuführen, führen Sie im Verzeichnis Compiler die Batch-Datei run.bat aus (z.B. run Eratos.obj [-debug]). Nach Starten von Eratos geben Sie die Obergrenze als Zahl ein (z.B. 100 Return). Durch Aktivieren der debug-Option werden die interpretierten Bytecode-Befehle samt Zustand des Expression Stacks auf der Konsole ausgegeben.
  • Decodierung: Um ein compiliertes MicroJava-Programm zu decodieren, führen Sie im Verzeichnis Compiler den Befehl java MJ.Decode fileName.obj aus. Die decodierten Bytecode-Instruktionen werden auf der Konsole ausgegeben.
  • MicroJava VM: Wer die MicroJava-VM samt dem Bytecode-Interpreter im Quellcode studieren will, kann sich die Datei MJ/CodeGen/Run.java ansehen.

Der Compilergenerator Coco/R

Im Buch wird der Compilergenerator Coco/R beschrieben, mit dem ein Scanner und ein Parser eines Compilers (oder eines Compiler-ähnlichen Werkzeugs) aus einer kompakten Compilerbeschreibung generiert werden kann. Coco/R akzeptiert LL(*)-Grammatiken und erzeugt Parser im rekursiven Abstieg. Es gibt Versionen für Java, C#, C++ und viele andere Sprachen. Coco/R ist Open Source und kann samt Benutzerhandbuch von https://ssw.jku.at/coco/ heruntergeladen werden.

Für die Java-Version von Coco/R reicht es, die Dateien Coco.jar, Scanner.frame und Parser.frame herunterzuladen und in das gleiche Verzeichnis zu geben wie die mit Coco/R zu übersetzende Compilerbeschreibung (*.atg).

Downloads zu einzelnen Kapiteln des Buchs

  • Kapitel 2: Lexikalische Analyse, Übungsaufgabe 11
    Laden Sie die Datei TestScanner.zip herunter und expandieren Sie sie. Geben Sie ihre Dateien Scanner.java und Token.java ins Verzeichnis Compiler/MJ/, gehen Sie ins Verzeichnis Compiler und führen Sie runTestScanner.bat aus.
  • Kapitel 3: Syntaxanalyse, Übungsaufgabe 12
    Laden Sie die Datei TestParser.zip herunter und expandieren Sie sie. Geben Sie ihre Dateien Scanner.java, Token.java und Parser.java ins Verzeichnis Compiler/MJ/, gehen Sie ins Verzeichnis Compiler und führen Sie runTestParser.bat aus.
  • Abschnitt 7.3: Aufbau abstrakter Syntaxbäume mit Coco/R
    Abschnitt 7.3. des Buchs beschreibt den Einsatz des Compilergenerators Coco/R zur Erzeugung eines Compilers, der aus einem Programm einen abstrakten Syntaxbaum aufbaut. Der Quellcode dieses Beispiels kann von Taste.zip heruntergeladen werden. Expandieren Sie diese Datei, gehen Sie ins Verzeichnis Taste und führen Sie dort build.bat aus. Anschließend können Sie den erzeugten Compiler z.B. mittels java Taste Test.tas ausführen.

Musterlösungen zu den Übungsaufgaben

Das Buch enthält mehr als 70 Übungsaufgaben zu allen behandelten Themen. Versuchen Sie, die Aufgaben am Ende jedes Kapitels eigenständig zu lösen. Hier sind die Musterlösungen dazu:

Kapitel 1: Überblick
- 1. Grammatik von E-Mail-Adressen
- 2. Grammatik vereinfachter boolescher Ausdrücke
- 3. Grammatik römischer Zahlen
- 4. Terminale Anfänge und Nachfolger (1)
- 5. Terminale Anfänge und Nachfolger (2)
- 6. Beseitigung von Linksrekursion (1)
- 7. Beseitigung von Linksrekursion (2)
- 8. Syntaxbäume (1)
- 9. Syntaxbäume (2)
- 10. Mehrdeutigkeit

Kapitel 2: Lexikalische Analyse
- 1. Reguläre Grammatiken (1)
- 2. Reguläre Grammatiken (2)
- 3. Reguläre Grammatiken (3)
- 4. Umwandlung einer regulären Grammatik in einen DFA
- 5. Umwandlung eines DFA in eine reguläre Grammatik
- 6. Einführung eines neuen Tokens
- 7. Erkennung geschachtelter Klammerkommentare
- 8. Scannen von Namen
- 9. Scannen von Zahlen
- 10. Scannen von Zeichenkonstanten
- 11. Implementierung des Scanners für MicroJava

Kapitel 3: Syntaxanalyse
- 1. Kellerautomat
- 2. Rekursiver Abstieg (1)
- 3. Rekursiver Abstieg (2)
- 4. Rekursiver Abstieg (3)
- 5. Rekursiver Abstieg (4)
- 6. Rekursiver Abstieg (5)
- 7. LL(1)-Bedingung (1)
- 8. LL(1)-Bedingung (2)
- 9. LL(1)-Bedingung (3)
- 10. Syntaxfehlerbehandlung mit allgemeinen Fangsymbolen
- 11. Syntaxfehlerbehandlung mit speziellen Fangsymbolen
- 12. Implementierung des Parsers für MicroJava

Kapitel 4: Attributierte Grammatiken
- 1. Verstehen attributierter Grammatiken
- 2. Römische Zahlen
- 3. Rechnen mit Uhrzeiten
- 4. Adressvergabe bei Variablendeklarationen
- 5. Kurse und Teilnehmer
- 6. Berechnen von Präfix-Ausdrücken
- 7. Skriptsprache für boolesche Ausdrücke
- 8. Übersetzung von XML nach Json

Kapitel 5: Symbolliste
- 1. Symbolliste mit einfachen Typen
- 2. Symbolliste mit Arrays
- 3. Symbolliste mit Klassen
- 4. Objekt- und Strukturknoten
- 5. Typprüfungen
- 6. Implementierung von Strukturäquivalenz
- 7. Parameter
- 8. Indirekte Rekursion
- 9. Implementierung der Symbolliste für MicroJava

Kapitel 6: Codeerzeugung
- 1. Operanden der Codeerzeugung (1)
- 2. Operanden der Codeerzeugung (2)
- 3. Ablaufkontrollstrukturen (1)
- 4. Ablaufkontrollstrukturen (2)
- 5. Zusammengesetzte boolesche Ausdrücke
- 6. Methodenaufruf
- 7. Funktionsaufruf
- 8. Inkrement- und Dekrement-Anweisung
- 9. Spracherweiterung: erweiterte while-Schleife
- 10. Spracherweiterung: Enumerationstypen
- 11. Spracherweiterung: Datentyp boolean
- 12. Implementierung des Codegenerators für MicroJava

Kapitel 7: Der Compilergenerator Coco/R
- 1. Pfadberechnung
- 2. Interpreter für boolesche Ausdrücke
- 3. Einlesen eines Telefonbuches
- 4. Komplexitätsanalyse
- 5. Extraktion von Dokumentationskommentaren

Kapitel 8: Exkurs: Bottom-up-Syntaxanalyse
- 1. Tabellenerzeugung (1)
- 2. Tabellenerzeugung (2)
- 3. Tabellenerzeugung (3)
- 4. LR-Fehlerbehandlung (1)
- 5. LR-Fehlerbehandlung (2)