Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Software Engineering

Compilerbau

 

Wann und Wo

Vorlesung: Montag, 11-13 Uhr, RUD 25, 3.001
Vorlesung: Donnerstag, 13-15 Uhr, RUD 25, 3.001
Übung: Dienstag, 9-11 Uhr, RUD 25, 3.113
Übung: Dienstag, 11-13 Uhr, RUD 25, 3.113
Übung: Mittwoch, 11-13, RUD 25, 3.113
Übung; Donnerstag, 11-13, RUD 25, 3.101

Wer

Dozent: Prof. Grunske / Dorian Weber

Beschreibung und Aufbau der Lehrveranstaltung

Studierende erlernen die Grundlagen der Analyse und der Übersetzung von Programmiersprachen und wenden diese beim Bau eines einfachen Compilers selbst an.

  • Architektur und Aufgaben eines Compilers
  • Anwendung der Theorie der Automaten (endliche Automaten, Kellerautomaten) auf Probleme des Übersetzerbaus
  • Konzepte und Techniken der lexikalischen Analyse
  • Konzepte und Techniken des Parsings (LL Analyse, LR Analysetechniken)
  • Semantische Analyse (inkl. Typerkennung, -verträglichkeit, Gültigkeitsbereiche, Abhängigkeitsanalyse)
  • Grundlagen der Codegenerierung, Codeoptimierung und Verlinkung im Überblick
  • Praktische Konstruktion eines Compilers aus den einzelnen Phasen
  • Moderne Techniken wie JIT Compilation und neuere Forschungsthemen

 

Für Studierende der SPO 2015 besteht die LV nur aus V3/Ü1 und 5 LP.

Studierende nach der SPO 2022 erhalten 8 LP.


Wechselnde in die SPO 2022, die das Modul bereits mit 5 LP absolviert haben, erbringen zusätzliche 3 LP nach dem PA-Beschluss zum "Übergang zwischen Bachelor-Studium SPO 2015 und Bachelor-Studium SPO 2022" vom 24.10.2022 mit einer erfolgreich absolvierten Zusatzaufgabe (Programmierprojekt, in dem die Studierenden einen vollständigen Compiler bestehend aus Scanner und Parser für eine neuartige Anwendungsaufgabe schreiben).

 

Terminplanung Vorlesung bis Semesterende (Änderungen möglich)

Mo, 11.00-13.00  

Thema

   Do, 13.00-15.00  

Thema
14.04.25 V Dies Academicus - keine Vorlesung   17.04.25 V Einführung C/Rust
21.04.25 V keine Vorlesung (Ostern)   24.04.25 V

Einführung Compilerbau

 
28.04.25 V Lexikalische Analyse: der Scanner   01.05.25 V keine Vorlesung
05.05.25 V

Lexikalische Analyse: der Scanner

   08.05.25 V

keine Vorlesung

12.05.25 V

Syntaktische Analyse - Parsing I

Grundlagen

   15.05.25 V Syntaktische Analyse – Parsing II-a
Methoden der Syntaxanalyse LL(1)-Parsing
19.05.25 V

Syntaktische Analyse – Parsing II-b

Methoden der Syntaxanalyse LL(1)-Parsing

   22.05.25 V

Syntaktische Analyse – Parsing III

Methoden der Syntaxanalyse LR-Parsing (1)
26.05.25 V

 Syntaktische Analyse – Parsing III & IV

LR-Parsing/ Shift-Reduce  (2) & Präzedenz-Parsing (1)

   29.05.25 V

keine Vorlesung (Himmelfahrt)
02.06.25 V

Syntaktische Analyse– Parsing IV

Shift-Reduce & Präzedenz-Parsing (2)

   05.06.25 V

Syntaktische Analyse – Parsing V

LR/LR(k)-Parsing (1)
09.06.25 V

keine Vorlesung (Pfingsten)

   12.06.25 V

Syntaktische Analyse – Parsing V

LR/LR(k)-Parsing (2)
16.06.25 V

Syntaktische Analyse – Parsing V

LR/LR(k)-Parsing (3)

   19.06.25 V

Syntaktische Analyse – Parsing XI

LR/LR(k)-Parsing (4)
23.06.25 V

Syntaktische Analyse – Parsing XII

LR/LR(k)-Parsing (5)

   26.06.25 V

