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 anhand einer Implementierung eines Compilers von MiniJava in ausführbaren Maschinencode. mehr...

Organisation

Dozenten

• Dr. Ulrich Schöpp
• Robert Grabowski
• Prof. Martin Hofmann

Zeit und Ort

Hörerkreis und Scheinerwerb

Teilnehmer

• Studierende der Informatik im Hauptstudium
• Bachelorstudenten im 5. Semester können das Praktium als Modul P17, Vertiefende Themen der Informatik belegen.

Vorkenntnisse

Grundkenntnisse Informatik, insbesondere in Java

Schein

gilt für Diplomprüfung im Haupt- oder Nebenfach Informatik

Prüfungsbereich

PG, T

Scheinerwerb

Mündliche oder schriftliche Prüfung am Ende des Semesters mit Zulassungsvoraussetzung. Die Zulassungsvoraussetzung wird abhängig von der Hörerzahl zu einem späteren Zeitpunkt festgelegt und mitgeteilt werden.

Materialien

• Vorlesungsfolien - Stand: 10.02.2010 (PDF)
• MiniJava-Beispielprogramme zum Testen - Stand: 18.11.2009 (ZIP)
• Carl Offner — Notes on Graph Algorithms Used in Optimizing Compilers
• Division.mj - manuelle MiniJava-Implementierung der Ganzzahl-Division - Stand: 17.02.2010

Übung 1: Interpreter für Beispielsprache "Straightline"

• Klassen für Syntax, Pretty Printer und Testprogramm (ZIP)

Übung 2: Lexer und Parser für Beispielsprache "Straightline"

• JFlex- und JavaCUP-Spezifikationen, Testprogramm und Beispielcode (ZIP)
• Dokumentation zu den Tools
• MiniJava-Grammatik

Übung 3: Parser für MiniJava

• Klassen für die abstrakte Syntax von MiniJava (ZIP)

Übung 5: Übersetzung in Zwischensprache

Übung 6: Aktivierungssätze (Frames)

Übung 7: Basisblöcke

Tools

• JFlex (Dokumentation)
• JavaCUP (Dokumentation)

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. Die Implementierungssprache ist Java (auf Wunsch können aber auch andere Sprachen wie zum Beispiel OCaml verwendet werden).

Themen

Das Praktikum folgt dem unten angegebenen Buch Modern Compiler Implementation in Java, welches wie folgt strukturiert ist:

• Grundlagen
  1. Einführung
  2. Lexikalische Analyse
  3. Parsing
  4. Abstrakte Syntax
  5. Semantische Analyse
  6. Activation records
  7. Zwischensprachen
  8. Basisblöcke
  9. Instruktionsauswahl
  10. Lebendigkeitsanalyse
  11. Registerallokierung
• Fortgeschrittene Themen (werden nur teilweise im Praktikum behandelt)
  
  1. Speicherverwaltung
  2. Objekt-orientierte Sprachen
  3. Funktionale Sprachen
  4. Polymorphe Typen
  5. Datenflussanalyse
  6. Schleifenoptimierungen
  7. SSA (Static single-assignment form)
  8. Pipelining and scheduling
  9. Speicherhierarchie

Literatur

• Andrew Appel: Modern Compiler Implementation in Java, 2nd edition, Cambridge University Press. ISBN-10: 052182060X.