Übersetzerbau, Spezialvorlesung, WS1999/2000
Peter Thiemann
- Vorlesung: Mo 13-15 (051-03-026), Fr 11-13 (051-03-026)
- Übungen: zweiwöchig freitags im Wechsel mit der Vorlesung, Beginn: 5.11.1999
Der Übersetzerbau/Compilerbau beschäftigt sich mit der Übersetzung von
höheren Programmiersprachen in Maschinenprogramme. Dabei treten
interessante Probleme auf, deren Lösung oft von allgemeinem Interesse
sind.
Zunächst muss ein Compiler die Struktur eines Programmtextes
anhand der kontextfreien Grammatik der Sprache ermitteln. Dies
geschieht durch einen Parser, der ein Wort in einer
kontextfreien Sprache in einen Strukturbaum überführt.
Das Problem des Parsens tritt auch in vielen anderen Kontexten auf
(Lesen von Konfigurationsdateien, Definieren von eigenen Minisprachen,
Lesen von Benutzereingaben, uva.). Mit den Techniken der Vorlesung
können solche Probleme schnell und effizient gelöst werden.
Auf dem Strukturbaum werden eine Reihe von Analysen und
Transformationen durchgeführt, mit dem Ziel die Programmstruktur der
Struktur der wirklichen Maschine anzunähern. Hier sind zum Beispiel
Typüberprüfung oder Sichtbarkeitsanalyse angesiedelt.
Zum Schluss erfolgt die Übersetzung in Maschinensprache, sowie die
Programmoptimierung. In dieser Phase kommen verschiedene
Graphalgorithmen zum Einsatz.
Da der Compilerbau ein Gebiet mit langer Tradition ist, ist die
Struktur von Compilern besonders gut erforscht und kann daher als
Muster für einen gut durchdachten Softwareentwurf dienen.
"Wer einen Compiler schreiben kann, kann jedes Programm schreiben."
In dieser Vorlesung werden wir die Programmiersprache Caml verwenden,
die ein Dialekt aus der ML-Familie ist. Caml hat große Ähnlichkeit mit
Haskell (Info 1), verwendet jedoch eine
Call-by-value-Auswertungssemantik und hat imperative Merkmale
(explizite Referenzen, auch Pointer genannt, und Exceptions).
- Die Programmiersprache Caml
- Die Aufgaben werden in OCaml
2.02, der
aktuellen Version der Programmiersprache Caml, programmiert. Das
"O" steht für Objective, aber wie in C++ kann man die
objektorientierten Erweiterungen ignorieren, was wir auch tun
werden.
- Das Caml Referenzhandbuch
(online,
postscript)
- Die Caml FAQ
- Es gibt ein Buch (in englisch) über funktionale Programmierung
in caml [4], das zum Semesteranfang in der
Universitätsbibliothek zur Verfügung stehen wird.
- Im WWW gibt es eine Einführung
in die funktionale Programmierung mit Caml von John Harrison.
- Studenten, die sich besonders für die Programmiersprache Caml
interessieren, sollten auch einen Blick auf den Caml
Hump werfen, der eine
Liste von Werkzeugen und Bibliotheken enthält, die für realistische
Programmentwicklung mit Caml gedacht sind.
- [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 2.02, Documentation and user's
manual.
INRIA, France, March 1999.
From http://pauillac.inria.fr/caml.
- [8]
-
Reinhard Wilhelm and Dieter Maurer.
Übersetzerbau -- Theorie, Konstruktion, Generierung -- 2
Auflage.
Lehrbuch. Springer-Verlag, Berlin, Heidelberg, 1996.
thiemann@informatik.uni-freiburg.de,
April 26, 2001