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*

Einführung Übungskonzept

Einführung C/Rust

   17.04.25 V

Einführung Compilerbau

 
21.04.25 V keine Vorlesung (Ostern)   24.04.25

V*

Einführung C/Rust

 
28.04.25 V Lexikalische Analyse: der Scanner  (1)   01.05.25 V keine Vorlesung
05.05.25 V

Lexikalische Analyse: der Scanner (2)

   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

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

   29.05.25 V

keine Vorlesung (Pfingsten)
02.06.25 V

 Syntaktische Analyse – Parsing IV

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

   05.06.25 V

keine Vorlesung (Tag der Informatik)
09.06.25 V

keine Vorlesung (Pfingsten)

   12.06.25 V

Syntaktische Analyse – Parsing V

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

Syntaktische Analyse – Parsing V

LR/LR(k)-Parsing (2+3)

   19.06.25 V

Syntaktische Analyse – Parsing VI

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

V

*

Anwendungen des Compilerbau's

   26.06.25

V

*

Repetitorium
30.06.25 V

Semantische Bearbeitung (1)

 

   03.07.25 V

Semantische Bearbeitung (2)
07.07.25 V

Laufzeitumgebung(en)
und Codegenerierung & Optimierung (1)

 

   10.07.25 V

Laufzeitumgebung(en)
und Codegenerierung & Optimierung (2)

Zusammenfassung
14.07.25 V keine Vorlesung   17.07.25 V keine Vorlesung
 

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

 

 

Kalenderwoche

Aufgabe

Übungsthema

16: 14.04. - 18.04.  

 

— keine UE —

17: 21.04. - 25.04.

 

Organisatorisches, Compilertechnologie, Toolchain, Einführung C

18: 28.04. - 02.05.

Taschenrechner

Vorstellung Taschenrechner, Visitor Pattern für Syntaxbaum

19: 05.05. - 09.05.

 

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

20: 12.05. - 16.05.

Lexikalische Analyse

Besprechung Taschenrechner, Vorstellung Lexer, Scannergenerator, Zustandsübergangstabelle

21: 19.05. - 23.05.

 

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

22: 26.05. - 30.05.

Syntaktische Analyse

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

23: 02.06. - 06.06.

 

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

24: 09.06. - 13.06.

Semantische Analyse

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

25: 16.06. - 20.06.

 

Interpretation eines abstrakten Syntaxbaumes, Codegenerierung

26: 23.06. - 27.06.

Codegen/Interpretation

Besprechung Type-Checking, Vorstellung Interpretation

27: 30.06. - 04.07.

 

Prüfungsvorbereitung

28: 07.07. - 11.07.

 

Prüfungsvorbereitung

29: 14.07. - 18.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