Praktikum Compilerbau Wintersemester 2006/2007

Voraussetzungen

Betreuung

Prof. Dr. Peter Thiemann Dipl.-Inf. Stefan Wehr

Termine

Abschlusspräsentation: Die Abschlusspräsentation findet am 19.4.2007 um 14 Uhr im Raum 00-019 Geb. 079 statt. Die Teilnahme ist verpflichtend.

Vorbesprechung: Mittwoch, 25.10.2006, ca. 17:30 Uhr, SR 00-010/14 Geb. 101 (im Anschluss an die Compilerbauvorlesung)

Einführung in OCaml:

Montag, 30.10.2006, 16-18 Uhr, SR 00-010/14 Geb. 101 (zur regulären Vorlesungszeit)
Mittwoch, 8.11.2006, 14-16 Uhr, SR 00-019 Geb. 079

Anwesenheitszeit für das restliche Praktikum: Mittwoch, 11-13 Uhr und 14-16 Uhr, Poolraum 00-018 Geb. 079. In dieser Zeit sollen Probleme zusammen mit dem Betreuer gelöst und Lösung vorgestellt werden.

Aufgabenstellung (aktualisiert)

Ziel des Praktikums ist es, einen funktionsfähigen Übersetzer für eine Java-ähnliche Sprache mit Erweiterungen für sogenannte Typklassen zu implementieren. Als Implementierungssprache werden wir OCaml einsetzen. Zielsprache zur Codeerzeugung ist MIPS Assembler. Wir benutzen den SPIM Simulator zum Ausführen der MIPS Programme.

Ein Parser und Lexer für eine Teilmenge der zu übersetzenden Sprache ist bereits vorhanden. Zu Beginn des Praktikums sollen diese erweitert werden, um sich mit dem Parsergenerator ocamlyacc und dem Lexergenerator ocamllex (Link) vertraut zu machen.

Der Parser liefert einen AST, auf den dann der Typchecker und eine erste Transformation angewendet wird. Dabei wird nur ein kleiner Ausschnitt der Sprache unterstützt, so dass die Transformation und der Typchecker auch von den Studenten implementiert werden kann.

Aus dem Ergebnis der ersten Transformation soll dann, über eine weitere Zwischensprache, MIPS Assembler generiert werden. Dazu werden Algorithmen zur Instruktionsauswahl und zur Registerallokation benötigt. Am Ende sollen ausgewählte Optimierungen und/oder ein Garbage Collector implementiert werden.

Zeitplan (aktualisiert)

Wochenbeginn	Aufgabe
23.10.06	Einführung in OCaml
30.10.06	Einführung in OCaml
6.11.06	Einführung in OCaml / Lexing und Parsing
13.11.06	Lexing, Parsing
20.11.06	Lexing, Parsing
27.11.06	Semantische Analyse
4.12.06	Semantische Analyse
11.12.06	Transformation in Zwischensprache
18.12.06	Transformation in Zwischensprache
8.1.07	Instruktionsauswahl
15.1.07	Instruktionsauswahl
22.1.07	Registerallokation
29.1.07	Registerallokation
5.2.07	Optimierungen, GC
12.2.07	Optimierungen, GC

Material und Aufgaben

Einführung in OCaml (PDF, PDF 4 auf 1)
Einführung in OCaml, Teil 2 (PDF, PDF 4 auf 1)
Einführung in Waitomo (.PS,.PDF)
Der OCaml Kurs von Prof. Thiemann auf dem Sommercampus 2004 enthält weitere, sinnvolle Übungsaufgaben zu OCaml.
Aufgabenblatt 1 (.PS, .PDF)
Frontend des Waitomo Compilers
- 5.11.2006: Initialversion (.tar.gz).
- 13.11.2006: Bugfix, Zuweisungen an lokale Variablen werden jetzt geparst (.tar.gz).
- 14.11.2006: Bugfix, Desugarer kann mit this umgehen (.tar.gz). Achtung: Die Syntax für implementation Deklarationen hat sich geändert. Anstelle von
```
implementation<X_1,...,X_n> N_1,...,N_m of K where Q_1,...,Q_k {
    ...
}
```
  schreibt man jetzt
```
implementation<X_1,...,X_n> K [N_1,...,N_m] where Q_1,...,Q_k {
    ...
}
```
Aufgabenblatt 2 (.PS, .PDF)
- 6.12.2006: Subtyping für anyref verbessert
Mini-Java
- 23.11.2006: Initialversion (.tar.gz).
- 28.11.2006: Sichtbarkeitsmodifikatoren sind per Hand zu Mini-Java hinzuzufügen.
- 5.12.2006: Das Modul Mini_java_symtab enthält zwei neue Werte empty und empty_env (.tar.gz).
- 8.12.2006: Der Desugarer behandelt Zuweisungen an lokale Variablen nicht richtig. In der Funktion desugar_stmt muss daher der Fall für Stmt_assign_var durch folgenden Code ersetzt werden:
```
  | Ast.Stmt_assign_var (v, e) ->
      if Scoped_vars.elem v then
        let v' = Scoped_vars.lookup v in
        let e' = desugar_expr e in
          Dst.Stmt_assign_var (v', e')
      else
        let f = Id.mk_field (Id.string_from_var v) in
          desugar_stmt (Ast.Stmt_assign_field (Ast.Expr_var (Id.this), f, e))
```
Aufgabenblatt 3 (.PS, .PDF)
Interpreter für JIR: jir_eval.ml
Aufgabenblatt 4 (.PS, .PDF)
Instructions.ml

Material

Vorlesungsseite