Compilerbau

Die Studierenden erlernen Prinzipien des Compilerbaus und der Programmiersprachen. Sie lernen den Aufbau eines Compilers und die Phasen der Compilierung kennen. Sie werden befähigt, einfache Compiler selbst zu entwickeln und erwerben praktische Kenntnisse und Fähigkeiten im Umgang mit Programmiersprachen, -systemen und zugehörigen Werkzeugen.

siehe auch Modulbeschreibung.

Prüfungstermin

Dienstag, d. 13.09.2016, 8.00-10.00 Uhr: ZHG/HS B 

Regelmäßige Termine

Die Vorlesung findet beginnend am Freitag, 8.4.2016 statt:

dienstags 9:15 - 10:45 Uhr  (HG 0.19) und
freitags 9:15-10:45 (HG 0.19)
.

Die Übung findet beginnend am Mittwoch, 13.4.2016 statt:

mittwochs 13:45 - 15:15 Uhr (HG 0.20).

Anforderungen

Zum Bestehen des Moduls sind zwei Prüfungsteilleistungen zu erbringen:

  • erfolgreiche Teilnahme am Praxisteil
  • erfolgreiche Teilnahme an einem Prüfungsgespräch

Im Praxisteil wird in Praktikumsgruppen von jeweils 2 bis 3 Teilnehmern ein Compiler entwickelt.

Es gibt auch theoretische Übungsaufgaben sowie Übungsaufgaben zur Programmierung in Haskell, deren Bearbeitung freiwillig ist, aber dringend empfohlen wird. Man kann Lösungen zu diesen Aufgaben vom Übungsleiter korrigieren lassen.

Einschreibung

Neben der Anmeldung zum Modul ist eine Einschreibung, inklusive Zuordnung zu einer Praktikumsgruppe, erforderlich.

Vorlesung

Im Verlauf des Semesters werden hier die aktuellen Vorlesungsmaterialien veröffentlicht:

  • 0 Organisatorisches
  • 1 Sprachen und Compiler
  • Einführung in Haskell
  • 2 Syntax
    • Konzepte und Formalismen
    • Scanner
    • Parsierung (Teil I, Teil II, Teil III)
  • 3 Semantik und semantische Analyse
    • Typklassen
    • Typisierung
    • Namen und Namensanalyse
    • Syntaxgesteuerte Übersetzung / Attributierte Grammatiken
  • 4 Interpretation
    • Grundkonzepte, Lambda-Kalkül
    • Interpretationsfunktionen
    • SECD-Maschine
    • Graphreduktion
  • 5 Codeerzeugung
  • 6 Speichermodell
  • 7 Garbage Collection

Praxisteil

Programmierumgebung

Im Praxisteil wird die Programmiersprache Haskell verwendet. Für die Programmierung sollte die Haskell Platform benutzt werden, welche u.a. den Glasgow Haskell Compiler inklusive der interaktiven Umgebung GHCi, das Haskell-Paketverwaltungstool cabal-install und eine Reihe von Basisbibliotheken enthält.

Aufgabenstellung

  • Aufgaben
    • Aufgabe 1
    • Aufgabe 2
    • Aufgabe 3
    • Aufgabe 4
    • Aufgabe 5
    • Aufgabe 6
    • Aufgabe 7
  • Vorgaben
    • Parserkombinatoren
    • Parserkombinatoren und AST
    • Parserkombinatoren, AST und Parser
  • Dokumentation µOpal
  • Dokumentation µOM
  • Beispielprogramme
  • Dokumentation für Beispielprogramme

Automatischer Test

Die eigene Implementierung der Parserkombinator-Bibliothek aus Aufgabe 1 kann man mittels der Haskell-Bibliothek QuickCheck und der im Modul Test.Parser enthaltenen Testbench testen. Dazu lädt man das Modul Test.Parser in GHCi (ghci Test/Parser.hs) und gibt Folgendes ein:

quickCheck prop_ParserRunIsCorrect

Dadurch wird die Implementierung mit 100 Testfällen getestet. Will man z.B. 10000 Testfälle, kann man folgendes eingeben:

quickCheckWith (stdArgs { maxSuccess = 10000 }) prop_ParserRunIsCorrect

Ein Testfall besteht aus einem Parser, einer Eingabe und einem erwarteten Ergebnis. Liefert der Parser für die Eingabe nicht das erwartete Ergebnis, zeigt QuickCheck den Testfall in folgender Form an:

run parser input == result

Die Angabe rechts von den Gleichheitszeichen stellt die erwartete Ausgabe dar. Um zu ermitteln, was der Parser tatsächlich liefert, gibt man den Ausdruck links von den Gleichheitszeichen in GHCi ein.

Es werden sowohl Testfälle generiert, bei denen das Parsen erfolgreich ist, als auch solche, bei denen es scheitert. Im Falle des Scheiterns wird nicht verlangt, dass der Parser eine bestimmte Fehlermeldung liefert. Nur die Fehlerposition wird abgeprüft. Der Testfall enthält daher keine Fehlermeldung. In der textuellen Darstellung des Testfalls sieht man statt einer Fehlermeldung einen Unterstrich.

Freiwilliger Übungsteil 

AufgabenBesprechungVorgaben
1Blatt 1 
2Blatt 2 
3Blatt 3  
4Blatt 4  
5Blatt 5
6Blatt 6
7Blatt 7
8Blatt 8
9Blatt 9
10Blatt 10

Material aus den Übungen:

... folgt hier

Kontakt

Mit Fragen und Anregungen wenden Sie sich bitte an Petra Hofstedt oder Peter Sauer.