Modul Übersetzerbau

Sommersemester 2023
Arbeitsgruppe Programmiersprachen und Übersetzerkonstruktion

Nr. Art Termine Raum Veranstalter
080132 V4 Mo 10:15 - 11:45 CAP 3 - HS. 1 Hanus
    Di 16:15 - 17:45 CAP 3 - HS. 1  
080135 Ü2 Do 10:15 - 11:45 CAP 3 - HS. 1 Hanus, Bunkenburg

Vorlesungsbeginn

Dienstag, 11.4.2023, 16:15 Uhr, CAP 3 - HS. 1

Zielgruppe

Studierende in den Bachelor- und Masterstudiengängen Informatik und Wirtschaftsinformatik sowie Studierende mit Nebenfach Informatik

Voraussetzungen

Grundstudium (1.-4. Semester) in Informatik, insbesondere Module Programmierung bzw. Einführung in die Informatik sowei und Fortgeschrittene bzw. Deklarative Programmierung (das Skript zu dieser Vorlesung ist hier innerhalb der CAU zugreifbar)

Inhalt

Die Übersetzung von Programmiersprachen ist eine wohldefinierte aber dennoch komplexe Aufgabe. Zur Beherrschung dieser Komplexität wurde eine Zerlegung in einzelne Übersetzungsaufgaben entwickelt (hierfür wurden übrigens Alfred Aho and Jeffrey Ullman mit dem ACM Turing Award 2020, dem "Nobelpreis der Informatik", ausgezeichnet), die heute in dieser oder ähnlicher Form in den meisten Übersetzern verwendet wird. In dieser Vorlesung werden die einzelnen Übersetzungsaufgaben und die bekannten Lösungsansätze dazu vorgestellt. Im Einzelnen werden behandelt:

  • Programmiersprachen, Interpreter, Übersetzer
  • Lexikalische Analyse
  • Syntaktische Analyse
  • Semantische Analyse
  • Codeerzeugung

Modulprüfung

Am Ende der Vorlesung findet eine mündliche Abschlussprüfung statt.

Ergänzende Materialien zur Vorlesung

Es gibt ein Skript zur Vorlesung (PDF-Format, nur innerhalb der CAU Kiel zugreifbar!), welches während des Semesters leicht überarbeitet wird. Dieses Skript ist kein Lehrbuch, aber es beinhaltet den ungefähren Vorlesungsverlauf. Daher sollte neben dem Lesen des Skripts auch immer die Vorlesung besucht werden, um über den aktuellen Stand informiert zu sein!

Folien und Programme:

11.4.2023: Einführungsfolien (PDF) Darstellung von Simple-Programmen in Haskell
17.4.2023: Relevanz der Sprachsemantik: Haskell-Beispiel Curry-Beispiel
25.4.2023: Recursive Descent Parser für eine einfach Anweisungssprache ...mit Parserkombinator
2.5.2023: Recursive Descent Parser für Ausdrücke
9.5.2023: Happy-Spezifikation eines Ausdrucksparsers
15.5.2023: Happy-Spezifikation eines Ausdrucksparsers mit Konflikten Happy-Spezifikation eines Ausdrucksparsers mit gelösten Konflikten Rekursiver Abstiegsparser für Binärzahlen mit Wertberechnung Happy-Spezifikation eines Binärzahlenparsers mit Wertberechnung Happy-Spezifikation eines Ausdrucksparsers mit Wertberechnung Rekursiver Abstiegsparser für Ausdrücke mit Wertberechnung Happy-Spezifikation eines Simple-Interpreters für Zuweisungen Happy-Spezifikation eines Simple-Interpreters mit print-Anweisungen
16.5.2023: RD-Parser mit Berechnung der Blockschachtelungstiefe Attributierte Grammatik für Blockschachtelungstiefe in Happy Happy-Spezifikation eines Simple-Parsers mit AST-Erzeugung
30.5.2023: Definition abstrakter Ausdrucksbäume als Zwischensprache
12.6.2023: Maximal-Munch-Algorithmus zur lokal optimalen Zielcodeauswahl

Übungen

In den begleitenden Übungen wird für praktische Programmieraufgaben die Sprache Haskell eingesetzt, für die es frei verfügbare Implementierungen für Unix- und Linux-Systeme gibt.

Literatur

  • A. Aho, M. Lam, R. R. Sethi, J.Ullman: Compiler - Prinzipien, Techniken und Werkzeuge (2. Auflage), Pearson Education, 2008
  • A. Aho, M. Lam, R. Sethi, J.Ullman: Compilers: principles, techniques, and tools (2nd ed.), Pearson Education, 2007
  • A. Appel: Modern compiler implementation in ML, Cambridge UP, 1997
  • R.H. Güting, M. Erwig: Übersetzerbau, Springer 1999
  • W. Waite, G. Goos: Compiler Construction, Springer, 1984
  • R. Wilhelm, D. Maurer: Übersetzerbau: Theorie, Konstruktion, Generierung, Springer, 1992
  • N. Wirth: Grundlagen und Techniken des Compilerbaus, Oldenbourg, 2008
Weitere Literatur wird in der Vorlesung bekanntgegeben.