Station - Ein Code-Erzeuger für strukturierte MiniPython-Programme

Aufgabe des Code-Erzeugers

Der Code-Erzeuger hat die Aufgabe, strukturierte MiniPython-Programme in Programme einer (maschinennahen) Sprache zu übersetzen. Die Arbeitsweise des Code-Erzeugers soll am folgenden Beispiel-Programm verdeutlicht werden.

x = 9
y = 6
while x != y:
    if x <= y:
        y = y - x
    else:
        x = x - y
    #end
#end

Der Code-Erzeuger verarbeitet als Quellcode das zugehörige strukturierte MiniPython-Programm:

[
  ['=', ('VAR', 'x'), [('ZAHL', '9')]],
  ['=', ('VAR', 'y'), [('ZAHL', '6')]],
  ['while', ['!=', ('VAR', 'x'), ('VAR', 'y')],
    [
      ['if', ['<=', ('VAR', 'x'), ('VAR', 'y')],
        [
          ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('VAR', 'x')]]
        ],
        [
          ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
        ]
      ]
    ]
  ]
]

Aus diesem Qhellcode soll der Code-Erzeuger ein Bonsaiassembler-Programm erzeugen

0: tst 0
1: jmp 3
2: jmp 5
3: dec 0
4: jmp 0
5: inc 0
6: inc 0
7: inc 0
8: inc 0
9: inc 0
10: inc 0
11: inc 0
12: inc 0
13: inc 0
14: tst 1
15: jmp 17
16: jmp 19
17: dec 1
18: jmp 14
19: inc 1
20: inc 1
21: inc 1
22: inc 1
23: inc 1
24: inc 1
25: tst 2
26: jmp 28
27: jmp 30
28: dec 2
...
179: hlt
#0
#0
#0
#0
#0
#0
#0
#0
#0

Die erzeugung dieses Assemblercodes erfolgt (hier) in zwei Schritten. Zunächst wird ein Programm einer Hilfsassemblersprache erzeugt (s.u.).

tst x
jmp (+2)
jmp (+3)
dec x
jmp (-4)
inc x
inc x
inc x
inc x
inc x
inc x
inc x
inc x
inc x
tst y
jmp (+2)
jmp (+3)
dec y
jmp (-4)
inc y
inc y
inc y
inc y
inc y
inc y
tst _h0
jmp (+2)
jmp (+3)
dec _h0
...

Dieser Zwischencode wird anschließend in BonsaiAssembler-Code umgewandelt.

Die Assemblerhilfssprache

Der Befehlsumfang der Hilfsassemblersprache ist derselbe wie bei der Bonsai-Assemblersprache. Es werden nur die 5 Befehle inc, dec, jmp, tst und hlt benutzt.

Bei den Befehlen inc, dec und tst werden Variablenbezeichner statt Registeradressen benutzt. Jede Variable steht dabei für ein Register. Die genaue Adresse des Registers spielt vorerst noch keine Rolle.

Am Ende des Programms werden alle im Programm benutzten Variablen mit ihren Startwerten aufgelistet.

[x=0]
[y=0]
[p=0]
[_h0=0]

Mit dieser Notation wird angezeigt, welche Register im Programm verwendet werden und mit welchen Variablen auf die Registerwerte zugegriffen wird.

Im vorliegenden Beispiel wird z.B. das erste Register (mit einer noch zu vergebenden Adresse - z.B. der Adresse 0) von der Variablen x verwaltet. Der Anfangswert dieses Registers ist die Zahl 0.

Auch die Adressierung beim jmp-Befehl unterscheidet sich in der Hilfsassemblersprache von der BonsaiAssemblersprache.

Eine Angabe wie z.B. jmp (-5) bedeutet: Gehe 5 Zeilen im Programm zurück. Entsprechend bedeutet eine Angabe wie z.B. jmp (+5): Gehe 5 Zeilen im Programm weiter vorwärts. Die mit Klammern gekennzeichneten Adressen sind hier also relative Sprungadressen.

Durch die Verwendung relativer Sprungadressen müssen die einzelnen Befehle eines Hilfsassemblerprogramms nicht durchnummeriert werden.

