Praktikum Compilerbau

Aktuelles

• Die Abnahmen finden am Di, den 23.7. im Raum L109 statt.
• Bitte melden Sie sich bei UniWorX für das Praktikum an.

Inhalt

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 Praktikum wird ein Compiler für MiniJava, eine vereinfachte Version von Java, entwickelt. Damit werden 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 wahlweise Java, OCaml oder Haskell (für weitere Vorschläge sind wir durchaus offen).

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 

Organisation

Dozenten

• Dr. Andreas Abel
• Dr. Ulrich Schöpp

Zeit und Ort

Hörerkreis

Zielgruppe sind Studierende folgender Studiengänge:

• Master (Medien-)Informatik (Praktikum zu fortgeschrittenen Themen der Informatik)
• Diplom (Medien-)Informatik (Prüfungsbereich T)
• Bachelor (Medien-)Informatik (Vertiefende Themen der Informatik)

Materialien

• Vorlesungsfolien (Stand: 15.7.)
• MiniJava-Beispielprogramme
• Weiteres Beispielprogramm: Mandelbrot.zip
• Wilson — Uniprocessor Garbage Collections Techniques

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

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

Übung 2: Lexer und Parser für Straightline und MiniJava

• Lexer und Parser für Straightline-Programme in Java, OCaml und SML (ZIP)
• MiniJava-Grammatik (als txt)
• Operator-Präzedenzen in Java

Übung 3: Parser für Minijava

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

Ü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)
• Interfaces für Frames und Backend (OCaml), Übersetzer von Tree nach C zum Testen des Frontends (ZIP)
• Laufzeitbibliothek (C 32bit), C 64bit

Übung 8: Instruktionsauswahl

• Klassen für die Repräsentierung einiger x86-Assemblerinstruktionen (Java, ZIP)
• Intel 80x86 cheat sheet
• Simulator für x86-Assembler mit beliebig vielen Registern (TAR.GZ, letzte Änderung: 25.6.2013) (geschrieben von Andreas Abel)
  Auch als Haskell-Cabal-Paket auf Hackage

Tools

• JFlex (Dokumentation)
• JavaCUP (Dokumentation)
• ocamllex, ocamlyacc
• ML-ULex, ML-Yacc

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)