Vorlesung Übersetzerbau

Vorlesung Übersetzerbau

Die Vorlesung Übersetzerbau erzählt eine der Erfolgsgeschichten der Informatik:

Von der automatischen Übersetzung maschinenunabhängiger Programme (`high-level') in maschinenausführbare Programme (`low-level').

Vor 50 Jahren war man der Überzeugung, dass eine Automatisierung des Übersetzungsprozesses nicht möglich ist. Heute ist dies (selbstverständliche) Realität. Zwar werden die wenigsten jemals einen Übersetzer für eine ausgewachsene Programmiersprache wie C, Java, Haskell oder Prolog schreiben, dennoch sind viele Teilgebiete des Übersetzerbaus unmittelbar für die Berufspraxis relevant, zum Beispiel:

Syntaxanalyse: Eingabevalidierung, Lesen von Konfigurationsdateien etc;
viele Probleme sind der Natur nach Übersetzungsprobleme;
Entwurf und Implementierung sogenannter anwendungsspezischer Sprachen (`domain-specific languages'): wie z.B. Skriptsprachen, Web-Sprachen, Schaltkreisentwurf, Robotersteuerung, Bildbeschreibungssprachen etc.

Darüber hinaus sind Übersetzer

Paradebeispiele für gut durchdachten Softwareentwurf ("Wer einen Compiler schreiben kann, kann jedes Programm schreiben.");
Paradebeispiele für den erfolgreichen Einsatz formaler Methoden ("In der Informatik gibt es keine Theorie.").

Material:

Vorlesungsfolien
Zusatzmaterial
Übungsaufgaben

1 Vorlesungsfolien

Teil I: Grundlagen des Übersetzerbaus
1. Einführung: PDF, PDF (weißer Hintergrund), PS (4 Folien auf einer Seite), PS (4 Folien auf einer Seite, weißer Hintergrund).
2. Lexikalische Analyse: PDF, PDF (weißer Hintergrund), PS (4 Folien auf einer Seite), PS (4 Folien auf einer Seite, weißer Hintergrund).
3. Syntaxanalyse: PDF, PDF (weißer Hintergrund), PS (4 Folien auf einer Seite), PS (4 Folien auf einer Seite, weißer Hintergrund).
4. Abstrakte Syntax: PDF, PDF (weißer Hintergrund), PS (4 Folien auf einer Seite), PS (4 Folien auf einer Seite, weißer Hintergrund).
5. Semantische Analyse: PDF, PDF (weißer Hintergrund), PS (4 Folien auf einer Seite), PS (4 Folien auf einer Seite, weißer Hintergrund).
6. Zwischensprachen: PDF, PDF (weißer Hintergrund), PS (4 Folien auf einer Seite), PS (4 Folien auf einer Seite, weißer Hintergrund).
7. Codeerzeugung: PDF, PDF (weißer Hintergrund), PS (4 Folien auf einer Seite), PS (4 Folien auf einer Seite, weißer Hintergrund).
8. Codeoptimierung: -
Teil II: Fortgeschrittene Themen
1. Interpreter, Übersetzer und partielle Auswerter
2. Domain-specific Languages (DSLs)
3. Polymorphe Typen
4. Garbage Collection

2 Zusatzmaterial

Ein einfacher Übersetzer: Replace.pdf (Quellprogramm: Replace.lhs).
Lexikalische Analyse: PDF (Quellprogramme: Lexing.tar.bz2). In Java von Stefan Schulz: regexp.tar.bz2.
Syntaxanalyse: Parserkombinatoren in Erlang von Matthias Kretschmer.

Möchte man die Haskell-Programme ausführen, muss zusätzlich die folgende Bibliothek installiert werden: librh.tar.bz2.

3 Übungsaufgaben

Übungsblatt 1: PDF.
Übungsblatt 2: PDF.
Übungsblatt 3: PDF.
Übungsblatt 4: PDF.
Übungsblatt 5: PDF.
Übungsblatt 6: PDF.
Übungsblatt 7: PDF.
Übungsblatt 8: PDF.
Übungsblatt 9: PDF.
Übungsblatt 10: PDF.
Übungsblatt 11: PDF.

Ralf Hinze, ralf@informatik.uni-bonn.de, 12 October 2004.