Implementierung von Compilerbau-Werkzeugen SS 22

Themen und Ziele

Wir wollen das innere Funktionieren der im Compilerbau genutzten Generatoren "Flex" (zur Erzeugung von Scannern) und "Bison" (zur Erzeugung von Parsern) genau verstehen und bauen zu diesem Zweck eigene Versionen dieser Programme. Wir werden uns wegen des dann einfacheren Testens auf gemeinsame Eingabesprachen fuer die Tools einigen. Die Implementierungssprache (und die Zielsprache) koennen aber von den Teams selber und durchaus unterschiedlich gewaehlt werden. Ziel ist es, die entstandenen Programme zu benutzen, um die Scanner und Parser fuer die Tools (jeweils einer fuer jedes Tool) selber zu generieren - das ist der sogenannte "Bootstrap".

Literatur

Grune, Jacobs, Parsing Techniques, Springer
Meyer, Grundkurs Compilerbau, Rheinwerk Computing
Aho, Lam, Sethi, Ullman, Compilers, Pearson

Organisation

Den Teilnehmenden wird empfohlen, sich in Zweierteams zu organisieren, wobei dann jeweils eine Person fuer den Scannergenerator und die andere fuer den Parsergenerator verantwortlich ist. Einzelbearbeitungen werden aber auch akzeptiert; dann muss natuerlich nur einer der Generatoren implementiert werden.

Ablauf

Woche 1: Compiler, Generatoren, Grammatiken, Automaten

Vorlesung: Skript Seite 1 - 8
Demo-Programm: Skript Seite D0 - D5
Einschub: Skript Seite E1 - E6
Aufgaben: Aufgaben 1

Woche 2: a) Spezifikation des Scanner-Generators, Bootstrap-Scanner

Woche 2: b) Spezifikation des Parser-Generators, Bootstrap-Parser

Vorlesung: Skript Seite S0 - S7
Vorlesung: Skript Seite P0 - P9
Aufgaben: Aufgaben 2

Woche 3: Abstrakte Syntax und Namenstabelle (SG und PG)

Vorlesung: Skript Seite S8 - S17
Vorlesung: Skript Seite P10 - P18
Aufgaben: Aufgaben 3

Woche 8: Min-DEA 2 (SG), LALR(1)-DEA (PG)

Aufgaben: Aufgaben 8

Woche 9: Tabellenausgabe (SG und PG)

Vorlesung: Skript Seiten aus S68 - S74
Aufgaben: Aufgaben 9

Woche 10: Treiber (SG und PG)

Vorlesung: Skript Seite S75
Vorlesung: Skript Seiten P50 - P53
Aufgaben: Aufgaben 10

Woche 11: Bootstrap (SG und PG)

Vorlesung: Skript Seite S76
Aufgaben: Aufgaben 11

Woche 12: Demonstration und Abschluss

Tests

Version 0: Bootstrap-Scanner
Version 1: Bootstrap-Parser
Version 2: Abstrakte Syntax, Semantik-Pruefungen
Version 3: SG: NFA, PG: FIRST sets
Version 4: SG: DFA, PG: LR(0) NFA with channels
Version 5: SG: minimal DFA, PG: LALR(1) DFA
Version 6: SG, PG: Tabellen-Erzeugung und Ausgabe
Version 7: SG, PG: Treiber, Demo-Scanner und Parser

Material

Demo-Programm in C
Demo-Programm in Flex/Bison
Demo-Programm in SG/PG
SG: Eingabesprache
PG: Eingabesprache
DFA-Minimierung 1
DFA-Minimierung 2
DFA-Minimierung 3
Scanner und Parser fuer C

Bewertung

Es zaehlt (neben aktiver Beteiligung am seminaristischen Unterricht) vor allem der erreichte Funktionsumfang der Software. Prinzipiell bestanden (50%) wird der Kurs mit korrekter Erzeugung des jeweiligen AST und den semantischen Pruefungen. Die verbleibenden 50% verteilen sich dann auf die Automatenkonstruktionen, die Tabellenerzeugung und den jeweiligen Treiber. Genaueres besprechen wir in der Veranstaltung.