UnivIS

Grundlagen des Übersetzerbaus

Dozent/in

Details

Zeit/Ort n.V.

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

  • Do 8:15-9:45, Raum H4 (außer vac) ICS

Inhalt

*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

Zusätzliche Informationen

www: https://www.studon.fau.de/crs4533479.html