Sehr geehrter Nutzer, sehr geehrte Nutzerin,
wir haben unseren Auftritt mit Techniken wie CSS barrierearm gestaltet. Leider unterstützt Ihr Browser diese Webstandards nicht komplett oder die Verwendung von Stylesheets ist ausgeschaltet.

Zur Navigation - Metanavigation überspringen |
Zum Inhalt - Navigation überspringen


Zusatznavigation

English Logo Leibniz Universität Hannover Kontakt Sitemap
Programmiersprachen und Übersetzer

PSUE  > Lehre > WiSe 2018/19 > Compilerkonstruktion > Materialien

Materialien zur Laborübung Compilerkonstruktion

Grundlage dieses Labors war der im Anhang A des Buchs von Aho, Lam, Sethi und Ullman aufgeführte Beispielcompiler. Allerdings wurde die Sprachdefinition erweitert und der Gesamtaufbau des Compilers neu konzipiert. Die Aufgaben der semantischen Analyse, der Array-Transformation und der Code-Erzeugung wurde jeweils in einen Tree-Walker verlagert, der den vom Parser gelieferten Syntaxbaum durchläuft und entsprechende Aktionen ausführt. Es wird ausserdem expliziter Drei-Adress Code erzeugt, so dass in späten Phasen des Compilers Code-Optimierungen vorgenommen werden können.

Die Beispiel-Programmiersprache

Die Erweiterung der Beispielsprache gegenüber dem Original umfasst:
  • eine Kommentarkonvention im Stil von C oder Java
  • eine Erweiterung der Syntax des Deklarationsteils, um nach einer Typebezeichnung eine Liste von Identifiern aufführen zu können
  • eine for-Anweisung im Stil von C und die Möglichkeit, ein leeres Statement zu definieren.

Zwei Beispielprogramme mit der Übersetzung in Drei-Adress Code finden sie hier.

Hier finden Sie auch die modifizierte Grammatik und die entsprechend geänderten Syntaxgraphen, die für die Konstruktion eines recursive-descent Parsers benötigt werden.

Die lexikale Analyse

Die für diese Phase des Compilers notwendigen Dateien finden sie im Paket "lexer". Die wichtigsten Dateien sind:

  • Tag.java - enthält die Kodierung aller Token-Klassen als Enumeration
  • Token.java - definiert die Token-Klasse und liefert Daten für die Initialisierung des Scanners
  • Num.jav, Real.java - definieren die beiden numerischen Tokenklassen
  • Word.java, Type.java und Array.java - definieren die restlichen Tokenklassen
  • Lexer.java - der eigentliche lexikale Scanner

Die syntaktische Analyse und der Aufbau des Syntaxbaums

Die notwendigen Dateinen sind in den Paketen "parser" und "intern" zu finden.

Das Paket "parser" enthält nur die Implementation eines recursive-descent Parsers für die Beispielsprache. Der Parser erzeugt parallel zum Parsingprozess einen Syntaxbaum für das Eingabeprogramm. Bei Feststellung eines syntaktischen Fehlers in der Eingabe wird eine kurze Fehlermeldung ausgegeben.

Die Dateien im Paket "intern" definieren die Klassen der möglichen Knoten des Syntaxbaums. Eine grobe Übersicht über die Klassen und die Vererbungshierarchie findet man hier.

Die Treewalker

Die größte Änderung gegenüber dem im Buch von Aho et al. beschriebenen Compiler besteht in der Verwendung von dezidierten TreeWalkern für die folgenden Phasen des Compilers. Diese Konstruktion erlaubt eine bessere Trennung der einzelnen Phasen voneinander und eine maximale Unabhängigkeit von den vorangehenden Phasen. Die notwendigen Dateien befinden sich im Paket "treewalker". Die Dateien sind:

  • TreeWalker.java - eine generische abstrakte Klasse
  • LinTreeWalker.java - realisiert einen Treewalker, der den Syntaxbaum top-down durchläuft und eine linearisierte Ausgabe des Syntaxbaums erzeugt. Für jeden Knoten des Syntaxbaums wird eine Ausgabezeile erzeugt, wobei die Tiefe des Knotens im Syntaxbum durch eine Einrückung vor der Knoteninformation dargestellt wird.
  • LinTreeWalkerTyp.java - realisiert einen TreeWalker, der zusätzlich die Typ-Information für jeden Knoten ausgibt.
  • SemanticWalker.java - definiert einen TreeWalker, der eine semantische Analyse für den Syntaxbaum durchführt und gegebenenfalls eine automatische Typanpassung durch Einfügen neuer Operationsknoten im Syntaxbaum durchführt.
  • TransformWalker.java - realisiert einen Treewalker, der Arrayzugriffe, insbesonder bei mehrdimensionalen Arrays, transformiert. Dazu wird der Syntaxbaum gegebenenfalls so erweitert, dass Feldzugriffe in die einfache Form Startadresse[Offset] verwandelt werden.
  • CodeGenWalker.java - realisiert die Übersetzung des Syntaxbaums in eine Folge von Drei-Adress Befehlen. Die möglichen Drei-Adress Befehle werden mit den Dateien im Paket "code" definiert. Es enthält die Dateien:
    • DreiAdrCode.java - abstrakte Wurzelklasse
    • JumpCode.java - abstrakte Klasse, definiert Sprungbefehle
    • BedJumpCodeId.java, BedJumpCodeRel.java und UnbJumpCode.java - defineiren drei Klassen von Sprungbefehlen
    • ArithCode.java - abstrakte Klasse, definiert einfache arithmetische Drei-Adress Befehle
    • Arith2OPCode.java, Arith1OPCode.java und AssignCode.java - definieren drei Klassen von arithmetischen Drei-Adress Befehlen
    • ArrayCode.java - abstrakte Klasse, defniert Befehle mit Array-Zugriff
    • ArrayAssignCode.java und ArrayRefCode.java - definieren zwei Klassen von Drei-Adress Befehlen mit Array-Zugriff.

Das Hauptprogramm

Das Hauptprogramm befindet sich im Paket "main". Dort befinden sich die Dateien:

  • Main.java - Das Hauptprogramm. Hier wird in einer ersten Phase der Name einer Datei abgefragt, die das zu übersetzende Programm enthält. Nach Einlesen der Datei wird ein lexikaler Scanner erzeugt, der danach in einer Instanz eines Parsers benutzt wird, um die Eingabe zu parsen und einen Syntacxbaum zu erstellen. Anschließend laufen die Treewalker auf den so erzeugten Syntaxbaum und erzeugen letztlich die Übersetzung in Drei-Adress Code.
  • Env.java - Definition der Symboltabelle, dargestellt als verkettet Folge von Hash-Tabellen.
  • Labels.java - Hilfsklasse für die Übersetzung Boolescher Ausdrücke

Ergänzungen und Erweiterungen

Es gibt viele Ideen, wie man den Compiler erweitern könnte. Implementiert wurde z.B. ein TreeWalker, der konstante Ausdrücke bereits zur Übersetzungszeit auswertet oder auch ein TreeWalker, der prüft, ob verwendete Variable auch vorher mit einem Wert versehen wurden. Auch eine Erweiterung der Sprache um bedingte Ausdrücke wie in C wurde implementiert.

Eine weitere Möglichkeit wäre die Übersetzung in den Byte-Code der JVM, um die übersetzten Programme auch ausführen zu können.

Dieser Compiler ist auch zu Testzwecken in anderen Programmiersprachen implementiert worden. Es gibt eine Version für Python und eine Version für Swift.


Zusatzinformationen

Lehre im WiSe 2019/20


Fußzeile