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 4: Semantische Pruefungen (SG und PG)
Vorlesung: Skript Seite S18
Vorlesung: Skript Seite P19
Vorlesung: Grune/Jacobs "Hygiene in CF Grammars"
Aufgaben: Aufgaben 4
Woche 5: NEA (SG), FIRST-Mengen (PG), Parsingmethoden 1 (alle)
Vorlesung: Skript Seiten aus S19 - S34
Vorlesung: Skript Seiten aus P20 - P29
Aufgaben: Aufgaben 5
Aufgaben: Grune/Jacobs, Kapitel 9.4 und 9.5
Woche 6: DEA (SG), LR-NEA (PG), Parsingmethoden 2 (alle)
Vorlesung: Skript Seiten aus S35 - S49
Aufgaben: Aufgaben 6
Aufgaben: Grune/Jacobs, Kapitel 9.6 und 9.7
Woche 7: Min-DEA 1 (SG), LR-DEA (PG), Parsingmethoden 3 (alle)
Vorlesung: Skript Seiten aus S50 - S67
Aufgaben: Aufgaben 7
Aufgaben: Grune/Jacobs, Kapitel 9.7.1
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.