Compilerbau
Vorlesung
Wintersemester 2008, 09, 10, 11

Johannes Waldmann, HTWK Leipzig

Einleitung
- .
- Beispiel
- Inhalt
- Sprachverarbeitung
- Compiler und andere Werkzeuge
- Phasen eines Compilers
- Methoden und Modelle
- Anwendungen von Techniken des Compilerbaus
- Literatur
- Organisation
- Beispiel: Interpreter (I)
- Beispiel: Interpreter (II)
- Übung (Haskell)
- Übung (Interpreter)
- Umgebungen
Inferenz-Systeme
- Motivation
- Definition
- Inferenz-Systeme (Beispiel 1)
- Inferenz-Systeme (Beispiel 2)
- Inferenz-Systeme (Beispiel 3)
- Inferenz von Werten
- Umgebungen
- Aussagenlogische Resolution
- Resolution (Eigenschaften)
- Semantische Bereiche
- Continuations
Unterprogramme
- Beispiele
- Interpreter mit Funktionen
- Semantik
- Testfall (1)
- Closures
- Der Lambda-Kalkül
- Small-Step-Semantik des Lambda-Kalküls
- Mehrstellige Funktionen
- Let und Lambda
- Rekursion?
- Testfall (2)
Fixpunkte
- Motivation
- Rekursion
- Existenz von Fixpunkten
- Funktionen als CPO
- Funktionen als CPO, Beispiel
Rechnen im Lambda-Kalkül
- Daten als Funktionen
- Lambda-Kalkül als universelles Modell
- Fixpunkt-Kombinatoren
- Lambda-Berechenbarkeit
- Übung Fixpunkte
- letrec
- letrec nach rec
Zustand/Speicher
- Motivation
- Speicher
- Auswertung von Ausdrücken
- Änderung der Hilfsfunktionen
- Speicher-Aktionen als Monade
- Rekursion
- Rekursion (operational)
- Rekursion (semantisch)
- Speicher--Übung
Monaden
- Die Konstruktorklasse Monad
- Do-Notation für Monaden
- Die Zustands-Monade
- List als Monade
Kombinator-Parser
- Datentyp für Parser
- Elementare Parser (I)
- Monadisches Verketten von Parsern
- Elementare Parser (II)
- Kombinatoren für Parser (I)
- Kombinator-Parser und Grammatiken
- Robuste Parser-Bibliotheken
- Asymmetrische Komposition
- Nichtdeterminismus einschränken
- Fehlermeldungen
- Pretty-Printing (I)
- Pretty-Printing (II)
Ablaufsteuerung/Continuations
- Definition
- Motivation
- CPS für Linearisierung
- CPS für Resultat-Tupel
- CPS/Tupel-Beispiel
- CPS für Ablaufsteuerung
- Semantik für CPS
- Semantik
- CPS als Monade
- Übung CPS
Typen
- Grundlagen
- Inferenzsystem für Typen (Syntax)
- Inferenzsystem für Typen (Semantik)
- Inferenz für Let
- Applikation und Abstraktion
- Eigenschaften des Typsystems
Polymorphe Typen
- Motivation
- Typ-Argumente (Beispiel)
- Typ-Argumente (Regeln)
- Inferenz allgemeingültige Formeln
- Typen und Daten
Typ-Rekonstruktion
- Motivation
- Realisierung mit Constraints
- Inferenzregeln f. Rekonstruktion (Plan)
- Inferenzregeln f. Rekonstrukion
- Substitutionen (Definition)
- Substitutionen: Produkt
- Substitutionen: Ordnung
- Unifikation--Definition
- Unifikation--Algorithmus
- Unifikation--Komplexität
- Rekonstruktion polymorpher Typen
- Implementierung
Plan für Compiler
- Transformationen/Ziel
CPS-Transformation
- CPS-Transformation: Spezifikation
- CPS-Transformation: Zielsyntax
- Beispiel
- Transformation f. Applikation
- Transformation f. Abstraktion
- Namen
- Vereinfachungen
- Teilweise Auswertung
- Partial Evaluation
- Partial Evaluation (II)
- Erklärung CPS-Transformation
- Übung CPS-Transformation
Closure Conversion
- Motivation
- Spezifikation
- closure passing style
- Transformation
Lifting
- Spezifikation
- Realisierung
Kombinatorische Logik
- Motivation
- Beispiele
- Systematische Übersetzung
- Kombinator-Basen
- Anwendungen
Registervergabe
- Motivation
- Plan (I)
- Plan (II)
- Registerbenutzung
Automatische Speicherverwaltung
- Motivation
- Mark/Sweep
- Pointer Reversal (Invariante)
- Pointer Reversal (Ablauf)
- Eigenschaften Mark/Sweep
- Stop-and-copy (Plan)
- Stop-and-copy (Invariante)
- Stop-and-copy (Ablauf)
- Stop-and-copy (Eigenschaften)
- Breiten- und Tiefensuche
- Speicher mit Generationen
- Speicherverwaltung in JVM
- Speicherverwaltung in JVM (II)
Zusammenfassung
- Semantik
- Monaden zur Programmstrukturierung
- Parser
Anhang
- Prüfungsvorbereitung
Über dieses Dokument ...

Johannes Waldmann 2012-01-30