Spezialvorlesung Compilerbau, WS2006/2007

Allgemeines

	Vorlesung	Übung
Durchführung	Prof. Dr. Peter Thiemann	Stefan Wehr
E-mail	siehe pers. Homepage	siehe pers. Homepage
Zeit	Mo 16-18, Mi 16-17	Mi 17-18
Ort	SR 00-010/14 Geb. 101	SR 00-010/14 Geb. 101

Die Auswertung der Evaluation ist verfügbar.

Achtung: Vorlesung und Übung fallen in der Woche vom 29.1.2007 bis zum 2.2.2007 aus. Als Ersatz geht die Vorlesung am Mittwoch ab sofort bis 18 Uhr; die Übung findet dann im Anschluss daran statt.

Vorlesung

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 8.11.2006
Übungsaufgaben

Material

T Diagramme
Einführung in OCaml (PDF, PDF 4 auf 1)
Beispielspezifikationen für Lexikalische Analyse
Verschiedene Interpreter (08.01.2007)
Ein-Pass Transformation in A-Normalform (17.01.2007)
Codeerzeugung für MIPS (22.01.2007)
Codeerzeugung mit Templates (24.01.2007)
Inhaltsverzeichnis
Literaturverzeichnis
Lexikalische Analyse
Syntaxanalyse (aktualisiert am 13.12.2006)
Semantische Analyse
Lambda Liftung und A-Normal Form
Beispiele für Continuations
MIPS Architektur

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.09. Implementierungen sind verfügbar für Unix, Win32 und MacOS (source und binary).
Das OCaml Referenzhandbuch (online, pdf, postscript).
The OCaml FAQ.
Developing Applications with Objective Caml . Das Buch von Emmanuel Chailloux, Pascal Manoury und Bruno Pagano deckt fast alle Aspekte der Programmierung mit OCaml ab.
Introduction to the Objective Caml Programming Language . Das Skript von Jason Hickey ist eine gute und relativ kurze Einführung in die Sprache OCaml.
Using, Understanding, and Unraveling The OCaml Language. From Practice to Theory and vice versa . Die Lecture Notes von Didier Rémy geben eine Einführung in OCaml und die darunterliegende Theorie.
Viele Werkzeuge und Bibliotheken sind im OCaml Hump verfügbar.
Gutes Tutorial zu OCamlyacc

Referenzen

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