Beachte, dass die Hilfsassemblersprache auch Kommentare (# ...) zulässt.

Die Arbeitsweise des Code-Erzeugers

Die Aufgabe des Code-Erzeugers ist es, die Bausteine eines strukturierten MiniPython-Programms mit Hilfe der Befehle der Hilfsassemblersprache zu modellieren. Hierzu werden Code-Schnipsel für die einzelnen Bausteine erzeugt (vgl. auch Erzeugung von Hilfsassembler-Code). Wir verdeutlichen dies anhand einfacher Beispiele

Wir betrachten zunächst Zuweisungen der Form a = b:

Die Übersetzung solcher Zuweisungen könnte nach folgendem Verfahren ablaufen.

{a: III; b: IIII}
eine Hilfsvariable h erzeugen
{a: III; b: IIII; h: }
Register a leeren
{a:  ; b: IIII; h: }
transportiere den Inhalt von Register b in Register a und das Hilfsregister h
{a: IIII; b: ; h: IIII}
transportiere den Inhalt von Register h zurück in Register b
{a: IIII; b: IIII; h: }

Das entsprechende Code-Schnipsel sieht dann so aus:

# c_zuw_a_gleich_b
# Parameter: a, b
# Hilfsvariable: h
# a = 0
tst a
jmp (+2)
jmp (+3)
dec a
jmp (-4)
# b -> a, h
tst b
jmp (+2)
jmp (+5)
dec b
inc a
inc h
jmp (-6)
# h -> b
tst h
jmp (+2)
jmp (+4)
dec h
inc b
jmp (-5)

Als nächstes betrachten wir Bedingungen der Form a != 0:

Das Ergebnis bei der Auswertung einer Bedingung ist einer der beiden Wahrheitswerte True und False. Dieses Ergebnis wird in ein Hilfsregister abgelegt und mit einer Hilfsvariablen zugänglich gemacht. Zur Codierung der Wahrheitswerte benutzen wir die Zuordnung True -> 1 und False -> 0. Zu beachten ist, dass die´Hilfsvariable h zunächst auf einen festen Anfangswert (hier: 0) initialisiert wird.

# c_bed_a_ungleich_null
# Parameter: a
# Hilfsvariable: h
# h = 0
tst h
jmp (+2)
jmp (+3)
dec h
jmp (-4)
# a != 0?
tst a
jmp (+2)
jmp (+2)
inc h

Etwas aufwendiger sind Code-schnipsel zu Fallunterscheidungen und Wiederholungen. Zur Verdeutlichung betrachten wir Wiederholungen der Form:

while [bed]:
    [anw]
end#

Mit bed wird hier die Bedingung beschrieben, mit anw die Anweisungssequenz des Schleifenkörpers.

Wir setzen voraus, dass bereits Assembler-Code für die Bedingung und für die Anweisungssequenz vorliegen. Mit c_bed wird der Assembler-Code für die Bedingung beschrieben, mit c_anw der Assembler-Code für die Anweisungssequenz.

Bei der Übersetzung einer Wiederholung werden jetzt die bereits existierenden Code-Schnipsel benutzt, um das Code-Schnipsel für die gesamte Wiederholungsanweisung zu erzeigen.

# c_while
# benutzt: c_bed, c_anw
# Hilfsvariable: h
# Code für die Bedingung; Ergebnis in Hilfsvariable h
c_bed
# Ergebnis testen
tst h
jmp (+2)
jmp (+(Länge(c_anw)+2)) # über den anw-Code
c_anw_true
jmp (-(Länge(c_anw)+Länge(c_bed)+3)) # zurück zum bed-Code
# h = 0
tst h
jmp (+2)
jmp (+3)
dec h
jmp (-4)

Implementierung des Code-Erzeugers

Der Code-Erzeuger wird durch ein Objekt der Klasse UebersetzerWhileList realisiert. Dieses Objekt verfügt insbesondere über eine Methode uebersetzen, die letztlich für die Erzeugung des Zielcodes zuständig ist. Die genauen Details können dem Quelltext uebersetzerWhileList.txt entnommen werden.

Testen lässt sich der Code-Erzeuger mit fogendem testprogramm:

from uebersetzerWhileList import *
from variablenzustand import *

# Testprogramm
quellcode = [
  ['=', ('VAR', 'x'), [('ZAHL', '9')]],
  ['=', ('VAR', 'y'), [('ZAHL', '6')]],
  ['while', ['!=', ('VAR', 'x'), ('VAR', 'y')],
    [
      ['if', ['<=', ('VAR', 'x'), ('VAR', 'y')],
        [
          ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('VAR', 'x')]]
        ],
        [
          ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
        ]
      ]
    ]
  ]
]
# Erzeugung der Objekte
variablenzustand = Variablenzustand()
codeerzeuger = UebersetzerWhileList(variablenzustand)
# Erzeugung des Zielcodes
codeerzeuger.setQuellcode(quellcode)
codeerzeuger.uebersetzen()
zielcode = codeerzeuger.getProgramm()
# Ausführung des Programms und Ausgabe der Zustände
print('Quellcode:')
print()
for zeile in quellcode:
    print(zeile)
print()
print('Zielcode:')
print()
for zeile in zielcode:
    print(zeile)

Aufgabe 1

Probiere das selbst einmal aus. Übersetze verschiedene strukturierte MiniPython-Programme.