Compilerbau
Aktuelles
Inhalt
Compilerbau beschäftigt sich mit der Übersetzung von Programmen von einer Hochsprache in eine maschinennahe Sprache. Dieses Praktikum vermittelt die wichtigsten Techniken zur Konstruktion eines Übersetzers. Im Laufe des Praktikums wird ein Compiler von MiniJava in ausführbaren Maschinencode implementiert. mehr...
Organisation
Dozenten
Zeit und Ort
Veranstaltung | Zeit | Ort | Beginn |
---|---|---|---|
Praktikum | Mo, 14–18 Uhr | Raum L U117 (Takla Makan), Oettingenstr. 67 | 17.10.2011 |
Hörerkreis
- Zielgruppe sind Studierende folgender Studiengänge:
- Bachelor (Medien-)Informatik (Vertiefende Themen der Informatik)
- Master (Medien-)Informatik (Praktikum zu fortgeschrittenen Themen der Informatik)
- Diplom (Medien-)Informatik (Prüfungsbereich T)
Materialien
- Folien 17.10.2011
- Folien 24.10.2011
- Folien 07.11.2011
- Folien 14.11.2011
- Folien 21.11.2011
- Folien 28.11.2011
- Folien 05.12.2011
- Folien 12.12.2011
- Folien 09.01.2012
- Folien 16.01.2012
- Folien 23.01.2012
- Folien 30.01.2012
- MiniJava-Beispiele
- Intel 80x86 cheat sheet
- Cooper, Harvey, Kennedy — A Simple, Fast Dominance Algorithm
- Wilson — Uniprocessor Garbage Collections Techniques
Übung 1: Interpreter für Beispielsprache "Straightline"
Übung 2: Lexer und Parser für Straightline und MiniJava
- JFlex- und JavaCUP-Spezifikationen, Testprogramm und Beispielcode (ZIP)
- Straightline-Parser in Haskell (TGZ)
- Dokumentation zu den Tools
- MiniJava-Grammatik
Übung 3: Parser für Minijava
Übung 5: Übersetzung in Zwischencode
- Java-Klassen für die Syntax der Zwischensprache und Hilfsklassen für die Übersetzung (ZIP)
- Haskell-Datentyp für die Zwischensprache (ZIP)
Übung 6: Modellierung von Aktivierungssätzen (Frames)
- Interfaces für Frames und Backend; Klassen für Dummy-Machine; Übersetzer nach C (Java, ZIP)
- Interfaces für Frames und Backend; Klassen für Dummy-Machine; Übersetzer nach C (Haskell, ZIP)
- Laufzeitbibliothek (C)
Übung 7: Basisblöcke und Kanonisierung
- Klassen für Kanonisierung (7.12.) (Java, ZIP)
- Module für Kanonisierung (Haskell, ZIP)
Übung 8: Instruktionsauswahl
Tools
- JFlex (Dokumentation)
- JavaCUP (Dokumentation)
- Alex (Lexer Generator für Haskell)
- Happy (Parser Generator für Haskell)
- Scala IDE for Eclipse für
eclipse-ide-3.6
(Helios). Installation von Scala in Eclipse über Help/Install Software und dort die software site Scala 2.9.1 final verwenden.
Einführung
Compilerbau beschäftigt sich mit der Übersetzung von Programmen von einer (Hoch-)sprache in eine maschinennahe Sprache. Die dazu verwendeten Methoden, wie Parsing, syntaktische und semantische Analyse, finden in zahlreichen Gebieten der Informatik Anwendung. Das Praktikum bietet interessierten Studenten die Gelegenheit, sich grundlegende Techniken in diesem Gebiet anzueignen, sowie Kentnisse in verschiedenen Gebieten, von formalen Methoden bis maschinennaher Programmierung, zu vertiefen.
In diesem Kurs werden anhand der praktischen Implementierung eines Compilers für eine vereinfachte Version von Java, MiniJava, die wichtigsten Techniken zur Konstruktion eines Übersetzers vermittelt. Dies beinhaltet das Lesen und Analysieren des Eingabeprogramms, Optimierungen des Programms zur Effizienzsteigerung, sowie die Codegenerierung für moderne Prozessoren.
Für die Programmieraufgaben stehen mehrere Tools, wie ein Parsergenerator, zur Verfügung. Als Implementierungssprache kann Java, auf Wunsch aber auch andere Sprachen wie zum Beispiel SML, OCaml, Scala, Haskell, C/C++, ..., verwendet werden.
Themen
Das Praktikum folgt dem unten angegebenen Buch Modern Compiler Implementation in Java, welches wie folgt strukturiert ist:
- Grundlagen
- Einführung
- Lexikalische Analyse
- Parsing
- Abstrakte Syntax
- Semantische Analyse
- Activation records
- Zwischensprachen
- Basisblöcke
- Instruktionsauswahl
- Lebendigkeitsanalyse
- Registerallokierung
- Fortgeschrittene Themen (werden nur teilweise im Praktikum behandelt)
- Speicherverwaltung
- Objekt-orientierte Sprachen
- Funktionale Sprachen
- Polymorphe Typen
- Datenflussanalyse
- Schleifenoptimierungen
- SSA (Static single-assignment form)
- Pipelining and scheduling
- Speicherhierarchie
Literatur
- Andrew Appel: Modern Compiler Implementation in Java, 2nd edition, Cambridge University Press. ISBN-10: 052182060X.
- Torben Mogensen: Basics of Compiler Design (online kostenlos verfügbar)
Artikelaktionen