 |
|||
| HSG |
|
Quelltext-Dateien aus MiniPython
Divmod
a = 23
b = 5
q = 0
r = a
while r>=b:
r = r-b
q = q+1
#end
print(q)
print(r)
divmod1.py,divmod.c,divmod.pas
Wurzel
n = 20000
w = 0
u = 1
while n >= u:
n = n-u
u = u+2
w = w+1
#end
print(w)
Vergleich
a = 3
b = 2
c = 1
x = a
y = b
z = c
if x > y:
h = x
x = y
y = h
else:
pass
#end
if x > z:
h = x
x = z
z = h
else:
pass
#end
if y > z:
h = y
y = z
z = h
else:
pass
#end
print(a,b,c)
print(x,y,z)
JFlap-Grammatik
Startsymbol: S
Token, terminale Symbole: v Variablenname, =, n Zahl, w while, x #end, o Vergleichsoperator, :, +, -, i if, e else, p pass, z print-Zeile (wird ignoriert)
nonterminale Symbole: S Start, K Befehlskette, B Befehl, W While-Anweisung, F If-Anweisung, Z Zuweisung, A Ausdruck, C Bedingung
Produktionen:
S->K K->KB K-> B->W B->F B->Z B->p W->wC:Kx F->iC:Ke:Kx C->vov C->von C->nov Z->v=A A->n A->v A->v+n A->v-n A->v+v A->v-v
Testeingaben
v=nv=nv=vv=nwvov:v=v-vv=v+nx v=nv=nv=nwvov:v=v-vv=v+nv=v+nx v=nv=nv=nv=vv=vv=vivov:v=vv=vv=ve:pxivov:v=vv=vv=ve:pxivov:v=vv=vv=ve:px
Lexer und Parser mit PLY
python2bon0.py, python2bon1.py
Codeerzeugung
Als Zielsprache soll Bonsai-Assembler verwendet werden. Für die grundsätzlichen Ideen wird auf diesen MiniJava-Compiler verwiesen.
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.
Zuweisung
a = n, n natürliche Zahl
Es sind die Fälle 'initiale Zuweisung' und 'Zuweisung einer Konstanten' zu unterscheiden. Ist a noch nicht in der Symboltabelle, 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 Symboltabelle erzeugt. Sollte die Variable a in der Symboltabelle bereits existieren, so wird sie zunächst auf Null gesetzt
tst a jmp (+2) jmp (+3) dec a jmp (-4)
und dann n-mal 'inc a' angehängt.
Dieses spezielle Verhalten ist vom Programmierer zu bedenken.
a = a + 1
a = a + 1 wird direkt zu
inc a
a = a + n, n natürliche Zahl
a = a + 5 wird zu
inc a inc a inc a inc a inc a
a = b
tst a a auf Null setzen
jmp (+2)
jmp (+3)
dec a
jmp (-4)
tst b von b auf a 'umfüllen', h wird als Null vorausgesetzt
jmp (+2)
jmp (+5)
dec b
inc a *
inc h
jmp (-6)
tst h restaurieren von b
jmp (+2)
jmp (+4)
dec h
inc b
jmp (-5)
h ist am Ende 0
a = a + b bzw. a = a - b
Der Code ist entspricht a = b, wobei der erste Teil entfällt. Im Fall a = a - b steht an der Stelle * statt inc a dec a.
a = b + c
a = b + c kann durch die Folge a = b, a = a + c ersetzt werden.
Bedingung, 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 a ist Null jmp (+9) 0+ + jmp (+8) 00 + tst b a ist größer Null jmp (+2) ++ jmp (+6) +0 - ++ dec a dec b inc h2 jmp (-11) st + inc h1 h1 wird gesetzt - tst h2 Restaurierung von a und b jmp (+2) jmp (+5) dec h2 inc a inc b jmp (-6)
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,9,5)}
d.get('<=')[2] liefert z.B. 6
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.
a < 0 F ohne tst a >= 0 W ohne tst a <= 0 W bei a == 0 a == 0 W bei a == 0 a > 0 W bei a != 0 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.
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
while-Anweisung
Eine Schleife der Form
while cond:
kette
#end
wird zu
tst h jmp (+2) jmp (+lk+2) kette der Länge lk jmp(-(+lk+3))
übersetzt. Dabei ist h die von der Bedingung cond benannte Hilfsvariable.
Alle Code-Schnipsel können bequem mit einem Interpreter getestet werden, der symbolische Adressen und relative Sprünge versteht.
Versionen
Version 6 übersetzt oben angeführte Beispiele anscheinend richtig. Getestet wurde durch Ausführen der erzeugten Bonsai-Programme durch einen Bonsai-Interpreter.
python2bon0.py, python2bon1.py, python2bon2.py, python2bon3.py, python2bon4.py, python2bon5.py, python2bon6.py