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 Link zu einer externen Seite Modulbeschreibung.

Regelmäßige Termine

Die Vorlesung findet beginnend am Freitag, 10.04.2015 statt:

dienstags 11:30 - 13:00 Uhr (21.04. VG1C 0.01 ab 28.04. HG 0.16) und
freitags 9:15-10:45 (HG 0.19)
.

Die Übung findet beginnend am Mittwoch, 15.04.2015 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 Link zu einer externen Seite 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 (plus Beispielcode)
  • 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
  • Vorgaben
    • Parserkombinatoren
    • Parserkombinatoren und AST
    • Aus der Übung vom 8. Juli 2015
    • 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 22. April 2015
2Blatt 222. und 29. April 2015 
3Blatt 313. Mai 2015
4Blatt 420. Mai 2015
5Blatt 527. Mai 2015
6Blatt 63. Juni 2015
7Blatt 717. Juni 2015
8Blatt 824. Juni 2015
9Blatt 91. Juli 2015
10Blatt 108. Juli 2015
11Blatt 1115. Juli 2015

Material aus den Übungen:

Übung vom 15. April 2015

  • Einführung in Haskell (txt) (html)
  • Hallo Welt! (hallo.hs)
  • Hallo Du! (greeter.hs)
  • Funktionen und Datentypen (uebung.hs)

 Übung vom 22. April 2015

  • Notizen zur Lösung des Übungsblattes (txt) (html)

 Übung vom 20. Mai 2015

  • Regular Expressions (Regs.hs)

 

Kontakt

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