Überblick
Um die Unabhängigkeit des Zwischencodes von der Zielarchitektur zu demonstrieren, wurde parallel zum Linux Backend ein Interpreter implementiert, der ähnlich arbeitet. Dazu wurde der Hauptspeicher mit einer Arrayliste und ein Registersatz mit einer Hashmap nachgebaut. Die Größe des Hauptspeichers und die Anzahl der nutzbaren Register sind unendlich. Es wurden weiterhin mit Integervariablen die wichtigen Spezialregister Stack-Pointer, Frame-Pointer, Programmzähler, aktueller Level und "aktueller Gültigkeitsbereich" nachgebaut. Letzterer muss gespeichert werden, da der Code anders verwaltet wird, als in realen Maschinen. Dort werden die Instruktionen aller Gültigkeitsbereiche nacheinander in den Programmspeicher geschrieben und bleiben dort während der gesamten Programmausführung. Im Interpreter werden alle Gültigkeitsbereiche getrennt verwaltet und man muss sich merken, von welchem Gültigkeitsbereich gerade Code ausgeführt wird.
Benötigte Daten
Damit der Interpreter funktionieren kann, benötigt er zum Einen natürlich den auszuführenden Code. Dies ist, wie bereits erwähnt, der Zwischencode. Der Zwischencode liegt in linearisierter Form vor. Der Code eines jeden Gültigkeitsbereich wird als Liste von Anweisungen gespeichert. Alle Anweisungslisten sind wiederum in einer Liste zusammengefasst, der Codeliste. Die Reihenfolge, in der die Gültigkeitsbereiche in der Liste vorkommen, entspricht dem Auftreten im Quelltext (siehe Numerieren der Prozeduren). Weiterhin muss für jeden Gültigkeitsbereich das "Groblayout" des Aktivierungssegments verfügbar sein, also Größe, Werte der Konstanten, Level. Dazu wird die Symboltabelle ausgelesen und für jede Prozedur wird ein sogenanntes InterpreterFrame erzeugt. Dieses Frame hat eine bestimmte Größe, nämlich vier reservierte Felder + Anzahl der Konstanten + Anzahl der Variablen, die es aufnehmen muss. Außerdem enthält es den level, dieser wird allerdings nicht direkt in das aus dem Frame erzeugte Aktivierungssegment eingetragen, so dass er keinen Einfluss auf dessen Größe hat. Die Werte der Konstanten werden sofort eingetragen. Alle Frames werden im sogenannten FrameConatainer abgelegt.
Es werden vier statt der üblichen drei reservierte Felder benutzt, da im Interpreter neben Frame-Pointer, Stack-Pointer und Programmzähler auch die ID des aufrufenden Codeblocks gespeichert werden muss, um bei der Rückkehr von einer Unterprozedur im richtigen Codeblock mit der Programmausführung fortzufahren.
Programmabarbeitung
Der Interpreter besteht aus Initialisierung und aus einer Schleife. (Diese befinden sich in der Klasse backend.InterpreterBackend, Methode transformToExecutable() im Projekt PL0Compiler.)
Die Hauptschleife
Beim Start des Interpreters werden die "Register" und der "Hauptspeicher" initialisiert. Als nächstes werden aus dem Code des Hauptprogramms alle Label entfernt und zusammen mit ihrer Position im Code in eine HashMap, der sogenannten labelTable eingetragen. Muss später ein Sprungbefehl ausgeführt werden, so kann in dieser Tabelle nachgesehen werden, zu welcher Position im Code gesprungen werden muss.
Die Schleife wird ausgeführt, solange das Hauptprogramm noch nicht komplett abgearbeitet ist. Es wird immer die nächste zu bearbeitende Instruktion aus der Codeliste abgearbeitet und anschließend der Befehlszähler erhöht.
Anweisungen und Ausdrücke
Anweisungen werden in einer speziellen executeStatement(Statement s) Methode ausgeführt. Falls für eine Anweisung Ausdrücke zu berechnen sind, geschieht dies mit einer Hilfsmethode processExpression(Expression e). Außerdem gibt es Methoden, um in den simulierten Hauptspeicher oder die simulierten Register zu speichern bzw. aus ihnen zu laden.
Die meisten Anweisungen und Ausdrücke kommen ohne weitere Erläuterung aus, es sei hier der Code für eine binäre Operation gezeigt:
public int processExpression(Expression e) {
...
if (e instanceof BINOP) {
BINOP binop = (BINOP)e;
//Operatoren ermitteln
int op1 = processExpression(binop.getSrc1());
int op2 = processExpression(binop.getSrc2());
switch(binop.getOperatorInt()) {
case BINOP.PLUS:
return op1 + op2;
case BINOP.MINUS:
return op1 - op2;
case BINOP.MUL:
return op1 * op2;
case BINOP.DIV:
if (op2 == 0) {
System.err.println("Runtime Error: Division by zero");
System.exit(-2);
}
return op1 / op2;
case BINOP.AND:
return op1 & op2;
case BINOP.OR:
return op1 | op2;
case BINOP.XOR:
return op1 ^ op2;
case BINOP.LSHIFT:
return op1 << op2;
case BINOP.RSHIFT:
return op1 >> op2;
}
}
...
}
|
Man erkennt, dass die Abarbeitung von Anweisungen und Ausdrücken rekursiv absteigend erfolgt.
Prozedurbehandlung
Prozeduraufruf
Der komplizierteste Teil des Interpreters ist die Steuerung der Prozeduraufrufe. Beim Betreten oder Verlassen einer Prozedur muss ein Aktivierungssegment erzeugt bzw. zerstört werden.
Beim Prozeduraufruf wird die Methode prepareCall(CALL call) aufgerufen. Es wird ein Frame für den neuen Gültigkeitsbereich aus dem FrameContainer geholt, anschließend eine "Zeigerstruktur" entsprechend dem Abschnitt "Variablenrepräsentation" aufgebaut.
Der Frame wird auf den Stack von Aktivierungssegmenten gelegt. Im Feld für den dynamischen Link wird der aktuelle Frame-Pointer gespeichert. Im Feld für die Rücksprungadresse wird der derzeitige Programmzählerstand gespeichert und das Feld für den Gültigkeitsbereich erhält die ID des aktuellen Gültigkeitsbereichs.
Das Setzen des statischen Links geschieht genau wie im Abschnitt "Statische Links" beschrieben. Das sieht folgendermaßen aus:
//Neuer statischer Link: Wenn a b aufruft, folge level(a) - level(b) + 1
//statischen Links von a aus, das Ziel ist der statische Link von b
int newStaticLink = fp; //im einfachsten Fall zeigt der static link auf das aufrufende Frame
for (int i = 0; i < currentLevel - iframe.level() + 1; i++) {
newStaticLink = ((Integer)stack.get(newStaticLink + 0)).intValue();
}
stack.set(bp + 0, new Integer(newStaticLink));
|
Nachdem der statische Link gesetzt ist, nimmt der Frame-Pointer den Wert des alten Stack-Pointers an, der Stack-Pointer wird um die Größe des neuen Frames erhöht. Es werden currentCode, currentScope und currentLevel aktualisiert und der Befehlszähler sowie die Labeltabelle werden für den neuen Codeblock initialisiert.
Verlassen einer Prozedur
Das Verlassen einer Prozedur gestaltet sich weniger aufwendig. Der Stack-Pointer erhält den Wert des Frame-Pointers, der Frame-Pointer wird an den Anfang des vorherigen Frames gesetzt, indem er dem dynamischen Link des zu verlassenden Aktivierungssegments folgt, in den Befehlszähler wird die im Frame gespeicherte Rücksprungadresse eingetragen. Es werden currentCode, currentScope und currentLevel neu gesetzt. Den aktuellen Level erhält man, indem man zählt, wie vielen statischen Links man folgen muss, um zur Adresse 0 (der Startadresse des Hauptprogramms) zu gelangen. Alternativ hätte man auch einen Stack führen können, der sich die jeweiligen Level merkt. Die nun nicht mehr benötigte Speicherelemente werden vom Speicherstack (der Arrayliste, die den Hauptspeicher repräsentiert) entfernt.
 Das Linux-Backend | Downloads und Informationen  |