Compilerbau

Zeitplan

Vorlesung 1: Einführung

Kapitel 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:

• Klassen für Syntax
• Beispielsprogramm

Vorlesung 2: Lexikalische Analyse und LR(1)-Parsing

Die lexikalische Analyse wandelt einen Strom von Eingabezeichen in einen Strom von Tokens um. Diese Tokens sind z.B. Schlüsselwörter, Klammern, oder Identifier.

LR(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 jflex als Lexer-Generator, und java-CUP als Parser-Generator (siehe software).

Vorlesung 3: Abstrakte Syntax

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

Nach oben.

Vorlesung 4: Semantische Analyse: Type-checking

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

Vorlesung 5: Activation records

Zur 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:

• package Temp zur Verwaltung von temporären Namen und Labels.
• package Frame, das das abstrakte Interface zu den Activation Records darstellt; als Name kann entweder die Klasse Symbol.Symbol (für effizienteren Vergleich) oder String verwendet werden.

Vorlesung 6: Zwischensprachen

Die 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:

• Abstrakte Syntax der Zwischensprache
• Visitor interface
• Pretty printer für Zwischensprache

Vorlesung 7: Basisblöcke

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

• Code: Transformationen auf der Zwischensprache

Vorlesung 8: 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.

Vorlesung 9: Instruktionsauswahl

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

Frohe Weihnachten vom Compilerbau Team!

Vorlesung 10: 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.

Vorlesung 11: 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).

Vorlesung 12: Funktionale Sprachen

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

Hans-Wolfgang Loidl Last modified: Thu Jan 31 15:58:20 2008 Stardate: [-29]8898.11