 |
|||
| HSG |
|
Codeerzeugung
Als Zielsprache soll Bonsai-Assembler verwendet werden. Für die grundsätzlichen Ideen wird auf diesen MiniJava-Compiler verwiesen.
Achtung: Die Seite ist vorläufig. Der Code des Compilers ist noch nicht überall korrekt dokumentiert.
'Code-Schnipsel'
- Initialisierungen
- Zuweisungen
- Vergleiche
Initialisierungen
i1: a = n, n natürliche Zahl, n > 0
Es sind die Fälle 'initiale Zuweisung' und 'Zuweisung einer Konstanten' zu unterscheiden. Ist a noch nicht in der Variablentabelle, so liegt eine initiale Zuweisung vor. In diesem Fall wird kein Code erzeugt, sondern es wird eine Speicherzelle mit a assoziiert und mit n belegt. Es wird also ein entsprechender Eintrag in der Variablentabelle erzeugt.
Zuweisungen
z1: a = 0
Wirkung: a wird auf Null gesetzt, Hilfsvariablen: keine, Länge: 5
formal: a hilf: - Länge: 5 tst a jmp (+2) jmp (+3) dec a jmp (-4)
Code-Schnipsel können mit Hilfe des Bonsai-Interpreters bi.py getestet werden. Eine Testdatei z0.txt könnte folgendermaßen aussehen:
a = 17 tst a jmp (+2) jmp (+3) dec a jmp (-4)
z2: a = a + 1
formal: a hilf: - Länge: 1 inc a
z3: a = a - 1
formal: a hilf: - Länge: 1 dec a
z4: a = n, n natürliche Zahl, n > 0
Es sind die Fälle 'initiale Zuweisung' und 'Zuweisung einer Konstanten' zu unterscheiden. Sollte die Variable a in der Symboltabelle bereits existieren, so wird sie zunächst auf Null gesetzt und dann n-mal 'inc a' angehängt.
Dieses spezielle Verhalten ist vom Programmierer zu bedenken.
z5: a = a + n, n natürliche Zahl
a = a + 5 wird zu
formal: a hilf: - Länge: n inc a inc a inc a inc a inc a
z6: a = a - n, n natürliche Zahl
a = a - 3 wird zu
formal: a hilf: - Länge: n dec a dec a dec a
z7: a = b
Wirkung: Unabhängig vom Inhalt von a wird der Inhalt von b nach a kopiert, der Inhalt von b wird nicht verändert, Hilfsvariablen: h, Länge: 18
formal: a, b
hilf: h
Länge: 18
tst a
jmp (+2)
jmp (+3)
dec a
jmp (-4)
tst b
jmp (+2)
jmp (+5)
dec b
inc a
inc h
jmp (-6)
tst h
jmp (+2)
jmp (+4)
dec h
inc b
jmp (-5)
a auf Null setzen von b auf a 'umfüllen', h wird als Null vorausgesetzt restaurieren von b h ist am Ende 0
z8: a = a + b
Der Code ist entspricht a = b, wobei der erste Teil entfällt.
formal: a, b hilf: h Länge: 13 tst b jmp (+2) jmp (+5) dec b inc a inc h jmp (-6) tst h jmp (+2) jmp (+4) dec h inc b jmp (-5)
z9: a = a - b
Der Code ist entspricht a = b, wobei der erste Teil entfällt. An einer Stelle steht dec a statt inc a.
formal: a, b hilf: h Länge: 13 tst b jmp (+2) jmp (+5) dec b inc a inc h jmp (-6) tst h jmp (+2) jmp (+4) dec h inc b jmp (-5)
z10: a = b + c
a = b + c kann durch die Folge a = b, a = a + c ersetzt werden.
z11: a = b - c
a = b - c kann durch die Folge a = b, a = a - c ersetzt werden.
z12: a = b * c
a = 0 b = 17 c = 13 h1 = 0 h2 = 0 tst c jmp (+2) jmp (+5) dec c inc h1 inc h2 jmp (-6) tst h2 jmp (+2) jmp (+4) dec h2 inc c jmp (-5) tst h1 jmp (+2) jmp (+16) tst b jmp (+2) jmp (+5) dec b inc a inc h2 jmp (-6) tst h2 jmp (+2) jmp (+4) dec h2 inc b jmp (-5) dec h1 jmp (-17)
z13: a,b = b,a
a = 7 b = 13 tst a jmp (+2) jmp (+4) dec a inc h jmp (-5) tst b jmp (+2) jmp (+4) dec b inc a jmp (-5) tst h jmp (+2) jmp (+4) dec h inc b jmp (-5)
Vergleiche
Letztendlich wird bei einer Bedingung auf eine einzige Variable getestet, die den logischen Wert der Bedingung angibt.
v1: a == 0
Bedingungen der Form Variable-Operator-Konstante sind dann gut auszuwerten, wenn die Konstante Null ist.
formal: a hilf: - Länge:3 tst a jmp nein jmp ja
v1: a > 0
formal: a hilf: - Länge:3 tst a jmp ja jmp nein
Bedingungen der Form Variable-Operator-Variable, z.B. a <= b
Allgemein sollte eine Bedingung eine Variable liefern, die den Wahrheitswert der Bedingung angibt.
Der Bedingung wird eine Hilfsvariable h1 zugeordnet. h1 = 0 bedeutet falsch, h1 = 1 bedeutet wahr (grundsätzliche Ideen)
a b | == != < > <= >= -----+------------------ 0 0 | + - - - + + 0 + | - + + - + - + 0 | - + - + - + + + | ? ? ? ? ? ?
Ist eines der beiden Register auf Null, so kann eine Entscheidung gefällt werden. Sind beide Register größer Null (+), so werden sie heruntergezählt.
Code-Beispiel für a <= b
h1 und h2 gleich Null wird vorausgesetzt
st ++ + -
tst a jmp (+4) tst b jmp (+9) jmp (+8) tst b jmp (+2) jmp (+6) dec a dec b inc h2 jmp (-11) inc h1 tst h2 jmp (+2) jmp (+5) dec h2 inc a inc b jmp (-6)
a ist Null 0+ + 00 + a ist größer Null ++ +0 - st h1 wird gesetzt Restaurierung von a und b
Je nach Bedingung ändern sich die rot gekennzeichneten Sprungdifferenzen, der Rest bleibt gleich. Hier könnte folgendes Dictionary nützlich sein.
d = {'==':(10,8,6),'!=':(9,9,5),'<':(9,9,6),'>':(10,9,5),'<=':(9,8,6),'>=':(10,8(falsch:9),5)}
d.get('<=')[2] liefert z.B. 6
Achtung: Zumindest in den Fällen '>':(10,9,5),'<=':(9,8,6) wird nach 'tst b a ist Null' zum Label '-' gesprungen. Dh. der Test ist unnötig und kann entfallen. Hier kann/muss optimiert werden. Vermutlich ist es doch besser, jede Bedingung einzeln zu behandeln. Je nach Bedingung ist es besser, mal mit a, mal mit b anzufangen.
10. Bedingungen der Form Variable-Operator-Zahl bzw. Zahl-Operator-Variable
Hier könnte man sich zunächst auf den Fall beschränken, dass die Zahl gleich Null ist.
10.1 a < 0 F ohne tst 10.2 a >= 0 W ohne tst 10.3 a <= 0 W bei a == 0 10.4 a == 0 W bei a == 0 10.5 a > 0 W bei a != 0 10.6 a != 0 W bei a != 0
Die ersten beiden Fälle benötigen keinen Test. Die restlichen zwei Fälle lassen sich mit einem einfachen tst a erledigen.
11. if-Anweisung
Eine Alternative der Form
if cond:
kette1
else:
kette2
#end
wird zu
tst h jmp (+2) jmp (+lk1+2) kette1 der Länge lk1 jmp (+lk2+1) kette2 der Länge lk2
übersetzt. Dabei ist h die von der Bedingung cond benannte Hilfsvariable.
Übersetzung bei einer Bedingung der Form 'v o n'
tst a jmp (+lk1+2) nein kette1 ja jmp (+lk2+1) kette2 tst a jmp (+2) ja jmp (+lk1+2) nein kette1 jmp (+lk2+1) kette2
12. while-Anweisung
Eine Schleife der Form
while cond:
kette
#end
wird zu
Auswertung von cond, Länge: ltest tst h jmp (+2) // in Bedingung zurücksetzen, Schleifenkörper, Rückspung zur Auswertung der Bedingung jmp (+lk+3) // hinter Schleifenkörper springen dec h // zuerst Bedingung zurücksetzen kette der Länge lk jmp(-(+lk+ltest+4)) // Rücksprung
übersetzt. Dabei ist h die von der Bedingung cond benannte Hilfsvariable.
Speicherverwaltung
Außer den Speicherzellen, die für vorkommenden Variablen gebraucht werden, werden auch dynamisch immer wieder Hilfsvariablen gebraucht. Der Speicherplatz für diese Hilfsvariablen kann nach dem Gebrauch auch wieder freigegeben werden. Es ist aber zu bedenken, dass der Code im Allgemeinen nicht in der Ausführungsreihenfolge generiert wird, sodass das Problem bei der Generierung nicht gelöst werden kann. Ein mögliches Vorgehen könnte so sein: Bei der Generierung werden immer neue Hilfsvariablen angefordert, dh. jeder Codeabschnitt hat seine eigenen Hilfsvariablen. Damit ergeben sich keine Abstimmungsprobleme aber der Speicherverbrauch wird unnötig groß. Jeder Codeabschnitt wird mit zusätzlichen Speicherallokierungsbefehlen begonnen und mit Freigabebefehlen beendet. Wenn diese Befehle nicht die 'Kettenlängen' beinflussen sollen, so kann man sie an den ersten und letzten Befehl der Kette 'anheften' indem man diese Befehle als ersten Eintrag einer Liste und die 'Speicherbefehle' als zweiten Eintrag speichert. Diese Befehle enthalten die jeweiligen Namen der Hilfsvariablen. Bei einem zweiten Lauf wird nun der Code von vorne her durchgegangen bis man auf einen Allokierungsbefehl (z.B. malloc __h7)) stößt. Jetzt wird in der Hilfsvariablentabelle nachgesehen, wie die erste freie Speicherzelle heißt (z.B. __h1), diese Zelle als benutzt markiert und in die Menge der jemals benutzten eingetragen. Dann wird der Allokierungsbefehl entfernt und bei den folgenden Befehlen der bisherige Name durch den neuen Namen ersetzt (hier __h1 statt __h7). Dieses Ersetzen kann dadurch geschehen, dass bei jedem inc-, dec- oder tst-Befehl in einem 'Ersetzungsdictionary' (z.B. ersetzt) nachgesehen wird, ob eine Ersetzung eingetragen ist. Das geht so bis man auf den zugeordneten Freigabebefehl (hier free __h7 stößt. Jetzt wird der Freigabebefehl entfernt, die belegte Variable als frei markiert und die Ersetzung aus dem Ersetzungsdictionary entfernt. Am Ende des Durchgangs sind alle Allokierungs- und Freigabebefehle entfernt und alle Hilfsvariablen haben eine möglichst niedrige Nummer. Die benötigten Hilfsvariablen ergeben sich aus der Menge der benutzten Zellen.
Tests
Alle Code-Schnipsel können bequem mit einem Interpreter getestet werden, der symbolische Adressen und relative Sprünge versteht.