Spezialvorlesung Compilerbau, WS2004/2005

Allgemeines

Achtung: Termin und Ort teilweise geändert

	Vorlesung		Übung
Durchführung	Prof. Dr. Peter Thiemann		Matthias Neubauer
E-mail	siehe pers. Homepage		siehe pers. Homepage
Zeit	Mo 15-17	Mi 16-17	Mi 17-18
Ort	SR 00-006, Geb. 051	SR 02-027, Geb. 052	SR 02-027, Geb. 052

Vorlesung

Erste Vorlesung: 18 Oktober 2004
Geänderte Nachholtermine für ausgefallene Vorlesungen:
- 31.01.2005: Vorlesung von 15-18 Uhr (drei statt zwei Stunden)
- 16.02.2005: Vorlesung von 16r-18 Uhr (letzte Übung verschoben)
- 21.02.2005: Vorlesung von 15-17 Uhr
- 23.02.2005: Übung 17-18 Uhr
Abschlussprüfung: mündlich, am 31.03.2005
Zur Vorlesung wird es ein Skript in englischer Sprache geben.
Parallel zur Vorlesung bieten wir ein (Hauptstudiums-) Praktikum an. Ziel des Praktikums ist die Erstellung eines Compilers unter Verwendung der in der Vorlesung vorgestellten Methoden.

Übungen

Ein Übungsblatt pro Woche.
Erste Übung am 20. Oktober.

Übungsaufgaben

Material

Folien zum 20.10.04 (ppt) (pdf)
Lexikalische Analyse 25.10.04
Lexikalische Analyse II 27.10.04
Top-Down Syntaxanalyse 08.11.04 und 10.11.04
Bottom-Up Syntaxanalyse 15.11.04 und 17.11.04
SLR und LALR 22.11.04
Beispiele zum 24.11.04: Yacc Spezifikationen
Semantische Analyse 28.11.04 - Attributgrammatiken
Lambdakalkül 13.12.04 und 15.12.04
Angewandter Lambdakalkül und Lambda Lifting 20.12.04 und 22.12.04 Revidiert am 24.01.05
Implementierung des Lambdakalkül: Transformation in A-Normalform 17.01.05; 19.01.05 und 24.01.05

Optimierende Transformation in A-Normalform (in OCaml)
Kodegenerierung: 26.01.05; 31.01.05; 02.02.05 MIPS Architektur (zur Info)

Material dazu im Buch Modern Compiler Construction (in ML) von Andrew Appel:
Instruction Selection
Kapitel 9
Liveness Analysis
Kapitel 10
Garbage Collection: 07.02.05
Registerallokation: 14.02.05

Material dazu im Buch Modern Compiler Construction (in ML) von Andrew Appel:
Register Allocation
Kapitel 11
Kodeoptimierung: 16.02.05 und 21.02.05

Material dazu in
- Modern Compiler Construction (in ML): Kapitel 17 (.1, .2, .3 und Teile von .4)
- Aho, Sethi, Ullman: Kapitel 9.4 und 9.9
Referenzen zum Skript

Inhalt

Die zentrale Aufgabe des Compilerbaus ist die Entwicklung und Implementierung von Übersetzungen von höheren Programmiersprachen in Maschinenkode. Diese Aufgabe berührt viele wichtige Probleme von allgemeinem Interesse.

Lexikalische und syntaktische Analyse

Zunächst parst ein Compiler das Eingabeprogramm, d.h. er übersetzt eine Zeichenreihe in einen Baum, der die Struktur des Programms wiederspiegelt. Hierbei werden Konzepte aus der Theorie der formalen Sprachen, insbesondere der regulären und kontextfreien Sprachen, praktisch eingesetzt.
Semantische Analyse

Als nächstes formt der Compiler die Baumstruktur um und analysiert sie. Diese Phase wird mittels Attributgrammatiken spezifiziert.
Zwischenkode

Schließlich generiert der Compiler einen maschinenunabhängigen Zwischenkode, der über mehrere Schritte transformiert und optimiert wird.
Speichermodell und Speicherbereinigung

Der Compiler bildet Datenstrukturen auf Speicherstrukturen ab. Für Sprachen mit dynamischen Typen und/oder Speicherbereinigung müssen hierbei spezielle Vorkehrungen getroffen werden.
Maschinenkode

Im letzten Schritt wird der Zwischenkode in Maschinenkode übersetzt und maschinenspezifischen Optimierungen unterzogen. Dabei werden Techniken wie Baumgrammatiken, dynamische Programmierung sowie Graphfärbung verwendet.

Da der Compilerbau eine lange Tradition hat, ist die Struktur von Compilern wohldurchdacht. Somit kann ein Compiler als Beispiel für ein gut strukturiertes Softwaresystem dienen. "Wer einen Compiler schreiben kann, kann jedes Programm schreiben."

Die Techniken des Compilerbau kommen auch an vielen anderen Stellen zum Einsatz. Zum Beispiel vereinfachen Verfahren der Syntaxanalyse das Lesen von Konfigurationsdateien und textlichen Benutzereingaben, sowie die Definition von Mini-Sprachen erheblich.

Wissen über das Speichermodell ist hilfreich bei der Fehlersuche in systemnahen Programmiersprachen (C, C++).

OCaml

Die Kodebeispiele im Skript sind in der Programmiersprache Objective Caml (OCaml) geschrieben. OCaml ist eine objekt-orientierte und funktionale Sprache mit polymorphem Typsystem, Patternmatching, sowie einem mächtigen Modulsystem. Aufgrund dieser Eigenschaften ist OCaml sehr gut geeignet zum Schreiben von Compilern.

Die Sprache OCaml Die aktuelle Version ist 3.08. Implementierungen sind verfügbar für Unix, Win32 und MacOS (source und binary).
Das OCaml Referenzhandbuch (online, pdf, postscript)
The OCaml FAQ
OCaml Bücher in Englisch, Französisch, Deutsch und Italienisch Die Bücher basieren teilweise (CousineauMauny1998, Gudenberg1996) auf älteren Sprachversionen.
Freiverfügbare Einführung in die Programmierung mit OCaml.
Viele Werkzeuge und Bibliotheken sind verfügbar im OCaml Hump.

References

[1]: Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers Principles, Techniques, and Tools. Addison-Wesley, 1986.
[2]: Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.
[3]: Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.
[4]: Guy Cousineau and Michel Mauny. The Functional Approach to Programming. Cambridge University Press, 1998.
[5]: Christopher W. Fraser and David R. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, 1995.
[6]: Rene Leermakers. The Functional Treatment of Parsing. Kluwer Academic Publishers, Boston, 1993.
[7]: Xavier Leroy. The Objective Caml system release 3.02, Documentation and user's manual. INRIA, France, July 2001. From http://pauillac.inria.fr/caml.
[8]: Reinhard Wilhelm and Dieter Maurer. Übersetzerbau -- Theorie, Konstruktion, Generierung -- 2 Auflage. Lehrbuch. Springer-Verlag, Berlin, Heidelberg, 1996.

Matthias Neubauer

, July 29, 2004