Spezialvorlesung Compilerbau, WS 2009/2010
Allgemeines
| Vorlesung | Prof. Dr. Peter Thiemann |
| thiemann@info... | |
| Zeit | Mo 16-18 Uhr, Di 14-15 Uhr |
| Ort | Geb. 052, HS 02-017 |
| Übung | Annette Bieniusa |
| bieniusa@info... | |
| Zeit | Di 15-16 |
| Ort | Geb. 052, HS 02-017 |
Ankündigungen
- 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
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++).
Materialien
- Folien zur Vorlesung
- Attributgrammatiken
- Folien zur Intermediate Representation und Speichermanagement
- 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
- 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.
- Reinhard Wilhelm and Dieter Maurer. Übersetzerbau -- Theorie, Konstruktion, Generierung -- 2. Auflage. Lehrbuch. Springer-Verlag, Berlin, Heidelberg, 1996.