Grundlagen des Übersetzerbaus (UE1)

Vorlesung

Sie finden weitere Informationen auch in Campo bzw. StudOn.

Titel Grundlagen des Übersetzerbaus
Kurztext inf2-ueb
Turnus des Angebots nur im Wintersemester
Semesterwochenstunden 2

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

*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

1. Parallelgruppe

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

Übungen

Sie finden weitere Informationen auch in Campo.

Eine Studon-Anmeldung zu den Übungen ist nicht erforderlich. Melden Sie sich in Studon bitte lediglich zur Vorlesung an.

Titel Übungen zu Grundlagen des Übersetzerbaus
Kurztext inf2-ueb-ex
Turnus des Angebots nur im Wintersemester
Semesterwochenstunden 2

Im Rahmen der Übungen 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.

Die hierfür nötigen zusätzlichen Kenntnisse (z.B. Grundlagen des Assemblers für x86-64) werden in den Tafelübungen vermittelt.

Die im Laufe des Semesters zu erreichenden Meilensteine sind im UnivIS-Eintrag der Vorlesung aufgelistet.

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

1. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
wöchentlich Mo, 14:15 - 15:45 16.10.2023 - 05.02.2024 01.01.2024
25.12.2023
  • Florian Mayer
11302.02.133

Im Rahmen der Übungen 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.

Die hierfür nötigen zusätzlichen Kenntnisse (z.B. Grundlagen des Assemblers für x86-64) werden in den Tafelübungen vermittelt.

Die im Laufe des Semesters zu erreichenden Meilensteine sind im UnivIS-Eintrag der Vorlesung aufgelistet.

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

2. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
wöchentlich Fr, 08:15 - 09:45 20.10.2023 - 09.02.2024 29.12.2023
05.01.2024
  • Sascha Hofmann
11302.02.133

Im Rahmen der Übungen 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.

Die hierfür nötigen zusätzlichen Kenntnisse (z.B. Grundlagen des Assemblers für x86-64) werden in den Tafelübungen vermittelt.

Die im Laufe des Semesters zu erreichenden Meilensteine sind im UnivIS-Eintrag der Vorlesung aufgelistet.

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

3. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
wöchentlich Fr, 10:15 - 11:45 20.10.2023 - 09.02.2024 29.12.2023
05.01.2024
  • Tobias Heineken
11302.02.133