Spezialvorlesung Compilerbau, WS2004/2005

Allgemeines

Achtung: Termin und Ort teilweise geändert

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.

, July 29, 2004