Technische Universität München
Fakultät für Informatik
Prof. Dr. Helmut Seidl
Riitta Höllerer

Praktikum des Übersetzerbaus WS 2004:

Generierung von Benutzungsoberflächen

Aufgabenblatt 6

2. Juni 2004

11. Aufgabe (Codeerzeugung für if- und while-Anweisung)

Erweitern Sie Ihren Compiler von Aufgabe 9 so, dass er für if- und while-Anweisungen Jasmin-Code erzeugt. Jasmin ist ein Assembler für die "Java Virtual Machine" (JVM). Er konvertiert die Assembler-Eingabe in binäre Java Klassendateien.

Im folgenden wird angegeben welcher Code zu erzeugen ist:

Codeerzeugung für Bedingungen

Die abstrakte Syntax für Bedingungen ist gegeben als
Bed ::= ... | { BoolConst} "int": value // true=1, false=0
Für eine Bedingung BoolConst(value) wird folgender Code erzeugt:

bipush 1 oder bipush 0

je nachdem, ob value 1 oder 0 ist (true wird im Scanner als 1 codiert; false als 0).

Im obigen Übersetzungsschema wird der Code für die Bedingung so erzeugt, dass zur Laufzeit immer der Wert der Bedingung als oberstes Kellerelement erscheint.

Code für if-Anweisung

Abstrakte Syntax

Anw ::= ... | { IfThenElse } Bed Anw_Seq Anw_Seq

Für IfThenElse (bed anw_Seq1 anw_Seq2) wird folgender Code erzeugt:
<Code für bed> ifnull label1 <Code für anw_Seq1> jsr label2 label1: <Code für anw_Seq2> label2:
Im obigen Übersetzungsschema wird zunächst der Code für die Bedingung erzeugt. Danach folgt der Sprungbefehl. Die Sprungbedingung ifnull vergleicht das oberste Kellerelement mit 0. Zur Laufzeit wird, wenn der Vergleich erfolgreich ist, zu label1, d.h. zum else-Teil gesprungen. Nach dem Code für den then-Teil folgt ein Sprung über den else-Teil. Vor dem else-Teil wird die Marke label1 gesetzt, danach folgt der Code für den else-Teil. Zum Schluss wird die Marke label2 generiert.

Marken im Jasmin-Code werden durch einen Markennamen, gefolgt von einem Doppelpunk und newline, definiert. Markennamen können nicht mit einer Ziffer beginnen und dürfen keines der folgenden Sondeerzeichen enthalten

= : . " -

Code für while-Anweisung

Abstrakte Syntax:
Anw ::= ...| {WhileAnw} Bed Anw_Seq

Für WhileAnw (bed anw_Seq) wird folgender Code erzeugt:

jsr label1 label2: <Code für anw_Seq> label1: <Code für bed> ifnonnull label2

Es ist üblich den Code für die Bedingung an das Ende der Schleife zu setzen. Dadurch ist der Code etwas günstiger.

Im folgenden wird angegeben, was in dieser Aufgabe genau zu tun ist:

Codeerzeugung für konstante Bedingungen
Ergänzen Sie den Visitor EmitCodeVisitor um eine visit-Methode für Bedingungen, die nur aus true oder false bestehen. Oben wurde dafür der Knotenname BoolConst verwendet:
public void visit(BoolConst boolConst)
In der Methode soll der Code nach dem obigen Schema erzeugt werden.
Strategieänderung
Wie Sie aus den obigen Code-Schemata sehen, kann der Code für if- und while-Anweisung nicht in der standard Bottom-up-Reihenfolge ausgedruckt werden, sondern wird in einer bestimmten Reihenfolge in den IfThenElse- und WhileAnw-Knoten zusammengestellt.
Für die Strategieänderung gibt es zwei Lösungen. Sie benutzen für den Durchlauf des Baumes wie im IdentificationVisitor statt der traverseBottomUp-Methode die accept-Methode. Dabei mussen Sie die Durchlaufstrategie für alle Knoten explizit angeben, d.h. für jeden Knotentyp eine visit-Methode schreiben, in der meist nur childrenAccept-Methode aufgerufen wird. In den IfThenElse- und WhileAnw-Knoten müssen Sie dann die Sohn-Knoten in der richtigen Reihenfolge besuchen, so dass der Code wie oben ausgedruckt wird. Den Baumdurchlauf müssen Sie auch in der main-Methode der Main-Klasse mit accept anstoßen.
Bei der zweiten Lösung behalten Sie die Bottom-up-Strategie, aber geben den Code nicht direkt aus, sondern speichern ihn in einem Attribut im Baum und können ihn dann in den IfThenElse- und WhileAnw-Knoten in der gewünschten Reihenfolge zusammenstellen. Dafür definieren Sie im ast.cl ein Code-Attribut für die Knoten für die wir Code erzeugen:

