|
Grundlagen des Übersetzerbaus (PS-UE1)7.5 ECTS (englische Bezeichnung: Principles of Compiler Construction)
(Prüfungsordnungsmodul: Vertiefungsmodul Programmiersysteme)
Modulverantwortliche/r: Michael Philippsen Lehrende:
Michael Philippsen
Startsemester: |
WS 2014/2015 | Dauer: |
1 Semester | Turnus: |
jährlich (WS) |
Präsenzzeit: |
50 Std. | Eigenstudium: |
175 Std. | Sprache: |
Deutsch |
Lehrveranstaltungen:
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:
- Informatik (Bachelor of Science)
(Po-Vers. 2009w | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsmodul Programmiersysteme)
Dieses Modul ist daneben auch in den Studienfächern "Computational Engineering (Rechnergestütztes Ingenieurwesen) (Master of Science)", "Informatik (Master of Science)", "Informations- und Kommunikationstechnik (Master of Science)" verwendbar. Details
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 %
- Erstablegung: WS 2014/2015, 1. Wdh.: SS 2015
1. Prüfer: | Michael Philippsen |
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|