Praktikum: Compilerbau

Diplomstudiengang Informatik, Masterstudiengang Software Systems Engineering
(Praktische Informatik, Vertiefungsfach)

Inhalt

In diesem Praktikum soll ein Compiler und eine Virtuelle Maschine für die nebenläufige und nicht-deterministische Modellierungssprache PROMELA erweitert werden um Komponenten wie:

• Daten-/Kontrollfluß framework
• Bytecode Optimierungen
• Type Checker
• Erweiterungen der VM (z.B. um Timer)

PROMELA wurde unter anderem bei der NASA zur Modellierung und Software-Verifikation in diversen neueren Missionen erfolgreich eingesetzt.

HiWis

• Michael Rohrbach (Compiler Frontend)
• Gustavo Quirós (Bytecode-Generierung)
• Frank Birbacher (VM sowie Fragen zu C)

Termine

19.10.2005, 14:00h, Raum 4201b

Vorbesprechung (Folien)

20.2.2006, 14:00h, Raum 5055

Abschlußpräsentation

Voraussetzung

• Vordiplom im Fach Informatik
• Vorlesung Compilerbau oder PaCo, evtl. auch Model Checking Vorlesungen
• Gute Kenntnisse einer gängigen höheren Programmiersprache
  (Java, C/C++, C#, Haskell, O'Caml, Scheme, Common-Lisp, etc.)

Mailing-Listen

• cbp2005 (Diskussionen, Koordination, Ankündigungen, etc.)
• cbp2005-devel (CVS commit logs)

Teilnehmer

Aufgaben

[C]: Compiler
[VM]: Virtuelle Maschine

1. Compilergenerierung aus XSD-Beschreibung [C]
2. Integration des Compilers und Bytecode-Assemblers [C]
3. Optimierte Übersetzung von safety-Eigenschaften [C,VM]
4. Implementierung eines PROMELA Type Checkers [C]
5. Implementierung eines multi-threaded VM-Schedulers zur Ausnutzung von SMP-Hardware [VM]
6. Implementierung eines alternativen Exception handling Konzepts [C]
7. Extraktion des Kontrollflußgraphen durch Simulation in der VM [C,VM]
8. Deklarative Beschreibung eines Maschinenmodells zur VM-Generierung [C,VM]
9. Analyse zur Wertebereichsbeschränkung von Variablen [C,VM]
10. Einsatz von Theorembeweisern zur Verifikation [Funktionale Prog.]
11. Exaktes Tracing von Code locations im Übersetzungsprozeß [C] (evtl. VM)
12. Erweiterung des VM-Modells um Uhren [VM,C]
13. Erweiterung des VM-Modells um eine Heap-Komponente [VM,C]
14. Ein Compiler für NTIF [C]
15. Ein Compiler für Value-Passing CCS [C]
16. Speicheroptimierung des VM-Schedulers durch Zustandskompression [VM]
17. Speicheroptimierung des VM-Schedulers durch Partial Order Reduction [VM]
18. Speicheroptimierung des VM-Schedulers durch Symmetry Reduction [C,VM]
19. Escape Analyse für PROMELA [C]

Die detaillierten Spezifikationen des PROMELA Compilers und/oder der Virtuellen Maschine werden bei allen Aufgaben benötigt.

CVS

• Hinweise zur Benutzung des CVS am I2

Links

• VMSSG, a Virtual Machine for State Space Generation
• Abstract Syntax Definition Language
• CVS
  • CVS
  • WinCVS GUI
  • CVS Book
  • CVS Best Practice
• Unix-Umgebungen für Windows
  • Cygwin
  • MinGW

Literatur

• Appel: Modern Compiler Implementation (Bibliothek)
• J.R.Levine et al.: lex & yacc. O'Reilly, 1992.

Zuordnung

• Praktische Informatik
• Informatik Vertiefung

Ansprechpartner

Michael Weber, Stefan Rieger Volker Stolz