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

Title:

Foundations of Compiler Construction

Credits: 7,5

Prerequisites

Participants of this lecture are expected to have profound skills in the following programming languages:

• Java (assignments are implemented in Java)

• Assembler
  

It is recommended to complete the following modules before taking this module:

• Algorithms and Data Structures

• Computer Architecture

• Systems Programming

Contents

Motivation:

At first glance, it may appear less important to focus on compiler construction. Other areas seem to be much more applicable to current tasks in industrial practice. But appearences are deceptive:

• Compilers are among the most thoroughly studied middle-sized sequential software systems. Hence, there is a lot to learn from the experience made in the past.

• In the exercises that accompany this lecture, you will construct your own (small) compiler.

• For many participants, this project will be their first bigger software project.

• Normally, you expect every compiler you use to generate correct code. In the lecture, you will learn how one can achieve the required degree of correctness and reliability.

• You will gain an understanding of the concepts of programming languages and of how high-level language features are translated into machine code. Keeping this knowledge at the back of your mind, you will improve your capability to write good and efficient programs.

• Compilers are used not only for programming languages. Special compilers are needed in many areas of every-day life in computer science, e.g. for text formatting, program transformations, aspect oriented programming, XML processing etc.

• Every engineer should be able to build the tools he/she is using. For computer scienctists, this requires an in-depth understanding of the guts of compilers.

.

Main Focus of this Lecture:

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.

Topics covered in the lecture:

• 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.

Literature

• "Modern Compiler Implementation in Java", A. Appel, Cambridge University Press, 1998

• "Compilers - Principles, Techniques and Tools", A. Aho, M. Lam, R. Sethi, J. Ullmann, Addison-Wesley, 2006

• "Modern Compiler Design", D. Grune, H. Bal, C. Jacobs, K. Langendoen, Wiley, 2002

UE ([präsenz]):Übungen zu Grundlagen des Übersetzerbaus

Dozentinnen/Dozenten: Tobias Heineken, M. Sc., Florian Mayer, M. Sc.
www: https://www.studon.fau.de/crs4533479.html