Praktikum: Grundlagen der Programmierung
Prof. Dr. Alexander Pretschner, J. Kranz, G. Hagerer WS 2018/19
Übungsblatt 9 Abgabefrist: s. Moodle
Σ Punkte: 20 | Σ Bonuspunkte: 5
Aufgabe 9.1 (P) Lambdas und Iteratoren
Gegeben sei eine Klasse DateTemperature, welche die maximale Temperatur eines Tages
zusammen mit dessen Datum wie folgt repräsentiert:
1 import java.util.Date;
2
3 public class DateTemperature {
4 final private Date date;
5 final private double temperature;
6
7 public DateTemperature(final Date date, final double temperature) {
8 this.date = date;
9 this.temperature = temperature;
10 }
11
12 public double getTemperature() {
13 return temperature;
14 }
15
16 public Date getDate() {
17 return date;
18 }
19 }
Zusätzlich ist ein Datensatz als Semikolon-separierte Liste in Form einer CSV-Datei gege-
ben, welcher u.a. die Tageshöchsttemperaturen enthält, so wie diese am Raleigh-Durham
International Airport in North Carolina in den USA gemessen wurden1.
Verwenden Sie die in Java 8 eingeführten Lambda-Ausdrücke und die dazugehörige Stream-
API, um diese Temperaturen und deren jeweiliges Datum aus einem gegebenen CSV-
Dateipfad zu parsen. Fassen Sie dafür die CSV-Datei als einen Stream von Strings (eine
Zeile pro String) auf, welcher mittels map() in einen Stream von DateTemperatures um-
zuwandeln ist.
Nachdem die Daten geparst wurden, berechnen Sie für jedes Jahr von jeweils einschließlich
2010 bis 2017 die Durchschnittstemperatur. Verwenden Sie dafür die Methoden filter()
und map() oder alternativ average(). Verwalten Sie das Ergebnis als eine Liste oder
einen Stream von DateTemperatures, wobei das Datum auf den 1. Januar des jeweiligen
Jahres festgelegt ist.
Speichern Sie dieses Ergebnis wiederum als Semikolon-separierte Liste in Form einer CSV-
Datei ab. Öffnen Sie die Datei mit einem geeigneten Tabellenkalkulationsprogramm wie
1https://catalog.data.gov/dataset/local-weather-archive
1
https://catalog.data.gov/dataset/local-weather-archive
zum Beispiel Microsoft Excel oder LibreOffice Calc. Damit können Sie mittels Bar-Plots
die Daten visualisieren.
Aufgabe 9.2 (P) Geometrische Figuren mit Visitor-Pattern
Auf dem vorherigen Blatt haben wir abstrakte Methoden verwendet, um Funktionalität
in einer Basisklasse anzubieten, die dann von jeder Unterklasse verschieden implementiert
wurde. Dieser Ansatz ist in vielen Fällen auch genau richtig, hat allerdings in manchen
Situationen Nachteile:
• Die Implementierung wird über mehrere Klassen verteilt. Dies kann wünschens-
wert sein, kann das Verständis von Code aber auch schwieriger machen, wenn sehr
viel zwischen verschiedenen Klassen gesprungen werden muss, um eine bestimmte
Methode nachzuvollziehen.
• Die Klassen in der Hierarchie müssen angepasst werden. Stellen Sie sich vor, Sie
verwenden eine Hierarchie von Klassen an, die an unterschiedlichen Stellen in Ihrem
Code verwendet wird. Wann immer Sie Funktionalität benötigen, die nicht für alle
Elemente in der Hierarchie auf die gleiche Weise implementierbar ist, müssen Sie
alle Klassen um abstrakte Methoden erweitern. Dies kann dazu führen, dass Ihre
Klassen viele Methoden enthalten, die nur für Spezialzwecke in „Ecken“ Ihres Pro-
gramms gebraucht werden. Es kann außerdem sein, dass Sie eine Bibliothek anbieten
möchten, die jemand anderes in seinem Code verwenden kann. Dieser Klient kann
keine eigenen Methoden zu Ihrer Hierarchie hinzufügen.
Die oben genannten Probleme löst das sog. Visitor-Pattern2. Patterns sind abstrakte
Lösungsvorschläge für bestimmte Programmierprobleme, die sich als Verfahrensweise in
der Software-Entwicklung bewährt haben. Das Visitor-Pattern bietet eine allgemein nutz-
bare Möglichkeit an, von außerhalb einer Hierarchie nach konkreter Unterklasse eines
Objektes zu unterscheiden. Hierzu muss zunächst ein Interface Visitor bereitgestellt
werden, welches für jede konkrete Klasse ConcreteClass der Hierarchie eine Methode
void visit(ConcreteClass c) anbietet. Betrachten wir, um dies besser zu verstehen,
ein konkretes Beispiel einer Klassenhierarchie bestehend aus einer Oberklasse Tier, die
über zwei Unterklassen Hase und Pinguin verfügt. Das passende Visitor-Interface sieht
dann aus wie folgt:
1 public interface TierVisitor {
2 void visit(Hase c);
3 void visit(Pinguin c);
4 }
Diese visit()-Methoden werden in den jeweiligen Unterklassen aufgerufen, und zwar aus
einer Methode mit dem Namen accept() heraus. Die accept()-Methode ist in Oberklas-
sen der Hierarchie abstrakt und erlaubt es so, dynamische Methodenbindung zur Unter-
scheidung nach Unterklasse zu nutzen. Die accept()-Methode ist in jeder Klasse identisch
wie folgt implementiert:
2https://en.wikipedia.org/wiki/Visitor_pattern
2
https://en.wikipedia.org/wiki/Visitor_pattern
1 public void accept(Visitor visitor) {
2 visitor.visit(this);
3 }
Beachten Sie, dass alle accept()-Methoden zwar identisch implementiert sind, sich je-
doch in jeder Klasse unterschiedlich verhalten, da sie sich im statischen Typen von this
unterscheiden.
Die accept()-Methode ruft also eine zur aktuellen Instanz passende visit()-Methode
aus dem Visitor-Interface auf, die genau dasjenige Verhalten implementiert, welches
wir ohne Nutzung des Visitor-Patterns in den Unterklassen der Hierarchie implementiert
hätten. Es wird hier wiederum dynamische Methodenbindung verwendet, dieses Mal al-
lerdings dazu, eine konkrete Implementierung Visitors zu wählen. In unserem Beispiel
ergeben sich die folgenden Klassen:
1 abstract class Tier {
2 public abstract void accept(TierVisitor visitor);
3 }
4
5 class Hase extends Tier {
6 public void accept(TierVisitor visitor) {
7 visitor.visit(this);
8 }
9 }
10
11 class Pinguin extends Tier {
12 public void accept(TierVisitor visitor) {
13 visitor.visit(this);
14 }
15 }
Um nun eigenes Verhalten in Abhängigkeit der Unterklasse eines gegebenen Objektes zu
implementieren, schreibt man nun eine Klasse, die das Interface Visitor implementiert.
Nehmen wir als Beispiel an, dass wir die Differenz zwischen der Anzahl von Pingui-
nen und Hasen, die auf einer Insel leben, ausrechnen möchten. Dazu schreiben wir den
HaPingDiffVisitor:
1 public class HaPingDiffVisitor implements TierVisitor {
2 private int diff = 0;
3
4 public int getDiff() {
5 return diff;
6 }
7
8 public void visit(Hase c) {
9 diff -= 1;
10 }
3
11
12 public void visit(Pinguin c) {
13 diff += 1;
14 }
15 }
Diesen Visitor können wir nun verwenden, indem wir die accept()-Methode von Tier-
Objekten aufrufen:
1 Tier[] insel = /* … */ ;
2 HaPingDiffVisitor v = new HaPingDiffVisitor();
3 for(Tier tier : insel)
4 tier.accept(v);
5 System.out.println(v.getDiff());
Beachten Sie, dass hier sog. doppelter Dispatch stattfindet, wir für jedes Tier also dyna-
mische Methodenbindung zweifach nutzen – zunächst zur Wahl der passenden accept()-
Methode der jeweiligen Unterklasse, anschließend erneut zur Wahl der passenden visit()-
Methode unseres speziellen Visitors. Diese Verbindung einer Klassenhierarchie mit einer
Hierarchie von Visitoren ist die Kernidee des Patterns.
Wir gehen in dieser Aufgabe davon aus, dass wir die Berechnung der Fläche einer geome-
trischen Figur mit einem Visitor durchführen wollen, statt durch Implementierung in den
jeweiligen Unterklassen. Wir arbeiten daher nun mit folgenden Klassen:
1 public abstract class Grundflaeche {
2 public abstract void accept(Visitor visitor);
3 }
4
5 public class Kreis extends Grundflaeche {
6 private int radius;
7
8 public int getRadius() {
9 return radius;
10 }
11
12 public Kreis(int radius) {
13 this.radius = radius;
14 }
15 }
16
17 public class NEck extends Grundflaeche {
18 private int laenge;
19
20 public int getLaenge() {
21 return laenge;
22 }
23
4
24 private int n;
25
26 public int getN() {
27 return n;
28 }
29
30 public NEck(int n, int laenge) {
31 this.n = n;
32 this.laenge = laenge;
33 }
34 }
35
36 public class Quadrat extends Grundflaeche {
37 private int laenge;
38
39 public int getLaenge() {
40 return laenge;
41 }
42
43 public Quadrat(int laenge) {
44 this.laenge = laenge;
45 }
46 }
47
48 public class Rechteck extends Grundflaeche {
49 private int breite;
50
51 public int getBreite() {
52 return breite;
53 }
54
55 private int laenge;
56
57 public int getLaenge() {
58 return laenge;
59 }
60
61 public Rechteck(int breite, int laenge) {
62 this.breite = breite;
63 this.laenge = laenge;
64 }
65 }
Implementieren Sie das Visitor-Pattern und die geforderte Funktionalität zur Flächenbe-
rechnung in den folgenden Schritten.
1. Implementieren Sie das Interface Visitor. Dieses fordert eine visit()-Methode für
jede Unterklasse von Grundflaeche.
2. Implementieren Sie die accept()-Methode in jeder Klasse.
5
3. Implementieren Sie schließlich die Klasse FlaechenVisitor, der die Fläche einer
beliebigen geometrischen Figur der Hierarchie berechnet.
Hinweis: Sie dürfen den oben gegebenen Klassen keine weiteren Methoden (außer der
Methode accept()) hinzufügen.
Hinweis: Eine Alternative zum Visitor-Pattern ist es, den instanceof-Operator zu ver-
wenden. Dies führt allerdings gerade bei größeren Hierarchien zu Kaskaden von if-else-
Statements, die schwer lesbar und in der Ausführung langsam sind. Es ist außerdem sehr
leicht möglich, Unterklassen zu vergessen und diese nicht zu behandeln. Insbesondere
bei Erweiterungen der Klassenhierarchie können hier leicht Fehler in Programmen von
Nutzern der Hierarchie entstehen.
Aufgabe 9.3 (P) Interpretation und Assembler: Einführung
Auf diesem Blatt geht es in den Hausaufgaben unter anderem darum, Code zu inter-
pretieren; dies bedeutet, ein Java-Programm zu schreiben, welches selbst ein Programm
als Eingabe bekommt und dieses anschließend ausführt. Um das zu erreichen, müssen
allgemein die folgenden Schritte behandelt werden:
• Parsing: Zunächst muss das Programm geparst werden. Dies bedeutet, dass die
Textdarstellung des Programms in Objekte der Programmiersprache des Parsers
überführt wird. Die Eingabe des Parsers ist also das Programm als String, die Aus-
gabe eine Instanz einer Klasse Program. Diesen Schritt behandeln wir auf diesem
Übungsblatt nicht.
• Übersetzung: Ist das Programm geparst, liegt es nun als Java-Objekt des Typs
Program vor. Es muss nun in eine Liste von Anweisungen übersetzt werden. Diese
Liste von Anweisungen nennen wir im folgenden Assembler-Code.
• Interpretation: Die Liste der Assembler-Anweisungen muss schließlich nacheinan-
der abgearbeitet werden, wobei die Effekte der jeweiligen Anweisungen auf den vom
Interpreter verwalteten Programmzustand angewandt werden.
Die ersten beiden Schritte bilden zusammen die Aufgaben eines Compilers, der dritte die
des Interpreters3. In dieser Aufgabe geht es zunächst darum, ein intuitives Verständnis
für die Übersetzung eines Programms in eine einfache Assembler-Sprache zu entwickeln.
Betrachten Sie hierzu zunächst das folgende, einfache Programm:
1 int main() {
2 write(read() + read());
3 return 0;
4 }
Die Methode read() liest eine int-Zahl vom Benutzer ein, write(int x) gibt eine Zahl
an den Benutzer aus. Übersetzt in unsere Assembler-Sprache ergibt sich das folgende
Programm:
3Im Falle von Java wird der Interpreter als JVM bezeichnet.
6
0 // Zahlen einlesen und auf dem Stack speichern
1 IN
2 IN
3 // Zahlen addieren
4 ADD
5 // Ergebnis ausgeben
6 OUT
7 // Programm beenden
8 LDI 0 // ‘load immediate’, also Konstante 0 laden
9 HALT
Unser Programm verfügt über einen int-Stack zur Speicherung von lokalen Variablen,
Zwischenergebnissen sowie Speicheradressen. Die Instruktionen nutzen diesen Stack für
Parameter und Ergebnisse – IN legt den eingegebenen Wert auf den Stack, ADD konsumiert
seine beiden Parameter vom Stack und legt das Ergebnis wiederum auf den Stack. Am
Ende des Programms muss ein Ergebniswert für das gesamte Programm auf dem Stack
verbleiben; wir legen in diesem Beispiel dazu 0 auf den Stack.
Unser nächstes Beispiel enthält ein Programm, das Zahlen von 1 bis n aufsummiert, wobei
n vom Benutzer eingegeben wird:
1 int main() {
2 int i, n, result;
3 n = read();
4 result = 0;
5 i = 1;
6 while(i != n) {
7 result = result + i;
8 i = i + 1;
9 }
10 write(result);
11 return 0;
12 }
Der entsprechende Assembler-Code sieht aus wie folgt:
0 // 3 lokale Variablen deklarieren
1 DECL 3
2 // Wert einlesen, in Variable 2 (n) abspeichern
3 IN
4 STS 2
5 // Konstante 0 in Variable 3 (result) abspeichern
6 LDI 0
7 STS 3
8 // Konstante 1 in Variable 1 (i) abspeichern
9 LDI 1
10 STS 1
7
11 // Schleifenbedingung auswerten
12 LFS 2 // ‘load from stack’, Wert von Variable 2 (n) auf den Stack laden
13 LFS 1 // Wert von Variable 1 (i) auf den Stack
14 CMP EQUALS // Test auf Gleichheit
15 // Bei n == i ans Ende der Schleife springen (Zeile 32)
16 BRC 32 // ‘branch if condition’
17 // result = result + i;
18 LFS 1 // Wert von Variable 1 (i) auf den Stack laden
19 LFS 3 // Wert von Variable 3 (result) auf den Stack laden
20 ADD
21 STS 3 // Ergebnis (result + i) in Variable 3 (result) speichern
22 // i = i + 1
23 LDI 1 // Konstante 1 auf den Stack laden
24 LFS 1 // Wert von Variable 1 (i) auf den Stack laden
25 ADD
26 STS 1 // Ergebnis (i + 1) in Variable 1 (i) speichern
27 // ‘true’ (entspricht -1) laden für Rücksprung an Schleifenanfang
28 LDI -1
29 // Rücksprung an Schleifenanfang
30 BRC 12
31 // result ausgeben
32 LFS 3 // Wert von Variable 3 (result) auf den Stack laden
33 OUT
34 // Programm beenden
35 LDI 0
36 HALT
In diesem Beispiel werden lokale Variablen verwendet. Diese dürfen jeweils am Anfang
einer Methode über DECL deklariert werden. Jede Variable erhält dabei eine Position im
Stack-Frame ab 1 – rufen Sie sich in Erinnerung, dass ein Stack-Frame immer genau
demjenigen Stack-Bereich entspricht, den eine aktuell in Ausführung befindliche Methode
verwendet; d.h. für jeden Funktionsaufruf gibt es einen Frame, der zur Laufzeit erzeugt
und verwendet wird. In unserem Beispiel gibt es also nur einen einzigen Stack-Frame,
nämlich den der main()-Methode. Die Variablen lassen sich anschließend über LFS oben
auf den Stack laden bzw. über STS mit einem Wert von oben auf dem Stack beschreiben.
Wir verwenden in diesem Beispiel zur Umsetzung der Schleife außerdem die sog. Sprung-
Anweisung BRC. Diese nimmt einen Wert c vom Stack und setzt das Programm beim
als Parameter gegebenen Punkt fort, wenn c == -1 gilt (−1 repräsentiert true); einen
unbedingten Sprung goto zeilennummer realisieren wir mit der eigentlich überflüssigen
Abfrage if (true) goto zeilennummer bzw. LDI -1; BRC zeilennummer. Der Wert
der Bedingung c wird von der CMP OP-Instruktion berechnet. Diese konsumiert zwei Pa-
rameter a und b vom Stack und legt −1 (entspricht true) auf den Stack, falls a OP b zu
true evaluiert. Sonst legt sie 0 (entspricht false) auf den Stack.
Beachten Sie, dass auf dem Stack bis jetzt nur Werte abgelegt werden: Zwischenergeb-
nisse von Berechnungen und Werte von Variablen. Beachten Sie außerdem, dass bisher
für die Assemblerinstruktionen als Argumente sowohl Adressen – für Sprünge in Schleifen
mit der BRC-Instruktion – als auch Zahlen in Frage kommen. Diese Zahlen können einer-
seits Konstanten sein, z.B. 1, wenn i um 1 erhöht wird. Die Zahlen können aber auch
Referenzen auf Variablen sein, deren Werte gelesen und geschrieben werden können: 1,
8
2 und 3 entsprechen im Programm Referenzen auf die Variablen i, n und result. Für
jede Variable existiert (pro Funktionsaufruf, s.u.) ein Element auf dem Stack. Die Zahlen
1, 2, 3, also die Referenzen, werden benutzt, um die Elemente auf dem Stack zu finden:
relativ zum Anfang des Stack-Frames wird 1, 2, oder 3 (oder k, wenn es k Variablen gibt)
addiert, um das Stackelement für die entsprechende Variable zu identifizieren.
Im letzten Beispiel rufen wir eine Methode auf:
1 int sum(int a, int b) {
2 return a + b;
3 }
4
5 int main() {
6 write(sum(read(), read()));
7 return 0;
8 }
Wieder betrachten wir zunächst den Assembler-Code:
0 // Zahlen einlesen und auf dem Stack speichern
1 IN
2 IN
3 // Methode aufrufen
4 LDI 13 // Anfangsadresse der Methode ‘sum’ auf den Stack laden
5 CALL 2
6 // Ergebnis ausgeben
7 OUT
8 // Programm beenden
9 LDI 0
10 HALT
11
12 // Beginn der Methode sum; a ist im Stack-Frame bei -1, b bei 0
13 LFS 0 // Wert von Variable 0 (Parameter b) auf den Stack laden
14 LFS -1 // Wert von Variable -1 (Parameter a) auf den Stack laden
15 ADD
16 // Rücksprung, größe des Stack-Frames ist hier 2
17 RETURN 2
Statt die Summe wie im ersten Beispiel direkt mittels ADD zu berechnen, rufen wir hier
eine Methode sum() auf. Die Idee des Methodenaufrufs ist wie folgt: Zuerst werden die
Argumente für die Funktion auf den Stack gelegt, dann wird zur ersten Programmzeile
der aufgerufenen Funktion gesprungen, die nun die auf dem Stack liegenden Argumente
verwenden kann, und bei Verlassen der aufgerufenen Funktion wird der Stack bereinigt.
Da die Programmausführung mit der ersten Instruktion beginnt, platzieren wir den Code
der main()-Methode ganz oben im Programm. Zunächst werden zwei Werte eingelesen
und auf den Stack gelegt. Die Instruktion LDI 13 legt anschließend die Adresse von sum(),
also den Index ihrer ersten Instruktion, auf den Stack. Beachten Sie, dass auf dem Stack
9
neben Werten und Variablenreferenzen nun zusätzlich Adressen von Methoden liegen dür-
fen. Lassen Sie sich nicht davon verwirren, dass eine Zahl 17 einen konstanten Wert 17,
eine Referenz auf die 17. lokale Variable und die Codezeile 17 bedeuten kann. CALL 2
ruft die Methode anschließend mit zwei Parametern auf – das sind hier genau die beiden
Werte, die wir vorher mit IN auf den Stack gelegt haben. Allgemein müssen vor Auf-
ruf einer Methode mit k Parametern genau k viele Werte auf den Stack gelegt werden.
Durch den Aufruf der Methode wird ein neuer Frame auf dem Stack angelegt, also ein Be-
reich innerhalb des Stacks, der Parameter und lokale Variablen der aufgerufenen Methode
beinhaltet. Innerhalb dieses Stack-Frames von sum() befindet sich der erste Parameter
an Position −1, der zweite Parameter an Position 0 – also genau vor den lokalen Varia-
blen, die ja mit Positionen ab 1 indiziert werden (s.o.: 1 für i, 2 für n, 3 für result).
Argumente für Assembler-Instruktionen, die im Bereich von −p + 1 bis 0 liegen, können
also ab jetzt auch Referenzen auf p Funktionsparameter sein, die, ganz ähnlich wie lokale
Methodenvariablen, im Stack gespeichert sind. Am Ende der Methode gehen wir mittels
RETURN 2 zurück, der Return-Wert liegt nach dem Aufruf auf dem Stack. Die Zahl 2
entspricht hier nun der Anzahl der genutzten Frame-Zellen, also der Summe aus 2 Para-
metern und 0 lokalen Variablen. Der Stack-Frame von sum() wird an dieser Stelle wieder
vom Stack entfernt. Die Ausführung wird nun im Aufrufer von sum() fortgesetzt, also mit
OUT-Instruktion in Zeile 7.
In der Hausaufgabe sehen wir, dass Methodenaufrufe tatsächlich noch ein wenig (aber nur
ein wenig!) komplizierter sind.
Aufgabe 9.4 (P) Der Weg zum Erfolg
Um in einem Labyrinth vom Eingang zum Aus-
gang zu kommen, kann man die sogenannte
Rechte-Hand-Regel verwenden: Man tastet sich
so an den Wänden entlang, dass man immer zu
seiner rechten Seite eine Wand spürt. Dieser Al-
gorithmus funktioniert allerdings nicht immer;
falls man auf einer Insel im Labyrinth beginnt,
läuft man im Kreis.
Startet man von einem Eingang, kommt man zu-
mindest wieder dorthin zurück und kann ggf.
feststellen, dass es keinen (weiteren) Ausgang
gibt. Strenggenommen müsste der Eingang mar-
kiert werden, um ihn von einem (anderen) Aus-
gang zu unterscheiden, wenn man (wieder) hin-
kommt.
Im Folgenden soll das Durchwandern des Laby-
rinths mittels der Rechte-Hand-Regel mit Hil-
fe der Klasse Maze, die zusammen mit die-
sem Blatt verteilt wird, implementiert wer-
den. Maze bietet die statische Methode int[][]
generateMaze(int width, int height), die
ein zufälliges Labyrinth mit width Spalten und height Zeilen erzeugt, repräsentiert als
ein zweidimensionales int-Array. Hat dieses Array an der Stelle [x][y] den Wert
10
• Maze.WALL, befindet sich im Labyrinth bei den Koordinaten (x, y) eine Wand.
• Maze.PLAYER, befindet sich dort die Durchwanderin.
• Maze.FREE oder Maze.OLD_PATH_DONE, befindet sich dort nichts.
Alle diese Namen für unterschiedliche int-Konstanten sind in der Klasse Maze bereits
definiert. Der Wert Maze.OLD_PATH_DONE zeigt an, dass der Durchwandernde die Stelle
bereits besucht und wieder verlassen hat.
Der aktuelle Zustand des Labyrinths lässt sich mittels der Methode draw(int[][] maze),
die ebenfalls von Maze angeboten wird, in einem Fenster grafisch darstellen. Der Eingang
befindet sich links oben im Labyrinth bei den Koordination (1, 0), d. h. einen Schritt rechts
und null Schritte unterhalb vom oberen linken Eck (0, 0). Der Ausgang ist rechts unten
im Labyrinth bei den Koordinaten (width-1, height-2).
• Implementieren Sie eine Methode void walk(int x, int y, int direction), wel-
che vom Startpunkt (1,0) aus rekursiv alle Lösungsschritte der Rechte-Hand-Regel
nacheinander ausführt und den neuen Zustand jeweils mittels draw() ausgibt.
• Implementieren Sie eine main()-Methode, welche mittels generateMaze ein La-
byrinth erzeugt und dann mittels walk() nach dem Ausgang sucht. Es soll auch
ausgegeben werden, ob ein Ausgang gefunden wurde oder nicht.
Hinweis: Zum Testen ist es sehr nützlich, anstelle von generateMaze() eine Funktion
zu verwenden, die immer das selbe Labyrinth liefert. Eine derartige Funktion ist durch
generateStandardMaze() in Maze.java enthalten. Testen Sie Ihr Programm auch damit!
Die Hausaufgabenabgabe erfolgt über Moodle. Bitte geben Sie Ihren Code als UTF8-
kodierte (ohne BOM) Textdatei(en) mit der Dateiendung .java ab. Geben Sie keine
Projektdateien Ihrer Entwicklungsumgebung ab. Geben Sie keinen kompilierten Code
ab (.class-Dateien). Sie dürfen Ihren Code als Archivdatei abgeben, dabei allerdings
ausschließlich das ZIP-Format nutzen. Achten Sie darauf, dass Ihr Code kompiliert.
Hausaufgaben, die sich nicht im vorgegebenen Format befinden, werden nur mit Punkt-
abzug oder gar nicht bewertet.
Aufgabe 9.5 (H) Klassenhierarchie für Programme, Formatierung [4 Punkte]
In dieser Aufgabe geht es zunächst darum, eine Klassenhierarchie für Programme zu
erstellen. Dies soll es uns später erlauben, die im Präsenz-Teil angesprochene Übersetzung
von Programmen in Assembler-Code zu implementieren. Dazu müssen wir das Programm
in einzelne Teile wie z.B. Methoden, Deklarationen, Zuweisungen etc. zerlegen und jeden
dieser Teile durch eine passende Klasse repräsentieren.
Unsere Hierarchie soll eine Java-ähnliche Sprache modellieren, die wir im folgenden Mi-
niJava mit Methoden nennen. MiniJava soll dabei lediglich aus Methoden, int-Variablen
und den üblichen Kontrollstrukturen bestehen. Die Methoden stehen dabei direkt auf
der höchsten Ebene, da es in MiniJava keine Klassen gibt. Methoden der Java-Standard-
Bibliothek stehen nicht zur Verfügung; allerdings lässt sich eine int-Zahl per read()-
Aufruf vom Benutzer einlesen und per write()-Aufruf an den Benutzer ausgeben. Dekla-
rationen von Variablen sind nur am Anfang einer Methode erlaubt. Beispiele für vollstän-
dige Programme finden Sie in den Präsenz-Aufgaben.
Die Klassenhierarchie für MiniJava soll das Visitor-Pattern umsetzen, welches bereits aus
der Präsenzaufgabe bekannt ist. Dies bedeutet, dass Sie ein Interface ProgramVisitor be-
reitstellen müssen. Außerdem erhalten die Klassen der Hierarchie eine accept()-Methode.
11
Auf diese Weise wird es uns später möglich sein, ohne die Hierarchie zu verändern mit
dieser zu arbeiten – so zum Beispiel, um sie in eine formatierte String-Darstellung umzu-
wandeln oder sie in ein Array aus Assembler-Anweisungen zu übersetzen, was dann durch
die visit()-Methoden implementiert werden wird.
Im Folgenden sind alle nötigen Klassen mit je einer kurzen Beschreibung aufgelistet,
wobei Unterklassen jeweils in Unterpunkten zu finden sind. Die Klassen enthalten für
jede getter-Methode ein privates Attribut, welches im Konstruktor initialisiert wird. Die
Konstruktoren sollen die Attribute entsprechend der gezeigten Reihenfolge erhalten. Die
Beschreibung lässt ferner alle Methoden, die für das Visitor-Pattern implementiert werden
müssen, aus.
• Klasse Program: Repräsentiert ein Programm, welches aus Funktionen besteht
– Methode public Function[] getFunctions(): Liefert die Funktionen des
Programms zurück
• Klasse Function: Repräsentiert eine Funktion des Programms
– Methode public String getName(): Liefert den Namen der Funktion
– Methode public String[] getParameters(): Liefert die Parameter der Funk-
tion
– Methode public Declaration[] getDeclarations(): Liefert die Deklara-
tionen am Anfang der Funktion
– Methode public Statement[] getStatements(): Liefert die Statements in-
nerhalb der Funktion
• Klasse Declaration: Repräsentiert eine Liste von Variabledeklarationen von int-
Variablen
– Methode public String[] getNames(): Liefert die Namen der deklarierten
Variablen
• Klasse Statement: Repräsentiert ein Statement des Programms
– Unterklasse Assignment: Repräsentiert eine Zuweisung der Form variable =
expression;
∗ Methode public String getName(): Liefert den Namen der zugewiese-
nen Variablen
∗ Methode public Expression getExpression(): Liefert den zugewiese-
nen Ausdruck
– Unterklasse Composite: Repräsentiert eine Menge von aufeinanderfolgenden
Statements
∗ Methode public Statement[] getStatements(): Liefert die enthaltenen
Statements zurück
– Unterklasse IfThen bzw. IfThenElse: Repräsentiert ein If-Statement
∗ Methode public Condition getCond(): Liefert die Bedingung
∗ Methode public Statement getThenBranch(): Liefert das Statement im
Then-Zweig zurück
12
∗ Methode public Statement getElseBranch(): Liefert das Statement im
Else-Zweig zurück (nur in der Klasse IfThenElse)
– Unterklasse While: Repräsentiert ein While-Statement
∗ Methode public Condition getCond(): Liefert die Bedingung
∗ Methode public Statement getBody(): Liefert den Körper der Schleife
zurück
∗ Methode public boolean isDoWhile(): Gibt an, ob es sich um eine do-
while-Schleife handelt.
– Unterklasse Return: Repräsentiert ein return-Statement
∗ Methode public Expression getExpression(): Liefert den Ausdruck,
der den Rückgabewert berechnet
– Unterklasse ExpressionStatement: Repräsentiert ein Statement, welches nur
aus einem Ausdruck besteht, z.B. write(42);
∗ Methode public Expression getExpression(): Liefert den enthaltenen
Ausdruck
• Klasse Expression: Repräsentiert einen Ausdruck
– Unterklasse Variable: Repräsentiert eine Variable
∗ Methode public String getName(): Liefert den Namen der Variablen
– Unterklasse Number: Repräsentiert eine Konstante
∗ Methode public int getValue(): Liefert den Wert der Konstanten
– Unterklasse Binary: Repräsentiert einen binären Ausdruck
∗ Methode public Expression getLhs(): Liefert den linken Operanden
∗ Methode public Binop getOperator(): Liefert den Operator
∗ Methode public Expression getRhs(): Liefert den rechten Operanden
– Unterklasse Unary: Repräsentiert einen unären Ausdruck
∗ Methode public Unop getOperator(): Liefert den Operator
∗ Methode public Expression getOperand(): Liefert den Operanden
– Unterklasse Read: Repräsentiert ein read()-Aufruf
– Unterklasse Write: Repräsentiert einen write()-Aufruf
∗ Methode public Expression getExpression(): Liefert den Ausdruck,
dessen Wert ausgegeben werden soll
– Unterklasse Call: Repräsentiert einen Methodenaufruf
∗ Methode public String getFunctionName(): Liefert den Namen der auf-
gerufenen Funktion
∗ Methode public Expression[] getArguments(): Liefert die Argumente
der aufgerufenen Funktion
• Klasse Condition: Repräsentiert eine Bedingung
– Unterklasse True bzw. False: Repräsentiert true bzw. false
– Unterklasse BinaryCondition: Repräsentiert eine binäre Operation auf Bedin-
gungen
13
∗ Methode public Condition getLhs(): Liefert den linken Operanden
∗ Methode public Bbinop getOperator(): Liefert den Operator
∗ Methode public Condition getRhs(): Liefert den rechten Operanden
– Unterklasse Comparison: Repräsentiert einen Vergleich
∗ Methode public Expression getLhs(): Liefert den linken Operanden
∗ Methode public Comp getOperator(): Liefert den Operator
∗ Methode public Expression getRhs(): Liefert den rechten Operanden
– Unterklasse UnaryCondition: Repräsentiert eine unäre Operation auf einer
Bedingung
∗ Methode public Bunop getOperator(): Liefert den Operator
∗ Methode public Condition getOperand(): Liefert den Operanden
Die Aufzählungstypen Binop, Unop, Comp, Bbinop und Bunop werden mit der Aufgabe
verteilt.
Implementieren Sie auf Basis der gegebenen Hierarchie eine Klasse FormatVisitor, die
ein Programm, welches durch eine Instanz der Klasse Program repräsentiert wird, entspre-
chend der auch zum Programmieren in diesem Kurs verwendeten Richtlinien formatiert.
Die Klasse FormatVisitor soll dazu die Methode
public String getFormattedCode()
anbieten, die den formatierten Code zurückliefert. Zum Beispiel soll der Code
1 Function main = new Function(“main”,
2 new String[] {},
3 new Declaration[] {},
4 new Statement[] {
5 new ExpressionStatement(new Write(new Call(“sum”, new Expression[]
{ new Read(), new Read() }))),↪→
6 new Return(new Number(0))
7 });
8
9 Function sum = new Function(“sum”,
10 new String[] {“a”, “b”},
11 new Declaration[] {},
12 new Statement[] {
13 new Return(new Binary(new Variable(“a”), Binop.Plus, new
Variable(“b”)))↪→
14 });
15
16 Program prog = new Program(new Function[] { sum, main });
17
18 FormatVisitor fv = new FormatVisitor();
19 prog.accept(fv);
20 System.out.println(fv.getFormattedCode());
14
folgende Ausgabe erzeugen:
1 int sum(int a, int b) {
2 return a + b;
3 }
4
5 int main() {
6 write(sum(read(), read()));
7 return 0;
8 }
Aufgabe 9.6 (H) Interpretation von Assembler-Code [8 Punkte]
Wie Sie bereits wissen, können die Prozessoren von Computern komplexe Programme –
wie z.B. solche, die in Java geschrieben sind – nicht direkt verarbeiten. Stattdessen müssen
diese in einfache Befehle übersetzt werden; man nennt ein Programm in dieser Form ein
Assemblerprogramm bzw. spricht von der Assembler-Sprache4. In dieser Aufgabe soll ein
Interpreter für die einfache Assemblersprache, die in Aufgabe 9.3 eingeführt wurde, in
Java implementiert werden.
Unser Interpreter erwartet als Eingabe ein Array von Assembler-Instruktionen. Dieses Ar-
ray wird anschließend Schritt für Schritt abgearbeitet, wobei mit der Instruktion an Index
0 begonnen wird. Erreicht der Interpreter die Instruktion HALT, endet die Interpretation
des Programms. Wie Sie bereits aus dem Präsenz-Teil wissen, verwenden die Instruktionen
unserer Assembler-Sprache einen Stack-Speicher für Parameter und Ergebnisse. Der Inter-
preter verwaltet deswegen einen int-Stack der Größe 128. Außerdem stehen sog. Register
zur Verfügung; ein Register speichert einen Datenwert einer festen Größe, in unserem Fall
jeweils ein int. Es stehen hier zunächst zwei allgemein verwendbare Register (r0 und r1)
zur Verfügung, die dazu verwendet werden können, Stack-Elemente zwischenzuspeichern.
Darüber hinaus gibt es drei Spezialregister – den Stack-Pointer, den Befehlszähler (PC)
und den Frame-Pointer –, deren Nutzung später erläutert wird.
Die folgende Tabelle listet alle zur Verfügung stehenden Instruktionen. Anweisungen kön-
nen über konstante Parameter (Immediates) verfügen, die Teil der Instruktion selbst sind.
Es sei o1 das oberste Stack-Element, o2 das zweit-oberste Stack-Element. Werden o1 bzw.
o2 von einer Instruktion verwendet, werden diese Parameter dabei vom Stack entfernt.
Instruktion Immediate Beschreibung
NOP (no operation) keins Diese Instruktion hat keinerlei Effekt.
ADD keins Addiert o1 und o2
SUB keins Berechnet o1 − o2
MUL keins Multipliziert o1 mit o2
MOD keins Berechnet den Divisionsrest von o1 / o2
DIV keins Berechnet die Integer-Division o1 / o2
AND keins Berechnet das bitweise UND, also o1 & o2
OR keins Berechnet das bitweise ODER, also o1 | o2
4Dies ist allerdings ein Stück weit irreführend, weil jede Maschine ihre eigene Form von Assembler-
Sprache verwendet.
15
NOT keins Berechnet das bitweise NOT, also ~o1
LDI (load immediate) c Lädt die Konstante c auf den Stack
LFS (load from stack) i Lädt die lokale Variable bzw. den Methoden-
Parameter i auf den Stack
STS (store to stack) i Speichert den Wert o1 in der lokalen Varia-
blen bzw. dem Methoden-Parameter i
BRC (branch if cond.) i Springt zur Instruktion mit dem Index i, falls
o1 = −1 gilt
CMP (compare) op ∈ {=, <} Legt −1 auf den Stack, falls o1 op o2 gilt;
sonst legt die Instruktion 0 auf den Stack.
CALL n Ruft die Funktion an Index o1 mit n Argu-
menten auf
DECL (declare) n Reserviert Platz für n lokale Variablen auf
dem Stack; nur am Funktionsanfang gültig
RETURN n Rücksprung aus einer Funktion, n ist die
Summe aus Anzahl von lokalen Variablen
und Funktionsparametern
IN keins Liest einen Wert vom Benutzer ein und legt
ihn auf den Stack
OUT keins Gibt o1 an den Benutzer aus
PUSH i ∈ {0, 1} Legt den Wert des Registers r0 bzw. r1 auf
den Stack
POP i ∈ {0, 1} Schreibt den Wert o1 in das Register r0 bzw.
r1
HALT keins Beendet das Programm
Erstellen Sie nun zunächst die abstrakte Klasse Instruction, die als Oberklasse für
alle Instruktionen dient. Leiten Sie von dieser Klasse für jede Instruktion der Tabelle
eine Unterklasse ab (Benennung: Erster Buchstabe groß, Rest klein, z.B. Add für die
ADD-Instruktion). Erhält eine Instruktion einen Immediate, so erwartet die entsprechende
Klasse diesen als Parameter im Konstruktor. Implementieren Sie außerdem das Visitor-
Pattern, indem Sie ein passendes Interface AsmVisitor erstellen, welches für jede Un-
terklasse von Instruction eine visit()-Methode anbietet. Diese Methode benutzen wir
später erst für die formatierte Ausgabe von Assembler-Code und anschließend für die Aus-
führung eines Assemblerprogramms, also der Berechnung von dessen Rückgabewert. Wie
bereits von vorherigen Aufgaben bekannt, benötigen Sie außerdem in jeder Unterklasse
von Instruction eine accept()-Methode.
Erstellen Sie nun zunächst einen Visitor mit dem Namen AsmFormatVisitor, der ein
Programm, welcher er im Konstruktor als Array von Instruktionen erhält, formatiert. Die
Klasse AsmFormatVisitor soll dazu die Methode
public String getFormattedCode()
anbieten, die den formatierten Assembler-Code zurückliefert. Formatierter Assembler-
Code enthält jeweils eine Instruktion pro Zeile; vor jeder Instruktion steht ihre jeweilige
Adresse (Index, Zählung ab 0). Ein formatiertes Assembler-Programm, das hier eine Me-
thode an Index 33 ohne Argumente aufruft, sieht z.B. aus wie folgt.
16
0: LDI 33
1: CALL 0
2: HALT
Unser Interpreter speichert lokale Variablen auf dem Stack. Dazu verwaltet er den soge-
nannten Frame-Pointer. Der Frame-Pointer zeigt auf diejenige Stack-Zelle, ab der lokale
Variablen zu finden sind (zur Erinnerung: die erste lokale Variable befindet sich an der
Adresse Frame-Pointer+1); der Frame-Pointer enthält also eine bestimmte Adresse (einen
Index) des Stacks. Direkt vor dem Frame-Pointer befinden sich die Parameter der Metho-
de (der letzte Parameter liegt in derjenigen Stack-Zelle, auf die der Frame-Pointer zeigt,
also an Adresse Frame-Pointer−0; der vorletzte Parameter an Adresse Frame-Pointer−1
usw.).
Der Frame-Pointer erlaubt es, mittels der Instruktionen LFS und STS auf lokale Variablen
bzw. Methoden-Parameter zuzugreifen – so lädt zum Beispiel die Instruktion LFS 0 das
letzte und LFS -1 das vorletzte Methodenargument auf den Stack, die Instruktion STS 1
überschreibt die erste lokale Variable mit dem obersten Stack-Wert (vgl. Beispiel 2 von
Aufgabe 9.3 aus dem Präsenz-Teil) 5. Der Frame-Pointer muss beim Aufruf von Unter-
programmen auf dem Stack gespeichert und beim Rücksprung wiederhergestellt werden,
da sich der Frame-Pointer immer auf die aktuell ausführende Methode und ihren Frame
bezieht.
Für Methodenaufrufe bietet unsere Maschine die CALL n-Instruktion an, die eine Methode
mit n Argumenten aufruft. Dazu nimmt sie zunächst die Methodenadresse f (Index in
das Programminstruktionen-Array), die das aufrufende Programm vorher auf dem Stack
abgelegt hat, vom Stack. Anschließend werden n Argumente vom Stack entfernt und zwi-
schengespeichert; diese Argumente müssen ebenfalls vorher von der aufrufenden Methode
auf den Stack gelegt worden sein. Die Implementierung der CALL-Instruktion legt nun
den Index derjenigen Instruktion, ab der das Programm nach dem nach Verlassen der
aufgerufenen Methode fortgesetzt werden soll, auf den Stack. Es folgt der aktuelle Wert
des Frame-Pointers, also der Wert des Frame-Pointers der aufrufenden Funktion. Dahin-
ter kommen schließlich die vorher zwischengespeicherten Methodenargumente. Achten Sie
bei Ihrer Implementierung darauf, die Argumente in unveränderter Reihenfolge nach dem
Frame-Pointer auf den Stack zu legen. Betrachten wir als Beispiel folgenden Assembler-
Code, der eine Methode aufruft, welche die Summe ihrer beiden Argumente 42 und 99
bildet:
0 LDI 42
1 LDI 99
2 LDI 5
3 CALL 2
4 HALT
5 LFS -1
6 LFS 0
7 ADD
8 RETURN 2
5Mit STS -1 oder STS 0 können also auch Methodenargumente überschrieben werden. Das geht in
Java und MiniJava gleichermaßen.
17
Die folgende Abbildung zeigt links den Zustand des Interpreters bei erreichen der In-
struktion mit Index 3 (CALL 2). Die Adresse der Methode, die aufgerufen werden soll (5),
wurde durch Instruktion 2 auf den Stack gelegt.
Erinnern Sie sich, dass der Frame-Pointer auf die Stelle im Stack zeigt, die unmittelbar
vor der ersten lokalen Variable der aufgerufenen Methode liegt. Da hier bisher nur die
main()-Methode ausgeführt wird, die in MiniJava keine Parameter hat, ist die Position
der ersten lokalen Variablen im Stack 0, also Frame-Pointer = −1. Der Frame-Pointer ist
notwendig, um relativ zu diesem Frame-Pointer auf die Parameter und lokalen Variablen
der gerade ausgeführten Methode zuzugreifen.
Allgemein gilt: Wenn f1 die Methode f2 aufruft, und p1 der Frame-Pointer der aufrufen-
den Methode f1 ist, dann ist es notwendig, bei Aufruf von f2 den Frame-Pointer p1 auf
den Stack zu legen. Der Frame-Pointer für f2 wird dann entsprechend gesetzt, damit auf
die Parameter und Variablen von f2 zugegriffen werden kann. Bei Verlassen von f2 muss
für die Fortsetzung der Ausführung von f1 der Frame-Pointer wieder auf den Wert p1 ge-
setzt werden: Damit kann dann wieder eine Adressierung von Variablen und Parametern
in f1 erfolgen.
CALL 2
StackProgram StackProgram
PC PC 0
4
-1
42
99
42
99
0
5
2
frame
stackTop
frame
stackTop
3
3
5
3
Im Bild ist die Adresse der aufgerufenen Methode grün, Methodenargumente blau, der ge-
speicherte Frame-Pointer orange und die Rücksprungadresse rot markiert. Auf der rechten
Seite ist der Zustand nach dem Methodenaufruf zu sehen, also bei erreichen der Instruk-
tion mit dem Index 5. Es liegen nun die Rücksprungadresse (4, HALT-Instruktion) und der
ursprüngliche Frame-Pointer (−1) auf dem Stack. Die CALL-Instruktion hat außerdem die
Parameter auf den Stack gelegt und den Frame-Pointer passend auf 3 gesetzt, sodass die-
ser auf den obersten Parameter zeigt – das ist der Eintrag auf dem Stack, der unmittelbar
vor den lokalen Variablen der aufgerufenen Methode liegt. In diesem Fall gibt es keine
lokalen Variablen in der aufgerufenen Methode.
Die RETURN-Instruktion erwartet den Rückgabewert ganz oben auf dem Stack. Sie enthält
zusätzlich ein Immediate, welches angibt, wie viele Stack-Zellen der Methode entfernt
werden müssen – dies entspricht immer der Summe der Anzahl der formalen Parameter
und der Anzahl der lokalen Variablen. Die Instruktion stellt den ursprünglichen Frame-
Pointer wieder her, damit die aufrufende Methode anschließend auf dem korrekten Stack-
Frame arbeitet. Der Befehlszähler wird auf denjenigen Wert gesetzt, der vorher von CALL
18
auf den Stack gesichert wurde, sodass das Programm mit der Instruktion im Aufrufer
hinter dem CALL fortgesetzt wird. Der Rückgabewert wird oben auf Stack belassen und
kann anschließend weiterverarbeitet werden. Die folgende Abbildung zeigt die Ausführung
der RETURN 2-Instruktion an Index 8 des obigen Beispielprogramms:
RETURN 2
StackProgram StackProgram
PC PC 0
4
-1
42
141
99
0
2
frame
stackTop
stackTop
frame
4
88
141
In der Abbildung sind die Farben wie bei der Darstellung des Methodenaufrufs gewählt;
der zusätzliche Rückgabewert wird schwarz dargestellt.
Implementieren Sie nun die Klasse Interpreter, die wiederum das Interface AsmVisitor
implementiert. Der Interpreter soll dabei das Programm als Array der Klasse Instruction
als Parameter des Konstruktors erwarten. Er soll außerdem die Methode
public int execute()
anbieten, die das jeweilige Programm ausführt. Dazu soll die Klasse einen Stack sowie die
oben genannten Register verwalten und diese passend in den jeweiligen visit()-Methoden
manipulieren. Die Methode gibt das letzte auf dem Stack verbleibende Element zurück.
Hinweis: Gehen Sie bei dieser Aufgabe in Schritten vor. Erlauben Sie zunächst einfa-
che Programme, die Additionen sowie I/O mit dem Benutzer erlauben. Erweitern Sie
Ihre Implementierung anschließend um Sprünge. Im letzten Schritt fügen Sie dann die
Unterstützung für lokale Variablen (hier benötigen Sie den Frame-Pointer) sowie Metho-
denaufrufe hinzu.
Behandeln Sie Fehler in Ihrem Programm durch das Werfen einer passenden Excepti-
on. Erstellen Sie dazu eine Klasse InterpreterException, die von RuntimeException
erbt. Erstellen Sie für jeden Fehler, den Sie behandeln, eine passende Unterklasse von
InterpreterException. Achten Sie darauf, dass jede Ihrer Exceptions eine aussagekräf-
tige Meldung in der toString()-Methode zurückliefert.
Testen Sie Ihre Implementierung in einer Klasse InterpreterTest. Nutzen Sie dazu ins-
besondere die folgenden beiden Beispiel-Programme.
Beispiel 1 - Berechnung des größten gemeinsamen Teilers
Das Programm
19
1 int ggt(int a, int b) {
2 if (b >= a) {
3 int temp = b;
4 b = a;
5 a = temp;
6 }
7 do {
8 int temp = b;
9 b = a % b;
10 a = temp;
11 } while(b != 0);
12 return a;
13 }
14
15 int main() {
16 write(ggt(read(), read()));
17 return 0;
18 }
berechnet den größten gemeinsamen Teiler. Der passende Assembler-Code sieht aus wie
folgt:
0 // a und b einlesen und auf dem Stack speichern
1 IN
2 IN
3 // Methode ggt laden und mit zwei Argumenten aufrufen;
4 // der Rückgabewert landet wiederum auf dem Stack.
5 LDI 15 // Adresse von Methode ggt laden
6 CALL 2
7 // Rückgabewert des Aufrufs vom Stack nehmen und dem Nutzer ausgeben
8 OUT
9 // Programm beenden
10 LDI 0
11 HALT
12
13 // Methode ggt mit 2 Argumenten (a bei -1 im Stack-Frame, b bei 0)
14 // Eine lokale Variable anlegen
15 DECL 1
16 // Tausch von größerer Zahl nach vorne
17 // Lade Argument a auf den Stack
18 LFS -1
19 // Lade Argument b auf den Stack
20 LFS 0
21 // Ist !(b >= a), also b < a, ...
22 CMP LESS
23 BRC 31 // ... zur Hauptschleife springen
24 // Sonst: Tauschen von a und b
25 LFS 0
20
26 LFS -1
27 STS 0
28 STS -1
29 // Hauptschleife
30 // temp = b
31 LFS 0
32 STS 1
33 // b = a % b
34 LFS 0
35 LFS -1
36 MOD
37 STS 0
38 // a = temp
39 LFS 1
40 STS -1
41 // Schleifenbedingung auswerten
42 LDI 0
43 LFS 0
44 CMP EQUALS
45 NOT
46 // Rücksprung zur Schleife, wenn Bedingung hält
47 BRC 31
48 // Rückgabewert auf den Stack legen
49 LFS -1
50 // Wir geben zwei Argumente und eine lokale Variable frei
51 RETURN 3
Beispiel 2 - Berechnung des Fakultät
Das Programm
1 int fak(int n) {
2 if(n == 1)
3 return 1;
4 return n * fak(n - 1);
5 }
6
7 int main() {
8 write(fak(read()));
9 return 0;
10 }
berechnet die Fakultät n! einer Zahl n rekursiv. Der passende Assembler-Code sieht aus
wie folgt:
0 IN
1 LDI 9 // Adresse von Methode fak laden
2 CALL 1
21
3 OUT
4 LDI 0
5 HALT
6
7 // Methode fak, 1 Argument (n)
8 // Ist n == 1?
9 LDI 1
10 LFS 0
11 CMP EQUALS
12 NOT
13 BRC 17 // Sprung zum rekursiven Aufruf
14 LDI 1
15 RETURN 1
16 // Rekursiver Aufruf
17 LDI 1 // 1 laden
18 LFS 0 // n laden
19 SUB // n - 1 berechnen
20 LDI 9 // Adresse von Methode fak laden
21 CALL 1 // fak(n - 1)
22 LFS 0 // n laden (für n *)
23 MUL // n * fak(n - 1) berechnen
24 RETURN 1
Aufgabe 9.7 (H) In der Weihnachtsassemblybäckerei [8 Punkte]
In der vorletzten Aufgabe haben wir eine Java-Klassenhierarchie zur Repräsentation von
MiniJava-Programmen entwickelt. In der letzten Aufgabe haben wir dann einen Interpre-
ter für eine einfache Assembler-Sprache implementiert. In dieser Aufgabe sollen diese bei-
den Teile nun zusammengeführt werden, indem ein Code-Generator implementiert wird.
Dieser soll aus einer Instanz der Klasse Program ein Array bestehend aus Instruction-
Objekten generieren, welches dem repräsentierten Programm entspricht. Das Assembler-
Programm kann anschließend vom Interepreter ausgeführt werden.
Erstellen Sie hierzu einen weiteren Visitor mit dem Namen CodeGenerationVisitor. Der
CodeGenerationVisitor soll eine Methode
public Instruction[] getProgram(),
anbieten, mit der man das übersetzte Programm erhalten kann.
Die Code-Generierung generiert Code für alle Funktionen eines Programms. Jedes valide
Programm muss über eine Funktion verfügen, welche den Namen main hat. Ihr Assembler-
Programm muss diese Funktion als erstes aufrufen. In MiniJava gibt jede Funktion einen
int-Wert zurück. Ein Programm, welches eine Funktion ohne return-Statement verlässt,
ist invalide. Der Rückgabewert der main()-Funktion entspricht dem Rückgabewert der
execute()-Funktion des Interpreters. Gehen Sie bei Ihrer Implementierung wie folgt vor:
1. Beginnen Sie mit Ausdrücken, erlauben Sie also die Generierung von Code für Aus-
drücke. Testen Sie Ihre Implementierung anhand von Beispielen.
22
2. Fügen Sie nun noch Ein- und Ausgabe mittels read() bzw. write() hinzu.
3. Erweitern Sie Ihre Implementierung um die Unterstützung von Variablen.
4. Erweitern Sie Ihre Implementierung um die Unterstützung von Kontrollfluss, also
von Bedingungen und Schleifen.
Hinweis: Beachten Sie, dass Sie während der Übersetzung z.B. einer Schleife den
Index der ersten Instruktion nach der Schleife noch nicht kennen. Lösen Sie dieses
Problem, indem Sie zunächst einen Platzhalter für einen Sprung einsetzen, den Sie
später austauschen.
5. Implementieren Sie Unterstützung von Funktionen und Funktionsaufrufen.
Hinweis: Beachten Sie, dass Sie, ähnlich dem Problem bei der Generierung von
Code für Schleifen, den Index einer Methode an der Stelle eines Aufrufs ggf. nicht
kennen. Auch hier können Sie zunächst einen Platzhalter verwenden, den Sie aus-
tauschen, sobald Sie den Code für die jeweilige Methode generieren.
Behandeln Sie Fehler durch das Werfen einer passenden Exception. Insbesondere sollten
Sie die folgenden Fehler abfangen:
• Eine unbekannte Funktion wird aufgerufen (gilt insbesondere auch für den initialen
Aufruf zu main).
• Eine nicht deklarierte Variable wird verwendet.
Manche Fehler sind schwieriger zu erkennen und müssen daher nicht behandelt werden;
dies gilt insbesondere für die folgenden Fehler:
• Jeder Pfad durch eine Funktion endet in einem return-Statement (vgl. oben).
• Variablen wird ein Wert zugewiesen, bevor sie gelesen werden.
Erstellen Sie eine Klasse CodeGenException, die von RuntimeException erbt. Erstellen
Sie für jeden Fehler, den Sie behandeln, eine passende Unterklasse von CodeGenException.
Achten Sie darauf, dass jede Ihrer Exceptions eine aussagekräftige Fehlermeldung in der
toString()-Methode zurückliefert.
Testen Sie Ihre Implementierung zunächst mit den beiden Beispiel-Programmen der letz-
ten Aufgabe in der Klasse CodegenTest. Überlegen Sie sich außerdem weitere Tests!
Aufgabe 9.8 (H) Weihnachtsnuss: Switch [5 Bonuspunkte]
In dieser Aufgabe geht es darum, den Compiler um die Unterstützung für das switch-
Statement zu erweitern. Erstellen Sie dazu zunächst die Klasse SwitchCase, die einen
Zweig innerhalb des switch-Statements repräsentiert und die über die Methoden
public Number getNumber()
und
public Statement getCaseStatement()
23
verfügt. Erstellen Sie außerdem die Klasse Switch, die von Statement erbt und die Me-
thoden
public SwitchCase[] getCases(),
public Statement getDefault()
und
public Expression getSwitchExpression()
bietet. Erstellen Sie schließlich die Klasse Break, die das break;-Statement repräsentiert.
Ihre Klassen sollen außerdem über passende Konstruktoren verfügen.
Erweitern Sie nun sämtliche Visitoren aus den vorhergehenden Aufgaben um die Unter-
stützung für die neu hinzugefügten Statements (dies umfasst insbesondere den Visitor
FormatVisitor sowie den Visitor CodeGenerationVisitor).
Testen Sie Ihre Implementierung in einer Klasse TestSwitch, unter anderem mit dem
folgenden Programm.
1 int main() {
2 int x, y, z;
3 x = read();
4 z = 0;
5 switch(x) {
6 case 1: {
7 y = read();
8 switch(y) {
9 case 1: {
10 z = z + 1;
11 break;
12 }
13 case 2:
14 z = z + 2;
15 }
16 break;
17 }
18 case 2: {
19 z = 42;
20 // hier ist KEIN break!
21 }
22 default:
23 z = z + 1;
24 }
25 write(z);
26 return 0;
27 }
Hinweis: Die Unterstützung für break; innerhalb von Schleifen ist nicht gefordert.
24