 |
|||
| HSG |
|
Quelltext-Datei aus MiniJava
public class add1
{
public static void main(String[] args)
{
int a = 12;
int b = 33;
while (b > 0)
{
b = b - 1;
a = a + 1;
};
System.out.println(a);
}
}
JFlap-Grammatik
Startsymbol: S
Token, terminale Symbole: p public-Zeile , i int , w while, { , } , v Variablenname , + , - , ( , ) , > , n , ;
nonterminale Symbole: S Start, K Befehlskette, B Befehl, I Inc, D Dec, T Tst, Z Zuweisung
Produktionen:
S->p{p{K}}
K->KB
K->
B->I
B->D
B->T
B->Z
I->v=v+n;
D->v=v-n;
T->w(v>n){K};
Z->iv=n;
Testeingabe
p{p{iv=n;iv=n;w(v>n){v=v-n;v=v+n;};}}
Abstrakter Syntax-Baum
Zunächst baut man mit ply Lexer und Parser java2bon0.py und lässt sich den abstrakten Syntax-Baum AST anzeigen.
['S', 'public class add1\n', '{', 'public static void main(String[] args)\n ', '{',
['K', ['B', ['Z', 'int', 'a', '=', 12, ';']], ['K', ['B', ['Z', 'int', 'b', '=', 33, ';']],
['K', ['B', ['T', 'while', '(', 'b', '>', 0, ')', '{', ['K', ['B', ['D', 'b', '=', 'b', '-', 1, ';']],
['K', ['B', ['I', 'a', '=', 'a', '+', 1, ';']], ['K']]], '}', ';']], ['K']]]],
'}', '}']
Eine Rekonstruktion des Baumes ist leicht möglich, wenn man bedenkt, dass jede Liste als ersten Eintrag den Knotentyp und dann die Unterknoten hat.
Code-Erzeugung
Eine mögliche Idee ist es, jede Produktion soviel Code erzeugen zu lassen, wie es bei der Reduktion der rechten Seite möglich ist. Diese Code-Teile könnten z.B. als Liste von Befehlen realisiert werden. Bisher erzeugte Code-Teile werden dann von Produktion zu Produktion weitergereicht oder erweitert. Das Vorgehen soll nun an Beispielen erläutert werden.
Leere Kette, Zuweisung, Kette aus Kette und Befehl
Eine leere Kette wird sich in der Produktion schlicht als
p[0] = []
widerspiegeln. Das heißt, dieser nonterminale Knoten wird zum weiteren Aufbau der Liste der Befehle nur eine leere Liste beisteuern. Ein Zuweisungsknoten Z trägt zwar zur Befehlsliste nichts direkt bei, muss aber einen Eintrag in die Symboltabelle auslösen. Die Symboltabelle ist eine Liste mit den Tripeln (VariablenNummer,VariablenName,VariablenWert).
p[0] = [] global vz, symtab vz = vz + 1 symtab.append((vz,p[2],p[4]))
Die Produktion B : Z reicht die Liste aus Z an den B-Knoten weiter. In diesem Spezialfall ist diese Liste leer. Die Produktion K : K B verkettet die empfangenen Listen.
p[0] = p[1]+p[2]
Inc und Dec
Ein Inc-Knoten I führt zu einer Befehlsliste der Länge 1. Als Adresse wird zunächst der Variablenname eingetragen. Ein Dec-Knoten D wird analog behandelt.
p[0] = ['inc'+p[1]]
While
Ein T-Knoten zur while-Schleife verlangt eine aufwändigere Behandlung. Zunächst mache man sich klar, dass der Knoten K eine Befehlskette einer bestimmten Länge lk enthält. Der Aufbau dieser Kette spielt dabei keine Rolle.
Das Hinzufügen der Befehle vor und hinter der Kette dürfte einleuchten. Es bleibt das Problem, dass die Werte der Labels (Zeilennummern) zum Zeitpunkt der Erstellung der Befehlsliste nicht bekannt sind. Hier hilft die Idee der relativen Sprünge.
hlt
Beim Erreichen des Startknotens wird schließlich noch ein hlt-Befehl angehängt. Die Befehlsliste code0 sieht jetzt so aus:
['tstb', 'jmp(2)', 'jmp(4)', 'decb', 'inca', 'jmp(-5)', 'hlt']
Einarbeitung der Symboltabelle, Ersetzen der relativen Sprünge durch absolute
Die Befehlsliste code0 ist nun vollständig. Es müssen aber noch die Variablennamen durch die Registernummern und die relativen Sprünge durch absolute Sprünge ersetzt werden.
code = []
for i in range(len(code0)):
bef = code0[i]
if bef[0:3] == 'jmp':
adr = str(1+i+int(bef[4:-1])) # bon-Zeilen ab 1
if len(adr) == 1:
adr = ' '+adr
code.append('jmp'+adr)
elif bef[0:3] == 'hlt':
code.append('hlt')
else:
adr = str([x[0] for x in symtab if x[1] == bef[3:]][0])
if len(adr) == 1:
adr = ' '+adr
code.append(bef[0:3]+adr)
Die Befehlsliste code sieht jetzt so aus:
['tst 2', 'jmp 4', 'jmp 7', 'dec 2', 'inc 1', 'jmp 1', 'hlt']
Erzeugen der Ausgabedatei
Soll das alte *.bon-Format erreicht werden, so ist ein bisschen Nacharbeit nötig. Die nötigen Informationen wurden dabei mit list comprehensions aus der Symboltabelle 'gefischt'.
ausgabename = dateiname.split('.')[0]+'.bon'
datei = open(ausgabename,'w')
for bef in code:
datei.write(bef+'\r\n')
for i in range(1,vz+1):
datei.write('# '+str([x[2] for x in symtab if x[0] == i][0])+'\r\n')
for i in range(1,vz+1):
(n,w) = [(x[1],x[2]) for x in symtab if x[0] == i][0]
datei.write('; '+n+' = '+str(w)+'\r\n')
datei.close()
Quelltexte
Weitere Testdatei
public class mul1
{
public static void main(String[] args)
{
int a = 13;
int b = 17;
int p = 0;
int h = 0;
while (b > 0)
{
while (a > 0) {
a = a - 1;
p = p + 1;
h = h + 1;
};
while (h > 0) {
h = h - 1;
a = a + 1;
};
b = b - 1;
};
System.out.println(p);
}
}