|
Grundlagen des Übersetzerbaus (PS-UE1)7.5 ECTS (englische Bezeichnung: Principles of Compiler Construction)
(Prüfungsordnungsmodul: Grundlagen des Übersetzerbaus)
Modulverantwortliche/r: Michael Philippsen Lehrende:
Michael Philippsen
Startsemester: |
WS 2021/2022 | Dauer: |
1 Semester | Turnus: |
jährlich (WS) |
Präsenzzeit: |
50 Std. | Eigenstudium: |
175 Std. | Sprache: |
Deutsch |
Lehrveranstaltungen:
Empfohlene Voraussetzungen:
Participants of this lecture are expected to have profound skills in the following programming languages:
Es wird empfohlen, folgende Module zu absolvieren, bevor dieses Modul belegt wird:
Systemprogrammierung (SS 2021)
Algorithmen und Datenstrukturen (WS 2020/2021)
Rechnerarchitektur (WS 2020/2021)
Inhalt:
[Deutsch:]
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. . [English:]
The lecture teaches concepts and techniques of compiler construction from a compiler developer view, following the structure of the compiler frontend, middle end, and backend. Exercise sessions and practical assignments complement the lecture; the students implement their own compiler (based on a framework) for the e2 programming language, which is designed for this series of compiler construction lectures. Content Summary
Principles of compiling imperative programming languages
Structure of a compiler
Scanner and parser
Abstract syntax trees (ASTs)
Visitor design pattern
AST transformations, desugaring
Symbol tables and scopes
Semantic analysis: name analysis, type checking
Compilation of arithmetic expressions and control flow structures to register-based and stack-based intermediate languages
Compilation of functions and function calls, activation records
Compilation of object-oriented languages with single inheritance, interfaces, and multiple inheritance
Method resolution in Java (overloaded and overridden methods)
Code generation with Sethi-Ullmann algorithm, Graham-Glanville algorithm, tree transformations, and dynamic programming
Register allocation with local techniques and graph coloring
Instruction scheduling with the list scheduling technique
Debuggers
. Lecture Topics
1. Introduction: Class overview, modular structure of compilers (front-, middle-, and backend), compilation bootstrapping
2. Lexer and Parser: Tokens, literals, symbol table, grammar classes (LR(k), LL(k), ...), concrete syntax tree, shift-reduce parser
3. ASTs and semantic analysis: Abstract syntax tree, visitor pattern, double dispatch, scopes, definition table
4. Type consistency: Type safety, type system, type checks, type inference, type conversions, attributed grammars
5. AST transformations: Transformation patterns (arithmetics), transformation of nested and generic classes
6. Intermediate representations: Types of IRs, arithmetic operations, assignments, multidimensional array access, structs, control flow instructions, short-circuit evaluation
7. Activation record and stack frame: Relative addresses, call by value/reference/name, nested functions, function pointers, stack pointer and frame pointer, function calls: prolog and epilog
8. Object-oriented languages: single inheritance: Symbol and type analysis, method selection with method overloading and overriding, virtual method calls, class descriptors, dynamic type checks and casts
9. Object-oriented languages II: interfaces, multiple inheritance: Interface v-tables, dynamic type checks and casts with interfaces, interfaces with default implementations and state, diamond problem, virtual inheritance
10. Basic code generation: Code selection, register allocation, instruction order, basic blocks, optimal code generation for expression trees
11. Optimized code selection: Code selection as tree transformation, Graham-Glanville code generators, dynamic programming
12. Optimized register allocation: Performance approximations, liveness analysis, collision and interference graph, register spilling, coloring heuristics, optimistic extension, live range splitting, register coalescing, data structures
13. Instruction level parallelism, instruction order, debugger: Data, structural, and control conflicts in CPU pipelines, list scheduling, delay slots, branch predictions, superscalar and VLIW architectures, ptrace, break- and watch-points, DWARF
. Assignment Milestones
For the assignments of this course, the students put the concepts and techniques presented in the lecture for implementing a compiler into practice. The goal of the assignments is to implement a functional compiler for the e2 programming language by the end of the semester. The e2 language is specifically designed for educational purposes; the students obtain a description of the language.
A framework for the implementation is provided to the students. The students implement the core components of the compiler in five milestones.
All milestones need to be fulfilled to pass the module; the last milestone contains two tasks. In particular, the milestones are:
Milestone 1: Grammar definition and construction of the AST: ANTLR productions, AST visitor interface, and generic AST visitor for array accesses and return and loop statements; AST visitor for AST visualization.
Milestone 2: Name analysis: symbol table; declaring standard functions; AST visitor for name analysis.
Milestone 3: Constant folding and type analysis: AST transformations for constant folding; AST visitor for bottom-up type analysis, adding AST nodes for implicit casts;
Milestone 4: AST translation to intermediate representation: AST visitor to generate IR; translation of arithmetic, return, and assign statements, logical expressions, conditions, loops.
Milestone 5.0: Memory assignment: definition and implementation of the ABI calling convention; memory assignment of variables; stack frame allocation; caller-save and callee-save registers.
Milestone 5.1: Code generation: implementation of the e2 standard library; IR visitor to generate assembly code.
For milestones one through three, the compiler needs to support both integer and floating-point arithmetic. For the last two milestones, only integer arithmetic is required.
Lernziele und Kompetenzen:
[Deutsch:]
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
[English:]
Students who have successfully completed the module will have the ability to
identify the components and data structures of a compiler
explain the concept of bootstrapping
describe the structure and operation of a lexer and show limitations and problem cases
use grammars for the construction of parsers
know the complexity of Java parsers
describe the main tasks of semantic analysis and apply them to different programming languages (especially Java)
outline typical AST transformations using the Java compiler as an example
illustrate the basic features of the Java Virtual Machine (JVM) and the corresponding transformation from source to byte code
analyze the differences between programming languages in terms of arrays and compound structures
explain the use of stack memory in program execution
know different machine instruction sets
optimize register allocation before generating machine code
apply the Graham-Glanville algorithm to generate machine code
recognize limitations of optimization in code generation and to analyze alternative strategies
describe the difference between static and dynamic scheduling
examine features of compiler construction for object-oriented languages
augment a given lexer and abstract syntax tree to support all language constructs in an example language
implement constant folding, symbol table construction, and type checking on the abstract syntax tree
generate intermediate code from the abstract syntax tree
map control structures to jumps
translate compound boolean expressions with shortcut evaluation
illustrate addressing of (multidimensional) arrays
design conventions for function calls and stack frame layout
calculate offsets for stack variables
implement a basic register allocation.
know details of different processor architectures
generate machine code for at least one processor architecture
implement a runtime library
apply debugging to machine code
Literatur:
- „Modern Compiler Implementation in Java“, A.W. Appel, Cambridge University Press, 1998
„Compilers - Principles, Techniques and Tools“, A. Aho, R. Sethi, J. Ullmann, Addison-Wesley, 2006
„Modern Compiler Design“, D. Grune, H. Bal, C. Jacobs, Langendoen, Wiley, 2002
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
- Informatik (Bachelor of Science)
(Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Gesamtkonto | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsrichtung Programmiersysteme | Grundlagen des Übersetzerbaus)
Dieses Modul ist daneben auch in den Studienfächern "123#67#H", "Informatik (Bachelor of Arts (2 Fächer))", "Informatik (Master of Science)", "Information and Communication Technology (Master of Science)", "Informations- und Kommunikationstechnik (Master of Science)", "Mathematik (Bachelor of Science)" verwendbar. Details
Studien-/Prüfungsleistungen:
Grundlagen des Übersetzerbaus (Prüfungsnummer: 42401)
(englischer Titel: Oral Examination on Foundations of Compiler Construction)
- Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet, 7.5 ECTS
- Anteil an der Berechnung der Modulnote: 100.0 %
- weitere Erläuterungen:
[Deutsch:]
Wichtige Hinweise:
Je nach Anzahl der Teilnehmer bzw. Verlängerung der Corona-Satzung findet die Modulprüfung entweder schriftlich (90 Min. Klausur) oder mündlich (30 Min.) statt. Die konkrete Prüfungsform wird zu Semesterbeginn bekannt gegeben.
Die Erfahrung zeigt, dass ein Bestehen der Modulprüfung ohne die erfolgreiche Bearbeitung der Übungsaufgaben in der Regel äußerst schwer fällt. Wir empfehlen daher eindringlich das Erreichen aller Meilensteine des Übungsbetriebes.
[English:]
Grading Policy:
Successful completion of all assignment milestones during the semester (5 milestones, each graded pass/fail) is required for the exam admission.
The module grade results from 100% of the evaluation of the final examination. The final examination is either oral (30 minutes) or written (90 minutes) based on the number of participants and infection prevention regulations.
- Prüfungssprache: Deutsch
- Erstablegung: WS 2021/2022, 1. Wdh.: SS 2022
1. Prüfer: | Michael Philippsen |
- Ort: am 22.4. in Raum 02.152-113 Vorstandszimmer Hochhaus
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|