Modulcode:	Inf-CB
Englische Bezeichnung:	Compiler Construction
Modulverantwortliche(r):	Prof. Dr. Michael Hanus
Turnus:	unregelmäßig (WS16/17 SS18 WS19/20 WS21/22 SS23)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) WI (BSc Inf (15)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) MSc-WInf-WP-Inf (MSc WInf (21)) PI (MSc Inf (15)) WI (MSc Inf (15)) WI (MSc WInf (15)) WI (MEd Inf) WPI (MEd Inf) IS (SA) (MSc Inf (2-Fach)) WI (MSc WInf) IG (MSc Inf) IS (MSc Inf) MV (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-TGI Inf-FortProgP infDP-01a

Kurzfassung:

Die Übersetzung von Programmiersprachen ist eine wohldefinierte aber dennoch komplexe Aufgabe. Zur Beherrschung dieser Komplexität wurde eine Zerlegung in einzelne Übersetzungsaufgaben entwickelt, die heute in dieser oder ähnlicher Form in den meisten Übersetzern verwendet wird. Nach einer generellen Einführung in die Implementierung von Programmiersprachen mittels Interpretern, Übersetzern und partiellen Auswertern werden in dieser Vorlesung die einzelnen Übersetzungsaufgaben und die bekannten Lösungsansätze dazu vorgestellt. Im Einzelnen werden behandelt: Programmiersprachen, Interpreter, Übersetzer, partielle Auswerter, lexikalische Analyse, syntaktische Analyse, semantische Analyse, Codeerzeugung

Lernziele:

Die Studierenden erlernen die Techniken, um höhere Programmiersprachen auf herkömmlichen Rechnerarchitekturen effizient zu implementieren. Sie erlernen hierbei das gesamte Spektrum vom Einlesen strukturierter Sätze über deren Manipulation bis zur effizienten Codeerzeugung auf der Basis geeigneter Laufzeitstrukturen. Nach Abschluss dieses Moduls sind die Studierenden in der Lage, Werkzeuge zum Übersetzerbau zu entwickeln und einzusetzen beziehungsweise an neuen Techniken zur Realisierung von Sprachen (z.B. domänenspezifische Sprachen, Spezifikationssprachen) weiterzuarbeiten.

Lehrinhalte:

Die Übersetzung von Programmiersprachen ist eine wohldefinierte aber dennoch komplexe Aufgabe. Zur Beherrschung dieser Komplexität wurde eine Zerlegung in einzelne Übersetzungsaufgaben entwickelt, die heute in dieser oder ähnlicher Form in den meisten Übersetzern verwendet wird. Nach einer generellen Einführung in die Implementierung von Programmiersprachen mittels Interpretern, Übersetzern und partiellen Auswertern werden in dieser Vorlesung die einzelnen Übersetzungsaufgaben und die bekannten Lösungsansätze dazu vorgestellt. Im Einzelnen werden behandelt:

1. Programmiersprachen, Interpreter, Übersetzer, partielle Auswerter
   • Begrifssabgrenzung
   • Generierung von Übersetzern durch partielle Auswertung
   • Kombination von Interpretern und Übersetzern
   • Bootstrapping
2. Lexikalische Analyse
   • Spezifikationsmethode: reguläre Ausdrücke
   • Implementationsmethode: endliche Automaten
3. Syntaktische Analyse
   • Spezifikationsmethode: kontextfreie Grammatiken
   • Implementationsmethode: rekursive Abstiegsparser, LL-Grammatiken
   • Implementationsmethode: Bottom-up-Analyse, LR-Grammatiken und ihre Teilklassen
   • Parsergeneratoren
   • Methoden zur Fehlerbehandlung
4. Semantische Analyse
   • Semantische Aktionen
   • Attributierte Grammatiken
   • Abstrakte Syntax
   • Symboltabellenverwaltung
5. Codeerzeugung
   • Laufzeitspeicherorganisation
   • Zwischencodeerzeugung
   • Optimierung von Zwischencode
   • Zielcodeauswahl
   • Erzeugung optimaler Zielcodes
   • Registerallokation
   • Techniken zur Codeoptimierung
   • Programmanalyse, Einführung in die Datenflussanalyse und abstrakte Interpretation

Weitere Voraussetzungen:

Grundkenntnisse prozeduraler Sprachen und Kenntnisse der Programmiersprache Haskell, die z.B. im Modul "Deklarative Programmierung" (infDP-01a) oder im Modul "Fortgeschrittene Programmierung" (Inf-FortProgP) verrmittelt werden, sowie Grundkenntnisse der theoretischen Informatik (Grammatiken, endliche Automaten u.ä.).

Prüfungsleistung:

Mündliche Abschlussprüfung am Vorlesungsende

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

• A. Aho, R. Sethi, J. Ullman: Compilerbau (Teil 1 + 2), Oldenbourg, 1999
• A. Appel: Modern compiler implementation in ML, Cambridge UP, 1997
• R.H. Güting, M. Erwig: Übersetzerbau, Springer 1999
• W. Waite, G. Goos: Compiler Construction, Springer, 1984
• R. Wilhelm, D. Maurer: Übersetzerbau: Theorie, Konstruktion, Generierung, Springer, 1992
• N. Wirth: Grundlagen und Techniken des Compilerbaus, 2. Auflage, Oldenbourg, 1986

Verweise:

Kommentar: