HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material/Bonsai/Bonsai-Compiler/MiniPython-Compiler

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

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

Idee

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.

Code-Erzeugung

Vorläufiger Compiler

minipython.py, divmod1.py, boni.py