Nächste Seite:
Überblick
Compilerbau
Vorlesung, Wintersemester 2005
Johannes Waldmann, HTWK Leipzig
Überblick
Was ist ein Compiler?
Compiler zum Textsatz
Empfohlene Literatur/Links
Organisation
Leistungsnachweise
(Konkrete) Maschinen
abstrakte Maschinen
Bedeutung abstrakter Maschinen
Sprachen und Übersetzer
Arbeitsweise eines Übersetzers
Vorteile eines Compilers
Compilerbau heute?
DSL (domain specific languages)
Beispiel für DSL
Typische Probleme beim Sprach-Entwurf
Wadlers ,,Gesetz``
Compiler kennenlernen
Kellermaschinen
Lexikalische Analyse
Daten-Repräsentation im Compiler
Token-Typen
Reguläre Ausdrücke/Sprachen
Beispiele/Aufgaben zu regulären Ausdrücken
Endliche Automaten
Rechnungen und Sprachen von Automaten
Anwendung von Automaten in Compilern
Automaten mit Epsilon-Übergängen
Automaten-Synthese
Automaten-Synthese (II)
Reduzierte Automaten
Deterministische Automaten
Potenzmengen-Konstruktion
Minimierung von det. Aut. (I)
Minimierung von det. Aut. (II)
Nicht reguläre Sprachen
Endliche Automaten als Scanner
Automaten als Scanner (II)
Komprimierte Automatentabellen
Scanner mit Flex (I)
Scanner mit Flex (II)
Übung Scanner-Generator flex
Übung zu flex
flex benutzen
Make-Regeln für flex
Den flex-Scanner analysieren
Scanner für Java
Syntaktische Analyse (21. 12.)
Wort-Ersetzungs-Systeme
Grammatiken
Eingeschränkte Grammatiken
Die Chomsky-Hierarchie
Kontextfreie Sprachen
Ableitungsbäume für CF-Sprachen
Ableitungsbäume (II)
Eindeutigkeit
Normalformen von CFG
Erreichbare und produktive Variablen
Reduzierte Grammatiken
Nullierbare Variablen
Epsilon-freie Grammatiken
Kettenregeln
Kreise und kreisfreie Grammatiken
Chomsky-Normalform
Greibach-Normalform
Aufgaben zu Grammatiken
Dangling else
Arithmetische Ausdrücke
Implementierungen von Parsern
Überblick
Rekursiver Abstieg
Rekursiver Abstieg/gnat/Übung
Rekursiver Abstieg (III)
Links-Faktorisierung
Links-Rekursion
Links-Rekursion (II)
Keller-Automaten
Keller-Automaten
Keller-Automaten (II)
Beispiel autotool/Kellerautomaten
Sprachen von Keller-Automaten
Keller-Automaten-Sprachen und CFG
Rechts/Links-Ableitungen
Rechts/Links-Ableitungen und Parser
Shift und Reduce
Top-Down/Bottom-Up und Eindeutigkeit
Vorlesung 24. 11.
Dangling Else
Operatoren
Syntaxbäume
Syntaktische Analyse mit SableCC
SableCC
Eine SableCC-Eingabe
Annotierte Grammatiken
Durchlaufen von Syntaxbäumen
Aufruf eines SableCC-Parsers
Attribut-Grammatiken
CST zu AST
Übung SableCC
Quiz-Aufgabe
Semantik
Interpretation
Funktionen
Randbemerkung: Anonyme Klassen in Java
Typen
Typ-Prüfung als abstrakte Interpretation
Aufgabe zu Interpretation/Typprüfung
Bemerkung zu Auswertungsstrategien
Lazy Evaluation (Beispiel)
Typen
Typen
Nutzen der statischen Typprüfung
wenn man Zahlen und Wahrheitswerte verwechselt
Trick Question
wenn man nur einen Typ (int) kennt
Typ-Prüfung bei Funktions-Aufrufen
Statische Typen sind streng
Methoden-Aufrufe
Überladen von Bezeichnern
Überladen/Überschreiben
Generische Polymorphie
Typprüfung für generische Funktionen
Aufgabe zu generischen Typen
Eingeschränkte generische Polymorphie
Funktionen als Argumente und Resultate
Änderungen von Typen
Übungen zu versteckten Typänderungen
Warum gibt es zu schwache Typsysteme?
Diskussion
Kompilation für Keller-Maschinen
Befehlssatz
PostScript
Forth
Die Java-VM
Übersetzung von Ausdrücken
Übersetzung von Anweisungen
Übersetzung von Zuweisungen
Adressen und Werte
Übersetzen von Verzweigungen
Übersetzen von Schleifen
Stacktiefe
Übungsaufgaben
Unterprogramme
Definition
Beispiele für Unterprogramme (Funktionen)
Parameter-Übergabe (Semantik)
Parameter-Übergabe (Implementierungen)
Parameterübergabe
Call-by-name
Aufgaben zu Parameter-Modi
Frames
Frames (II)
Unterprogramme bei x86
Frame-Optimierungen
Register
Register-Windows
Unterprogramme auf Sparc
Gesamt-Analyse
Seminar Unterprogramme
End-Aufrufe (tail calls)
End-Aufrufe (Beispiel)
End-Rekursionen (tail recursion)
Transformationen für Tail-Calls
Geschachtelte Unterprogramme
Blockstruktur und Orthogonalität
Einschränkungen der Orthogonalität
Lokale Unterprogramme: Beispiel
Lokale Unterprogramme: Implementierung
Statische Ketten: Beispiel
Statische und Dynamische Ketten
Seminar 11. 11.: Statische Ketten
Beispiel Statische/Dynamische Kette
Unterprogramme als Daten
Orthogonalität (II)
Funktionen als Argumente
Zeiger auf Nested Functions
Closures
Funktionen als Resultate?
Funktionen als Resultate (II)
Funktionales Programmieren in Java?
Beispiel: Collections, Komparatoren
Beispiel: Ereignisbehandlung
Funktionales Programmieren in Java (II)
Innere Klassen
Lokale Klassen
Java funktional?
Code-Generierung und -Optimierung
Compiler-Phasen
Zwischencode-Generierung
Common Subexpression Elimination -- CSE
Constant Propagation
Constant Folding, Strength Reduction
<
Code-Transformationen
Einfacher Matrix-Zugriff
Constant folding
strength reduction
Rückgabe
Stack-Frames
Schleifen, Code-Verschiebung
Arithmetische Umformungen
Mehr Schleifen
Daten-Fluß-Analyse
Datenfluß (II)
Linearisieren
Registervergabe
Register-Interferenz-Graph
Register-Graphen-Färbung (Heuristik)
Seminar: Registervergabe
Peephole-Optimierung, Instruction Selection
Einzelheiten zu gcc
Ergänzungen, Zusammenfassung
Compiler oder Interpreter?
Compiler
und
Interpreter
Cross-Compilation
Bootstrapping zur Selbst-Optimierung
Super-Compilation
Geschichte des Compilerbaus
Geschichte des Compilerbaus (II)
Mathematische Methoden
Compilerbau: Zweck der Lehrveranstaltung
Domainspezifische Sprachen
Domainspezifische Sprachen
Intercal (1972)
Intercal (Ablaufsteuerung)
Intercal
Brainfuck -- Beispiel
Brainfuck
Brainfuck
Autotool-Highscore-Auswertung
Ausblick: Erweiterte Sternhöhe
Über dieses Dokument ...
Johannes Waldmann 2006-02-02