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)
Inferenz-Systeme
- Motivation
- Definition
- Inferenz-Systeme (Beispiel 1)
- Inferenz-Systeme (Beispiel 2)
- Inferenz-Systeme (Beispiel 3)
- Inferenz von Werten
- Umgebungen (Spezifikation)
- Umgebungen (Implementierung)
- Aussagenlogische Resolution
- Resolution (Vollständigkeit)
- Semantische Bereiche
- Continuations
Unterprogramme
- Beispiele
- Interpreter mit Funktionen
- Semantik
- Testfall (1)
- Let und Lambda
- Mehrstellige Funktionen
- Closures
- Rekursion?
- Testfall (2)
Lambda-Kalkül
- Motivation
- Der Lambda-Kalkül
- Lambda-Terme
- verkürzte Notation
- Gebundene Variablen
- Substitution
- Das falsche Binden von Variablen
- Gebundene Umbenennungen
- Ableitungen
- Eigenschaften der Reduktion
- Daten als Funktionen
- Lambda-Kalkül als universelles Modell
- Fixpunkt-Kombinatoren
- Lambda-Berechenbarkeit
- Übung Lambda-Kalkül
Fixpunkte
- Motivation
- Existenz von Fixpunkten
- Beispiele f. Halbordnungen, CPOs
- Funktionen als CPO
- Funktionen als CPO, Beispiel
- Fixpunktberechnung im Interpreter
- Fixpunkte und Laziness
- Simultane Rekursion: letrec
- letrec nach rec
- Übung Fixpunkte
Zustand/Speicher
- Motivation
- Speicher
- Auswertung von Ausdrücken
- Änderung der Hilfsfunktionen
- Speicher-Aktionen als Monade
- Variablen?
- Imperative Programmierung
- Rekursion
- Rekursion (semantisch)
- Rekursion (operational)
- Speicher--Übung
Monaden
- Die Konstruktorklasse Monad
- Do-Notation für Monaden
- Beispiele für Monaden
- Die IO-Monade
- Die Maybe-Monade
- List als Monade
- Gesetze für Monaden
- Monaden: Zusammenfassung
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
- Namen
- Transformation f. Applikation
- Transformation f. Abstraktion
- Vereinfachungen
- Teilweise Auswertung
- Partial Evaluation
- Partial Evaluation (II)
- Vergleich CPS-Interpreter/Transformator
- Übung CPS-Transformation
Closure Conversion
- Motivation
- Spezifikation
- closure passing style
- Transformation
Lifting
- Spezifikation
- Realisierung
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
- Methoden
- Semantik
- Monaden zur Programmstrukturierung
- Prüfungsvorbereitung
Über dieses Dokument ...

Johannes Waldmann 2013-01-31