Semantische Bearbeitung (1)
30.06.25 V

Semantische Bearbeitung (2)

Laufzeitumgebung(en)
und Codegenerierung & Optimierung (1)

   03.07.25 V

Anwendungen des Compilerbau's

 
07.07.25 V

Laufzeitumgebung(en)
und Codegenerierung & Optimierung (2)

 

Zusammenfassung

   10.07.25 V Repetitorium
14.07.25 V keine Vorlesung   17.07.25 V keine Vorlesung
 

Terminplanung Übung bis Semesterende (Änderungen möglich)

  • Termine: Di 09-11, 11-13, Mi 11-13, Do 11-13
  • relevante Feiertage: 1. Mai (Mi), 9. Mai (Do)
  • Vorschlag: Ausweichtermine zu Feiertagen
  • zwei Vorlesungstermine zur Einführung in C & Rust: 18.04. (Do) und 22.04. (Mo)
  • Übungsaufgaben in C oder Rust
  • Dienstag: C und Rust
  • Mittwoch: C oder Rust
  • Donnerstag: Negation von Mittwoch

 

Kalenderwoche

Aufgabe

Übungsthema

16: 15.04. - 19.04.  

 

— keine UE —

17: 22.04. - 26.04.

 

Organisatorisches, Compilertechnologie, Toolchain, Makefile

18: 29.04. - 03.05.

Taschenrechner

Vorstellung Taschenrechner, Visitor Pattern für Syntaxbaum

19: 06.05. - 10.05.

 

reguläre Ausdrücke, NFA -> DFA, Zustandsminimierung

20: 13.05. - 17.05.

Lexikalische Analyse

Besprechung Taschenrechner, Vorstellung Lexer, Scannergenerator, Zustandsübergangstabelle

21: 20.05. - 24.05.

 

kontextfreie Grammatiken, Ableitungsbäume, Top-Down Parser, rekursiver Abstieg

22: 27.05. - 31.05.

Syntaktische Analyse

Besprechung Lexer, Vorstellung Parser, Parsergenerator, Bottom-Up Syntaxanalyse, Syntaxanalysetabelle

23: 03.06. - 07.06.

 

Konstruktionsverfahren, Zustandsübergangsgraphen für LR(0), SLR(1), LR(1), LALR(1)

24: 10.06. - 14.06.

Semantische Analyse

Besprechung Parser, Vorstellung Type-Checking, blockstrukturierte Symboltabelle, abstrakter Syntaxbaum

25: 17.06. - 21.06.

 

Interpretation eines abstrakten Syntaxbaumes, Codegenerierung am Beispiel des C-Compilers nach Assembly

26: 24.06. - 28.06.

Codegen/Interpretation

Besprechung Type-Checking, Vorstellung Interpretation

27: 01.07. - 05.07.

 

Prüfungsvorbereitung

28: 08.07. - 12.07.

 

Prüfungsvorbereitung

29: 15.07. - 19.07.

— Prüfungszeitraum —

— Prüfungszeitraum —

Voraussetzungen und Prüfung

Die Lehrveranstaltung wird mit einer 120-Minuten-Klausur geprüft.

Für die Zulassung zur Prüfung ist ferner die Teilnahme am Übungsbetrieb verpflichtend.

Klausurtermin 1:

Klausurtermin 2:

Skript und Übungsaufgaben

Das Skript zu dieser Veranstaltung (Folien), Übungsblätter und weitere Materialien werden sukzessive in Moodle bereitgestellt.

Im Verlauf des Semesters werden größere Übungsaufgaben gestellt, die sich an den Inhalten der Vorlesung orientieren. Übungsaufgaben und evt Lösungsvorschläge werden ebenfalls über Moodle verfügbar sein.

Literatur

    • Kernighan, Ritchie: The C Programming Language, Prentice Hall, 2. Auflage, 1988, 1990
    • Aho, Sethi, Ullman: Compilers: Principles, Techniques und Tools, Addison-Wesley Publishing Company, 2. Auflage, 2007 (bekannt als „Drachenbuch“)
    • Wilhelm, Maurer: Übersetzerbau: Theorie, Konstruktion, Generierung, Springer Verlag, 2. Auflage
    • Fischer/LeBlanc: Crafting a Compiler with C, The Benjamin Cummings Publishing Company, 1991