Grundlagen des Übersetzerbaus (UE1)

Grunddaten

Voraussetzung zur Teilnahme an der Modulprüfung ist die erfolgreiche Bearbeitung der Übungsaufgaben.

Parallelgruppen / Termine

*Motivation:*

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.

.

*Fokus der Lehrveranstaltung:*

Es werden Konzepte und Techniken der Übersetzerkonstruktion aus Sicht
eines Übersetzerbauers und entlang der wesentlichen Arbeitsschritte
eines Übersetzers (Frontend; Mittelschicht; Backend)
vorgestellt. Übungen und Praxisaufgaben ergänzen die Vorlesung. Hier
entwickeln die Studierenden auf der Basis eines vorgegebenen
Programmrahmens einen eigenen Übersetzer für die Programmiersprache
e2, die speziell für den Übersetzerbau-Vorlesungszyklus entworfen
wurde.

*Behandelte Themenfelder:*

- Prinzipien der Übersetzung imperativer Programmiersprachen
- Struktur eines Übersetzers
- Symbolentschlüssler (Scanner) und Zerteiler (Parser)
- Abstrakter Syntaxbaum (AST)
- Besuchermuster
- AST-Transformationen, Entzuckerung
- Symboltabellen und Sichtbarkeitsbereiche
- Semantische Analyse: Namensanalyse, Typprüfung
- Übersetzung von arithmetischen Ausdrücken und Kontrollflusskonstrukten in registerbasierte oder stapelbasierte Zwischensprachen
- Übersetzung von Methoden und Methodenaufrufen; Methodenschachteln
- Übersetzung objektorientierter Sprachen mit Einfachvererbung, Schnittstellen und Mehrfachvererbung
- Methodenauswahl in Java (überladene und überschriebene Methoden)
- Code-Generierung nach Sethi-Ullmann, Graham-Glanville, per Baumtransformation sowie mit Hilfe dynamischer Programmierung
- Registerallokation mit lokalen Techniken und mit Graphfärbung
- Instruktionsanordnung mit "list scheduling"
- Debugger

.

*Themen der Vorlesungseinheiten:*

1. Einführung (Überblick, modulare Struktur von Übersetzern, Frontend,
Mittelschicht, Backend), Bootstrapping)

2. Symbolentschlüssler (Lexer) und Zerteiler (Parser), (Token,
Literale, Symboltabelle, Grammatikklassen (LK(k), LL(k), ...),
konkreter Syntaxbaum, Shift-Reduce-Parser)

3. AST und semantische Analyse (abstrakter Syntaxbaum, Besuchermuster,
Double Dispatch, Sichtbarkeitsbereiche, Definitionstabelle)

4. Typkonsistenz (Typsicherheit, Typsystem, Typüberprüfung,
Typberechnung, Typkonvertierung, attributierte Grammatiken)

5. AST-Transformationen (Transformationsschablonen für Ausdrücke,
Transformation innerer und generischer Klassen)

6. Transformation in Zwischensprache (registerbasiert versus
stapelbasiert, Übersetzung von arithmetischen Ausdrücken, Zuweisungen,
mehrdimensionalen Feldern, struct-Datentypen und
Kontrollflussstrukturen (einschließlich Kurzschlussauswertung))

7. Methodenschachteln und Kellerrahmen (relative Adressen, call by
value/reference/name, geschachtelte Funktionen, Funktionszeiger,
Stack- und Framepointer, Funktionsaufruf, Prolog, Epilog)

8. Objektorientierte Sprachen I: Einfachvererbung (Symbol- und
Typanalyse, Methodenauswahl mit Überschreiben und Überladen, virtuelle
Methodenaufrufe, Klassendeskriptoren, dynamische Typprüfung und
-wandlung)

9. Objektorientierte Sprachen II: Schnittstellen und Mehrfachvererbung
(Interface v-Tables, dynamische Typprüfung und -wandlung mit
Interfaces, Interfaces mit Default-Implementierung, Diamantenproblem)

10. Einfache Code-Erzeugung (Code-Selektion nach Sethi-Ullman,
Register-Allokation, Instruktionsreihenfolge, optimale Code-Erzeugung
für Ausdrucksbäume)

11. Fortgeschrittene Code-Erzeugung (Baumtransformation,
Graham-Glanville, dynamisches Programmieren)

12. Registerallokation (Leistungsabschätzung, Lebendigkeitsintervalle,
Kollisions- und Interferenzgraph, Spilling, Färbungsheuristiken,
Aufteilung von Lebendigkeitsintervallen, 2nd Chance Bin Packing,
Registerverschmelzung)

13. Parallelismus auf Instruktionsebene, Instruktionsreihenfolge,
Debugger (Konflikte im Instruktionsfließband, List Scheduling,
Delay-Slots, Sprungzielvorhersage, ptrace, Unterbrechungs- und
Beobachtungspunkte, DWARF)

*Meilensteine der Übungsbetriebs:*

Im Rahmen der Übungen (separater UnivIS-Eintrag) werden die in der
Vorlesung vorgestellten Konzepte und Techniken zur Implementierung
eines Übersetzers in die Praxis umgesetzt. Ziel der Übungen ist es,
bis zum Ende des Semesters einen funktionsfähigen Übersetzer für die
Beispiel-Programmiersprache e2 zu implementieren. Ein Rahmenprogramm
ist gegeben, das in fünf Meilensteinen um selbstentwickelte
Schlüsselkomponenten zu erweitern ist.

Folgende Meilensteine sind zu erreichen:

Meilenstein 1: Grammatik, AST-Konstruktion: Antlr-Produktionen,
AST-Besucherschnittschelle, generischer AST-Besucher für return und
Schleifen, AST-Besucher zur Visualisierung.

Meilenstein 2: Symbolanalyse, Symboltabelle, Standardfunktionen,
AST-Besucher für die Symbolanalyse.

Meilenstein 3: Konstantenfaltung per AST-Transformation, Typanalyse
mit bottom-up AST-Besuch, der implizite Typwandlungen bei Bedarf
ergänzt.

Meilenstein 4: AST-Besucher zur Erzeugung der
Zwischensprachrepräsentation, Übersetzung von arithmetischen
Ausdrücken, return, Zuweisungen, logischen Ausdrücken, Bedingungen und
Schleifen.

Meilenstein 5.0: Speicherzuteilung: Festlegung und Umsetzung der ABI
Aufrufkonvention, Zuweisung von Speicheradressen zu Variablen;
Kellerrahmenallokation; caller-save und callee-save Register.

Meilenstein 5.1: Code-Erzeugung: Implementierung der e2
Standardbibliothek; IR-Besucher zur Erzeugung von Assembly-Code.

Für die Meilensteine 1-3 soll der Übersetzer sowohl Integer- als auch
Gleitkomma-Arithmetik unterstützen. Für die nachfolgenden Meilensteine
reicht Integer-Arithmetik.

Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt: https://www.studon.fau.de/crs4533479.html

Zeitpunkt	Startdatum - Enddatum	Ausfalltermin	Durchführende/-r	Bemerkung	Raum
wöchentlich Do, 08:15 - 09:45	19.10.2023 - 08.02.2024	28.12.2023 04.01.2024	Prof. Dr. Michael Philippsen		11301.00.005