attr "String" code with Anw_Seq, Anw, Bed, Ausdr, Var;
und belegen das Code-Attribut z.B. im BoolConst-Knoten:
public void visit( BoolConst boolConst ) {
boolConst.setCode("bipush " + boolConst.getValue() + "\n");
Wenn der Code länger als ein Befehl ist, sollte man es in einem StringBuffer zusammenstellen und dann erst in das Code-Attribut speichern.
... StringBuffer buffer = new StringBuffer(); buffer.append( . . . ); . . . *.setCode( buffer.toString() );
Zugriff auf das Code-Attribut des Sohnes sieht folgendermaßen aus, z.B. auf das Code-Attribut der Bedingung im WhileAnw-Knoten
whileAnw.getBed().getCode();

Sie müssen auch den Code für Anw_Seq0, Anw_Seq1, BinAusdr, IntAusdr , VarAusdr und IdentAusdr in das jeweilige Code-Attribut speichern! Für die weiteren Knotentypen müssen Sie keine eigene visit-Methoden definieren.
Marken im Code
Für die erzeugung der Marken brauchen Sie in EmitCodeVisitor einem Markenzähler und eine Methode zur Erhöhung des Zählers.
Codeerzeugung für if- und while-Anweisung
Ergänzen Sie den Visitor EmitCodeVisitor um visit-Methoden für IfThenElse- und WhileAnw-Knoten:
public void visit(IfThenElse ifThenElse) public void visit(WhileAnw whileAnw )
In den Methoden soll der Code nach den obigen Schemas erzeugt werden.
Generieren Sie einen Compiler mit Ihren Quellen und testen Sie ihn mit folgendem Beispiel:
program P{ int a, b, c a + b * c -111 while true do a+b*222 od if false then b+333 fi if true then while true do a+b*444 od else if false then a+b*555 fi fi }

Geben Sie als Lösung der Aufgabe

eine mit Code2Html erzeugte Datei, die Ihre Eingabedateien (Scanner.jflex, Parser.cup ast.cl, EmitCodeVisitor.java), obiges Beispiel und den ausgedruckten abstrakten Syntaxbaum für das Beispiel enthält.
Zusätzlich geben Sie noch Ihre Quelldateien und den lauffähigen Compiler vom Verzeichnis dist ab (Verwenden Sie ant dist dafür.)

Jasmin Dokumentation ist hier: Jasmin Home Page

12. Aufgabe (IdentificationVisitor für den EMUGEN-Compiler)

In dieser Aufgabe realisieren wir einen Teil der Identifikation (=Bindungsanalyse) für den EMUGEN-Compiler, für den wir den Scanner und Parser in der Aufgabe 7 und den Aufbau des abstrakten Syntaxbaumes in der Aufgabe 10 realisiert haben.

Bei unserer Identifikation prüft der Compiler, ob alle auf den rechten Seiten der Produktionen benutzten Identifier definiert sind, d. h. ob für sie eine Produktion angegeben ist. Es dürfen auch keine doppelten Definitionen vorkommen. Unser Compiler müsste also beim folgenden Beispiel melden, dass Privat nicht definiert ist und Geschaeftlich doppelt deklariert ist:

Adressbuch::= Privat Geschaeftlich //Privat::= Person* Geschaeftlich::= Person* Geschaeftlich::= Person* Person::= String:Nachname String:Vorname String:Telefon

Hinweise:

Wenn Sie gute Fehlermeldungen ausgeben wollen sollten Sie die Zeilen und Spaltenangaben vom Scanner im Parser im abstrakten Syntaxbaum notieren, z.B. im Demo-Compiler für Identifier:
In der CUP-Eingabe:
var ::= IDENT:i {: RESULT = new IdentAusdr(i,ileft, iright); :}
Als Namen für die 3. und 4. Komponente eines Symbols kontekatiniert CUP den Namen der value-Komponente (hier i) mit left bzw. right (s. Objekttyp Symbol im Merkblatt3).

In der Classgen-Eingabe können Sie selbstgewählte Namen verwenden:
Var ::= {IdentAusdr} "String":ident "int":line "int": column | . . .
Dann können Sie im IdentificationVisitor in der Fehlermeldung auch die Zeilen und Spaltenangabe ausgeben.
Hier als Beispiel die Ausgabe der Zeilen- und Spaltenangaben beim IdentAusdr-Besuch:
public void visit(IdentAusdr identAusdr) { identAusdr.deklinfo = lookup(identAusdr.ident); System.out.println("Ident: "+identAusdr.ident+" Zeile: "+identAusdr.line+" Spalte: "+ identAusdr.column); }
Überlegen Sie welche Datenstrukturen Sie im IdentificationVisitor für das Sammeln der lhs-Namen bzw. rhs-Namen wählen. Sie brauchen Operationen fürs Eintragen, fürs Nachschauen, ob das Element schon drin ist und fürs Durchgehen der eingetragenen Elemente. Ganz raffiniert ist hier, den Classgen selber zur Hilfe zu nehmen. Schauen Sie mal, war Classgen für folgendes generiert.
Production ::= String: name String*: elements
Der generierte Datentyp StringList wäre geeignet für unsere Aufgabe und Sie könnten Sie in dem IdentificationVisitor verwenden.