Grundlagen des Übersetzerbaus (PS-UE1)7.5 ECTS
(englische Bezeichnung: Principles of Compiler Construction)
(Prüfungsordnungsmodul: Vertiefungsrichtung Programmiersysteme)

Lehrveranstaltungen:

• • Grundlagen des Übersetzerbaus
    (Vorlesung, 2 SWS, Michael Philippsen, Fr, 10:15 - 11:45, H4; Vorlesung wird im WS2018/19 NICHT angeboten!)
  • Übungen zu Grundlagen des Übersetzerbaus
    (Übung, 2 SWS, Patrick Kreutzer et al.)

Inhalt:

Auf den ersten Blick erscheint es wenig sinnvoll, sich mit Übersetzerbau zu beschäftigen. Andere Themen scheinen wesentlich näher an der direkten Anwendbarkeit in der industriellen Praxis. Der erste Blick täuscht:

• Übersetzer gehören wohl zu den am gründlichsten studierten mittelgroßen sequentiellen Software-Systemen. Man kann viel aus den Erfahrungen lernen, die im Laufe der Jahre gesammelt wurden.

• In den Übungen, die die Vorlesung begleiten, werden Sie selbst einen (kleinen) Übersetzer entwickeln.

• Für viele Teilnehmer wird dieses Projekt das erste größere Software-Projekt sein. Viele der Algorithmen aus dem Grundstudium werden angewendet.

• Bei jedem von Ihnen verwendeten Übersetzer gehen Sie in der Regel davon aus, dass richtiger Coder erzeugt wird. In der Vorlesung erfahren Sie, wie das geforderte hohe Maß an Korrektheit und Zuverlässigkeit erreicht wird.

• Sie erlangen ein Verständnis für Konzepte von Programmiersprachen und verstehen, welcher Maschinen-Code aus Sprachkonstrukten gemacht wird. Mit diesem Wissen im Hinterkopf verbessern Sie Ihre Fähigkeit, gute und effiziente Programme zu schreiben.

• Übersetzer werden nicht nur für Programmiersprachen benötigt. Spezielle Übersetzer braucht man in vielen Bereichen des täglichen Informatik-Lebens z.B. zur Textformatierung, für Programmtransformationen, für aspektorientiertes Programmieren, für die Verarbeitung von XML, ...

• Es gehört zu einer Ingenieur-Ausbildung, in der Lage zu sein, diejenigen Werkzeuge selbst zu fertigen, die man verwendet. Für Informatiker gehört daher ein Verständnis vom Innenleben eines Übersetzers zum Rüstzeug.
  

Themen der Vorlesung:

• Übersetzungsprinzipien für imperative Sprachen

• Struktur eines Übersetzers

• Symbolentschlüssler und Zerteiler (Scanner und Parser)

• Abstrakter Syntaxbaum

• Symboltabellen, Umgebungen

• Attributgrammatiken

• Semantische Analyse, Typprüfung

• Automatische Speicherbereinigung

• Code-Erzeugung

• Register Optimization
  

Themen der Übung:

• In den Tafelübungen werden die in der Vorlesung vorgestellten Themen anhand von Übungsaufgaben angewendet und vertieft.

• Zusätzlich implementieren die Studierenden in Zweiergruppen einen eigenen Übersetzer für eine Beispielprogrammiersprache. Ziel ist es, am Ende einen funktionsfähigen Übersetzer zu haben. Dazu wird ein Grundgerüst eines Übersetzers für den Einstieg vorgegeben.

Lernziele und Kompetenzen:

Die Studierenden

• nennen die typischen Aufgaben und Datenstrukturen eines Übersetzers

• erläutern das Konzept des Bootstrapping

• beschreiben Struktur und Arbeitsweise eines Abtasters (Scanner) und zeigen Grenzen und Problemfälle auf

• wenden Grammatiken zur Konstruktion von Zerteilern (Parser) an

• kennen die Komplexität eines Zerteilers für Java

• beschreiben die wichtigsten Aufgaben der semantischen Analyse und wenden diese am Beispiel verschiedener Programmiersprachen (insbesondere Java) an

• skizzieren typische AST-Transformationen am Beispiel des Java-Übersetzers

• veranschaulichen die Grundzüge der Java-Kellermaschine und die zugehörige Transformation von Quell- zu Byte-Code

• analysieren die Unterschiede zwischen Programmiersprachen hinsichtlich Felder und Verbund-Strukturen

• erläutern die Verwendung von Stapel- und Kellerspeicher bei der Programmausführung

• kennen verschiedene Maschineninstruktionssätze

• optimieren die Registerverwendung vor der Generierung von Maschinencode

• wenden das Verfahren von Graham & Glanville zur Erzeugung von Maschinencode an

• erkennen Grenzen der Optimierung bei der Code-Generierung und analysieren alternative Strategien

• beschreiben den Unterschied zwischen statischer und dynamischer Ablaufplanung

• untersuchen Besonderheiten des Übersetzerbaus für objekt-orientierte Sprachen

• ergänzen einen vorgegebenen Abtaster und abstrakten Syntaxbaum, um alle Sprachkonstrukte einer Beispielsprache zu unterstützen

• implementieren Konstantenfaltung, den Aufbau der Symboltabelle und Typprüfung auf dem abstrakten Syntaxbaum

• erzeugen Zwischencode aus dem abstrakten Syntaxbaum

• bilden Kontrollstrukturen auf Sprünge ab

• veranschaulichen die Adressierung von (mehrdimensionalen) Feldern

• entwickeln Konventionen für Funktionsaufrufe und den Aufbau des Stacks

• berechnen Offsets fuer Variablen auf dem Stack.

• implementieren eine einfache Registervergabe.

• kennen Details verschiedener Prozessorarchitekturen

• generieren Maschinencode für mindestens eine Prozessorarchitektur

• implementieren eine Laufzeitbibliothek

• wenden Debugging für maschinennahen Code an

Literatur:

• „Modern Compiler Implementation in Java“, A.W. Appel, Cambridge University Press, 1998

• „Drachenbuch“, A. Aho, R. Sethi, J. Ullmann: Compilers - Principles, Techniques and Tools, Addison-Wesley, 2006

• „Modern Compiler Design“, Grune, Bal, Jacobs, Langendoen, Wiley, 2002

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Informatik (Bachelor of Science)
   (Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsrichtung Programmiersysteme)

Studien-/Prüfungsleistungen:

Grundlagen des Übersetzerbaus (Prüfungsnummer: 42401)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet

Anteil an der Berechnung der Modulnote: 100.0 %

weitere Erläuterungen:
Die Note ergibt sich aus einer 30minütigen mündlichen Prüfung. Voraussetzung zur Teilnahme an der mündl. Prüfung ist die erfolgreiche Bearbeitung der Übungsaufgaben.

Erstablegung: WS 2017/2018, 1. Wdh.: SS 2018

1. Prüfer:

Michael Philippsen