Spezialvorlesung Compilerbau, WS 2009/2010

Allgemeines

Ankündigungen

• Die Vorlesung am 07.12.2009 entfällt!
• Am 1./7.12.2009 wird Prof. Neil Jones (University of Copenhagen) zum Thema Programmanalyse vortragen. Als Vorbereitung empfiehlt es sich aus Nielson,Nielson,Hankin. Principles of Program Analysis.Sprinter, 2005. die Kapitel 1 (p.1- 10) und 2.1.(p.35-54) zu lesen. Das Buch ist auch in der Fakultätsbibliothek zu finden.
• Am 09.11.2009 findet die Vorlesung von 17:00-17:45 Uhr statt; am 10.11.2009 ist dann von 14-16 Uhr Vorlesung.
• Die Übungsstunde am 10.11.2009 entfällt.

Organisatorisches

• Übungen
• Forum zur Diskussion bei Fragen und Problemen

Materialien

• Folien zur Vorlesung
• Attributgrammatiken
• Folien zur Intermediate Representation und Speichermanagement
• Folien zu Kontexten und Canonical Trees
• Folien zu Instruction Selection
• Data flow analysis
• Folien zu Kapitel 15 "Funktionale Programmiersprachen"
• Folien zu Kapitel 16 "Polymorphic Types"
• Folien zu Kapitel 13 "Garbage Collection"
• Folien zu Kapitel 18 "Loop Optimizations"
• Folien zu Kapitel 19 "Static Single-Assignment Form"
• Folien Register Allocation for Programs in SSA Form
• Die Vorlesungen wird sich zu weiten Teilen an Andrew Appel with Jens Palsberg, Modern Compiler Implementation in Java, 2nd edition. Cambridge University Press (2002) orientieren.

Weitere Literatur

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.   Reinhard Wilhelm and Dieter Maurer. Übersetzerbau -- Theorie, Konstruktion, Generierung -- 2. Auflage. Lehrbuch. Springer-Verlag, Berlin, Heidelberg, 1996.

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++).