Spezialvorlesung Compilerbau, WS2006/2007

Allgemeines

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

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.