 |
|||
| HSG |
|
Beispiel einer schematischen Übersetzung
Am Beispiel eines einfachen Multiplikationsprogramms
a = 13
b = 17
p = 0
while b > 0:
p = p + a
b = b - 1
#end
print(a,b,p)
sollen die wesentlichen Schritte einer schematischen Übersetzung erläutert werden.
Der Scanner hat zunächst die Token (VAR,'a'), ('=','='), (NUM,13), (VAR,'b') geliefert, bevor der Parser sich entschieden hat, welche rechte Seite reduziert werden soll. Er hat dann eine Zuweisung einer Konstanten zu einer Variablen entdeckt. Diese Variable wird nun in der Variablentabelle (oft auch Symboltabelle) gesucht. Da man sie nicht findet, wird sie eingetragen und die Zuweisung als initiale Zuweisung (Schema 2) behandelt, die zu keiner Code-Erzeugung führt. Entsprechend werden die nächsten zwei Zuweisungen behandelt. Die Variablentabelle sieht jetzt so aus:
1 a 13 2 b 17 3 p 0
Als weitere grammatische Struktur wird eine while-Schleife erkannt. Als Unterstruktur gibt es eine Bedingung und einen Schleifenkörper. Der Schleifenkörper ist dabei eine Kette von Befehlen. Genau genommen kann der Parser natürlich erst die Schleife entdecken, wenn eine gültige Bedingung und eine gültige Befehlskette vorliegt. Die Bedingung ist vom Typ 10.5. Die Befehlskette besteht aus einer Zuweisung vom Typ 6 und einer Zuweisung vom Typ 3-.
Da die print-Anweisung ignoriert wird, kann man an das Zusammenbauen gehen:
Bedingung: kein spezieller Code nötig, Länge: 0, Bedingungsvariable b
Schleife: tst h , formal h wird zu aktuell b, kurz: h --> b
jmp (+2)
jmp (+lk+2)
kette der Länge lk, lk zunächst nicht bekannt
jmp(-(+lk+3))
Kette: Typ 6 , Länge: 13, a --> p, b --> a, h --> __h1 (nächste freie Hilfsvariable)
Typ 3- , Länge: 1 , a --> b
einkopiert: formal durch aktuell ersetzt
tst b tst a
jmp (+2) jmp (+2)
jmp (+5) jmp (+5)
dec b dec a
inc a inc p
inc h inc __h1
jmp (-6) jmp (-6)
tst h tst __h1
jmp (+2) jmp (+2)
jmp (+4) jmp (+4)
dec h dec __h1
inc b inc a
jmp (-5) jmp (-5)
dec a dec b
Die Kette kann nun in die Schleife einmontiert werden:
tst b
jmp (+2)
jmp (+14+2) jmp (+16)
tst a
jmp (+2)
jmp (+5)
dec a
inc p
inc __h1
jmp (-6)
tst __h1
jmp (+2)
jmp (+4)
dec __h1
inc a
jmp (-5)
dec b
jmp (-(14+3)) jmp(-17)
Mit der Einführung von Zeilennummern können die relativen Sprünge aufgelöst werden.
1 tst b 2 jmp (+2) 4 3 jmp (+16) 19 4 tst a 5 jmp (+2) 7 6 jmp (+5) 11 7 dec a 8 inc p 9 inc __h1 10 jmp (-6) 4 11 tst __h1 12 jmp (+2) 14 13 jmp (+4) 17 14 dec __h1 15 inc a 16 jmp (-5) 11 17 dec b 18 jmp(-17) 1 19
Jetzt müssen nur noch die symbolischen Variablennummern anhand der Variablentabelle ersetzt werden.
a = 1 b = 2 p = 3 __h1 = 4 1 tst 2 2 jmp 4 3 jmp 19 4 tst 1 5 jmp 7 6 jmp 11 7 dec 1 8 inc 3 9 inc 4 10 jmp 4 11 tst 4 12 jmp 14 13 jmp 17 14 dec 4 15 inc 1 16 jmp 11 17 dec 2 18 jmp 1 19 hlt ergänzt
Test der Überlegungen durch Compiler und Interpreter
mk@x2:~/Arbeitsfläche/Technotag2012$ python3 mpc.py m0.py|cat -n
1 tst 2
2 jmp 4
3 jmp 19
4 tst 1
5 jmp 7
6 jmp 11
7 dec 1
8 inc 3
9 inc 4
10 jmp 4
11 tst 4
12 jmp 14
13 jmp 17
14 dec 4
15 inc 1
16 jmp 11
17 dec 2
18 jmp 1
19 hlt
20 # 13 a
21 # 17 b
22 # 0 p
23 # 0 __h1
mk@x2:~/Arbeitsfläche/Technotag2012$ python3 mpc.py m0.py|python3 bi.py
a = 13 , b = 17 , p = 0 , __h1 = 0
663 inc
459 dec
953 jmp
0 jmp()
494 tst
1 hlt
2570 gesamt
a = 13 , b = 0 , p = 221 , __h1 = 0