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
15.04.24 V Dies Academicus -keine Vorlesung   18.04.24 V Einführung C/Rust
22.04.24 V Einführung C/Rust   25.04.24 V

Einführung Compilerbau

 
29.04.24 V Lexikalische Analyse: der Scanner   02.05.24 V Lexikalische Analyse: der Scanner
06.05.24 V

Syntaktische Analyse - Parsing I

Grundlagen

   09.05.24 V

keine Vorlesung (Himmelfahrt)
13.05.24 V

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

   16.05.24 V Syntaktische Analyse – Parsing II-b
Methoden der Syntaxanalyse LL(1)-Parsing
20.05.24 V

keine Vorlesung (Pfingsten)

   23.05.24 V

Syntaktische Analyse – Parsing III

Methoden der Syntaxanalyse LR-Parsing (1)
27.05.24 V

 Syntaktische Analyse – Parsing III &IV

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

   30.05.24 V

Syntaktische Analyse– Parsing IV

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

Syntaktische Analyse – Parsing V

LR/LR(k)-Parsing (1)

   06.06.24 V

Syntaktische Analyse – Parsing V

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

Syntaktische Analyse – Parsing V

LR/LR(k)-Parsing (3)

   13.06.24 V

Syntaktische Analyse – Parsing XI

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

Syntaktische Analyse – Parsing XII

LR/LR(k)-Parsing (5)

   20.06.24 V

Semantische Bearbeitung (1)
24.06.24 V

Semantische Bearbeitung (2)

 

Laufzeitumgebung(en)
und Codegenerierung & Optimierung (1)

   27.06.24 V

Anwendungen des Compilerbau's
01.07.24 V

 Laufzeitumgebung(en)
und Codegenerierung & Optimierung (2)

 

Zusammenfassung

   04.07.24 V

Repetitorium

 
08.07.24 V

keine Vorlesung

   11.07.24 V keine Vorlesung
15.07.24 V keine Vorlesung   18.07.24 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

 

Zeitplan

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: Donnerstag, 25. Juli 2024 15:00 ESZ0'110; ESZ0'115 

Klausurtermin 2: Freitag, 11. Oktober 2024 13:00 ESZ0'110; ESZ0'115

 

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