| Hauptseite |
| Zeitplan |
| Übungen |
| Software |
| Literatur |
Compilerbau
Zeitplan
Vorlesung 1: EinführungKapitel 1 des Lehrbuchs gibt einen Überblick der Struktur eines Compilers. Als Aufwärmübung wird eine einfache Sprache definiert, für die ein einfacher Interpreter zu schreiben ist. Material:Nach oben.Vorlesung 2: Lexikalische Analyse und LL(1)-ParsingDie lexikalische Analyse wandelt einen Strom von Eingabezeichen in einen Strom von Tokens um. Diese Tokens sind z.B. Schlüsselwörter, Klammern, oder Identifier. LL(1)-Parser fuer eine kontextfreie Grammatik in einer bestimmten Form konstruieren zu gegebener Eingabe eine Linksableitung. Hierbei muss die passende Produktion anhand der erwarteten linken Seite und dem naechsten Eingabesymbol getroffen werden. Ist solch eine Entscheidung nicht moeglich, so liegt keine LL(1) Grammatik vor. LL(1)-Parser koennen mit der Methode des rekursiven Abstiegs leicht von Hand implementiert werden. NB: Im Gegensatz zum Lehrbuch verwenden wir im Kurs jflex als Lexer-Generator, und später java-CUP als Paser-Generator (siehe software). Material:Nach oben.Vorlesung 3: LR(1)-Syntaxanalyse und ParsergeneratorenLR(1)-Parser muessen die Entscheidung, welche Produktion zu verwenden ist, erst treffen, wenn die gesamte rechte Seite einer Produktion bereits eingelesen ist. Hierzu verwenden sie einen Keller von Grammatiksymbolen, der der bisher gelesenen Eingabe entspricht. Mithilfe eines endlichen Automaten entscheiden sie, ob ein weiteres Symbol eingelesen wird (Shift) oder aber die obersten Kellersymbole mithilfe einer Produktion reduziert werden (Reduce). JavaCUP ist ein LR(1), genauer gesagt LALR(1)-Parsergenerator, den wir im Praktikum verwenden. NB: Im Gegensatz zum Lehrbuch verwenden wir im Kurs später java-CUP als Paser-Generator (siehe software und das benötigte java-CUP JAR file). Material:Nach oben.Vorlesung 4: Abstrakte SyntaxZur weiteren Verarbeitung wird ein Eingabeprogramm während des Parsens in eine Baumstruktur, einen abstrakten Syntaxbaum (AST) umgewandelt. Dazu werden Klassen als Knoten der Baumstruktur definiert, die den Nicht-Terminalsymbolen in der Grammatik entsprechen (siehe MJAbsSyn.java). Die Grammatik des Parsers ist so mit semantischen Aktionen zu erweitern, dass als Resultat des Parsens ein AST erzeugt wird. Anschliessend ist ein Pretty-printer zu implementieren, der den AST als MiniJava source code ausgibt. Dieser Pretty-printer ist am besten mittels Visitor pattern zu realisieren. Als Beispiel für die AST Generierung der StraightLine Sprache samt Pretty-printer liegt ein entsprechend erweiterter Parser vor. Material:
Vorlesung 5: Semantische Analyse: Type-checkingNach dem Aufbau eines AST werden bestimmte semantische Eigenschaften des Programms auf dieser Datenstruktur geprüft. Insbesondere wird jeder Variable im Programm ein Typ zugeordnet. Alle Operationen werden dahingehend geprüft, ob sie auf Variablen oder Werte vom richtigen Type angewendet werden. In dieser Übung ist ein Typ-checker für Mini-Java zu implementieren, der Typkorrektheit von arithmetischen und boolschen Operationen, Array und Objekt-zugriff, sowie von Methoden-instanzierung überprüft. Dazu ist zuerst mittels Visitor pattern eine Symboltabelle für alle vorkommenden Variablen und Methoden anzulegen. Diese Tabelle kann dann vom Typ-checker, ebenfalls einem Visitor, verwendet werden. Nach oben.Vorlesung 6: Activation recordsZur Behandlung von Methodenaufrufen wird üblicherweise die stack-orientierte Datenstruktur von "activation records" oder auch "frames" verwendet. In dieser Struktur werden alle Daten gespeichert, die zum Ausführen einer (möglicherweise rekursiven) Methode notwendig sind. Die Verwaltung von Activation Records muss sich daher mit der Parameterübergabe sowie der Entscheidung ob Variablen register- oder speicher-allokiert sind befassen. Da derartige Entscheidungen stark von der Maschinenarchitektur abhängig sind, wird in dieser Vorlesung auf grundlegende Konzepte der Speicherverwaltung eingegangen. Im Rahmen des Mini-Java Compilers ist die Routine newFrame zu implementieren, die einen neuen Activation Record erzeugt, und Listen für die Zugriffsmethoden auf formale sowie konkrete Argumente verwaltet. Als Zugriffsmethoden ist die Klasse Frame.Access mit Subklassen InReg (für register-allokierte Variablen) und InFrame (für speicher-allokierte Variablen) zu erweitern. Dazu können folgende Hilfsfunktionen verwendet werden:
Nach oben. Vorlesung 7: ZwischensprachenDie Besprechung von Zwischensprachen in der Compilierung wir vertieft. Insbesondere wird auf die Zwischensprache eingegangen, die im praktischen Teil für den Mini-Java Compiler verwendet werden soll. Grundprinzipien in der Übersetzung von Mini-Java in diese Zwischensprache werden besprochen. Der Mini-Java Compiler ist mit einer Übersetzung in die vorgestellte Zwischensprache zu erweitern. Dazu können folgende files verwendet werden: Nach oben.Vorlesung 8: BasisblöckeZur weiteren Verarbeitung eines Programms in der Zwischensprache, wird dieses in eine Sequenz von Blöcke, sogenannte "Basisblöcke", aufgespalten. Jeder Basisblock hat nur einen Einsprungpunkt, nälich den textuellen Beginn des Blocks, und nur einen Aussprungpunkt, das Ende des Blocks. Damit bietet sich ein Basisblock als kleinste Einheit zur Berechnung des Kontrollflusses durch ein Programm an. Im MiniJava Compiler werden zunächst Vereinfachungen auf dem Baum der Zwischensprache durchgeführt, die diesen in eine Liste umwandeln. Danach werden Sequenzen von Basisblöcken, sogennante "Traces" ermittelt. Die Blöcke in diesen Traces werden so umgeordnet dass u.a. der else-Zweig eines bedingten Sprunges immer nach dem kommt. Als Ergebnis erhält man für jeden Rumpf einer Methodendefinition eine Sequenz von Statements. Der Code für die in der Vorlesung besprochenen Transformationen ist hier verfügbar, und muss nur noch in den eigenen Compiler eingebunden werden. Um das Testen des MiniJava Compilers zu erleichtern, steht auch ein Interpreter für die Zwischensprache zur Verfügung.
Nach oben. Vorlesung 9: Speicherverwaltung (Garbage Collection)Moderne Programmiersprachen wie Java entlasten den Programmierer von der Aufgabe allokierten Speicherplatz wieder explizit freizugeben. Stattdessen prüft das Laufzeitsystem bei einer Allokierung ob noch genug Speicherplatz verfügbar ist und, falls dies nicht der Fall ist, leitet es eine Speicherbereinigung ("Garbage Collection") ein. Dabei werden beginnend von bekanntermassen notwendigen Daten, wie den Daten am Stack, alle Datenstrukturen weiter verfolgt und gesichert. Die restlichen Daten, die somit nicht mehr benötigt werden, werden freigegeben. In dieser Vorlesung werden die Grundprinzipien der Garbage Collection, sowie die Grundzüge der wichtigsten Mechanismen zur Implementierung vorgestellt. Aktuelle Version des muHwI Interpreter. Bspsprge:
Im praktischen Teil dieser Vorlesung, ist eine Programmtransformation zu implementieren, die den eingelesenen abstrakten Syntaxbaum in einen Weihnachtsbaum umwandelt. Frohe Weihnachten vom Compilerbau Team! Nach oben.Vorlesung 10: InstruktionsauswahlUm den Zwischencode in Assemblercode zu übersetzen, müssen Sequencen von Zwischencode auf Assemblerbefehle abgebildet werden. Das geschieht indem eine Überlagerung ("Tiling") des Zwischencodebaums durch Assemblerbefehle berechnet wird. In der Vorlesung wird das Prinzip eines solchen Tilings erläutert. Im praktischen Teil ist der vorgestellte "maximal munch" Algorithmus zu implementieren. Nach oben.Vorlesung 11: Aktivitätsanalyse (liveness analysis)Ziel der Aktivitätsanalyse ist es festzustellen, ob eine gegebene Variable an einem bestimmten Programmpunkt aktiv ist, d.h. später im Programm noch verwendet werden könnte. Für diese Analyse wird zunächst ein Kontrollflussgraph erzeugt, und über diesen werden dann Datenflussgleichungen gelöst. Mit dieser Information kann ein Interferenzgraph berechnet werden, der für je 2 Temporaries angibt, ob sich ihre Aktivitätsbereiche überlappen und sie daher nicht in das selbe Register abgebildet werden können. Diese Information wird für die Registerallokierung benötigt. Im praktischen Teil sind die Routinen zur Übersetzung in einen Kontrollflussgraphen (Klasse AssemFlowGraph), sowie die Aktivitätsanalyse (Klasse Liveness) zu implementieren. Als Ressourcen können die Routinen von der MiniJava Page verwendet werden. Nach oben.Vorlesung 12: Funktionale SprachenFunktionale Sprachen verwenden moderne Konzepte wie Funktionen höherer Ordnung ("higher-order functions") sowie Bedarfsauswertung ("lazy evaluation"). In dieser Vorlesung werden wir die Implementierung dieser Konzepte, sowie die Modelle zur Implementierung funktionaler Sprachen im allgemeinen besprechen. Nach oben.Vorlesung 13: Registerverteilung (register allocation)Die Registerverteilung ordnet den bis zu diesem Zeitpunkt in der Kompilierung verwendeten abstrakten Registern konkrete Register zu. Dabei wird auf die Information der Aktivitätsanalyse, in der Form eines Interferenzgraphen, zurückgegriffen. Die Registerallokierung erfolgt mittels "graph-colouring": im Interferenzgraphen werden die Knoten so eingefärbt, dass keine 2 benachbarten Knoten dieselbe Farbe haben. Dabei entsprechen die Farben Registern der Maschine und die Nachbarschaftsbeziehung im Graphen der Information, dass 2 abstrakte Register nicht auf dasselbe konkrete Register abgebildet werden dürfen. In der Vorlesung werden die Registerverteilung mittels Graphenfaerbung sowie einige Verfeinerungen zum Basisalgorithmus vorgestellt. Im praktischen Teil ist diese Registerverteilung zu implementieren, so dass für jede Method gültiger Assembler Code erzeugt wird (einschliesslich Parameterübergabe und Rettung von Registern). Nach oben.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
