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

Aufgabe des Code-Erzeugers

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

x = 24
y = 15
d = x - y
while d != 0:
    if d > 0:
        x = x - y
    else:
        y = y - x
    #if
    d = x - y
#while

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

[
  ['=', ('VAR', 'x'), [('NAT', '24')]], 
  ['=', ('VAR', 'y'), [('NAT', '15')]], 
  ['=', ('VAR', 'd'), ['-', ('VAR', 'x'), ('VAR', 'y')]], 
  ['while', ['!=', ('VAR', 'd'), ('NAT', '0')], 
    [
      ['if', ['>', ('VAR', 'd'), ('NAT', '0')], 
        [
          ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
        ], 
        [
          ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('VAR', 'x')]]
        ]
      ], 
      ['=', ('VAR', 'd'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
    ]
  ]
]

Diesen Quellcode transformiert der Code-Erzeuger in folgenden Zielcode:

[
(None, ['=', ('VAR', 'x'), [('NAT', '24')]]),
(None, ['=', ('VAR', 'y'), [('NAT', '15')]]),
(None, ['=', ('VAR', 'd'), ['-', ('VAR', 'x'), ('VAR', 'y')]]),
('.L3', ['noop']),
(None, ['if', ['!=', ('VAR', 'd'), ('NAT', '0')], ['goto', '.L4'], ['goto', '.L5']]),
('.L4', ['noop']),
(None, ['if', ['>', ('VAR', 'd'), ('NAT', '0')], ['goto', '.L0'], ['goto', '.L1']]),
('.L0', ['noop']),
(None, ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]]),
(None, ['goto', '.L2']),
('.L1', ['noop']),
(None, ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('VAR', 'x')]]), ('.L2', ['noop']),
(None, ['=', ('VAR', 'd'), ['-', ('VAR', 'x'), ('VAR', 'y')]]),
(None, ['goto', '.L3']),
('.L5', ['noop'])
]

Der Zielcode stellt eine strukturierte Version des folgenden Goto-Programms dar:

x=24
y=15
d=x-y
label .L3
if d!=0:
    goto .L4
else:
    goto .L5
label .L4
if d>0:
    goto .L0
else:
    goto .L1
label .L0
x=x-y
goto .L2
label .L1
y=y-x
label .L2
d=x-y
goto .L3
label .L5

Die Codesprache MyGoto

Syntax und Semantik der Sprache Goto werden hier nur informell beschrieben.

MyGoto-Programme benutzen Sprunganweisungen, um Fallunterscheidungen und Wiederholungen zu modellieren. Es gibt verschiedene Typen von Anweisungen:

• Zuweisungen der Gestalt "Variable" = "Term"
• Festlegung von Sprungmarken der Gestalt label .L"Zahl"
• Sprungbefehle der Gestalt goto "Spungmarke"
• Bedingte Sprungbefehle der Gestalt if "Bedingung": goto "Spungmarke" else: goto "Sprungmarke"
• Passieranweisungen der Gestalt pass

Zuweisungen und Bedingungen dürfen dabei nur so wie in der Sprache MyWhile gebildet werden.

Bei der Ausführung von Goto-Programmen sind folgende Vorgaben zu beachten:

• Eine Zuweisung wird wie in der Sprache MyWhile ausgeführt. Als nächste Anweisung wird dann die in der nächsten Programmzeile ausgeführt.
• Bei einem Sprungbefehl der Gestalt goto "Spungmarke" wird die Ausführung mit der Zeile fortgesetzt, die die angegebenen Marke festlegt.
• Bei einem bedingten Sprungbefehl wird zunächst die Bedingung ausgewertet, bevor dann in Abhängigkeit des Ergebnisses der Sprung erfolgt.
• Eine Passieranweisung der Gestalt pass wird übergangen. Es wird also in der darauf folgenden Zeile weitergemacht.

Die Arbeitsweise des Code-Erzeugers

Die entscheidende Aufgabe des Code-Erzeugers ist es hier, Fallunterscheidungen und Wiederholungen mit Hilfe von goto-Sprunganweisungen zu modellieren. Wir verdeutlichen die Übersetzungsschablonen anhand einfacher Beispiele.

Fallunterscheidung:

x = 1
if x1 != 0:
    y = x
else:
    y = 0
#if

Die Kommentare illustrieren die Idee der Übersetzung.

x=1
if x1!=0:      # Auswertung der Bedingung
    goto .L0   # Sprung zum wahr-Fall
else:
    goto .L1   # Sprung zum falsch-Fall
label .L0      # wahr-Fall
y=x
goto .L2       # Sprung zum Ende der Fallunterscheidung
label .L1      # wahr-Fall
y=0
label .L2      # Ende der Fallunterscheidung

Wiederholung:

x = 5
while x != 0:
    x = x - 1
#while

Die Kommentare illustrieren die Idee der Übersetzung.

x=5
label .L0      # Beginn der Schleife
if x!=0:       # Auswertung der Bedingung
    goto .L1   # Sprung zum Schleifenkörper
else:
    goto .L2   # Sprung aus der Schleife
label .L1      # Beginn des Schleifenkörpers
x=x-1
goto .L0       # Sprung zum Beginn der schleife
label .L2      # Ende der Schleife

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.

class UebersetzerWhileList(object):
    def __init__(self):
        self.quellcode = None

    def setQuellcode(self, q):
        self.quellcode = q

    def uebersetzen(self):

        def c_programm(p):
            'programm : anweisungsfolge'
            return c_anweisungsfolge(p) 

        def c_anweisungsfolge(p):
            '''anweisungsfolge : anweisung anweisungsfolge
                               | anweisung'''
            if len(p) > 1:
                return c_anweisung(p[0]) + c_anweisungsfolge(p[1:])
            else:
                return c_anweisung(p[0])

        def c_anweisung(p):
            '''anweisung : VAR ZUW term
                         | PASS
                         | WHILE bedingung DP anweisungsfolge ENDWH
                         | IF bedingung DP anweisungsfolge ELSE DP anweisungsfolge ENDIF'''
            if p[0] == "=":
                return [(None, p)]
            elif p[0] == "pass":
                return [(None, ['noop'])]
            elif p[0] == 'while':
                ergebnis_true = c_anweisungsfolge(p[2])
                ergebnis_wh = [('.L' + str(self.zaehler), ['noop']), \
                               (None, ['if', p[1], \
                                                   ['goto', '.L' + str(self.zaehler+1)], \
                                                   ['goto', '.L' + str(self.zaehler+2)]]), \
                               ('.L' + str(self.zaehler+1), ['noop'])] + \
                               ergebnis_true + \
                              [(None, ['goto', '.L' + str(self.zaehler)]), \
                               ('.L' + str(self.zaehler+2), ['noop'])]
                self.zaehler = self.zaehler + 3
                return ergebnis_wh
            elif p[0] == 'if':
                ergebnis_true = c_anweisungsfolge(p[2])
                ergebnis_false = c_anweisungsfolge(p[3])
                ergebnis_if = [(None, ['if', p[1], \
                                                   ['goto', '.L' + str(self.zaehler)], \
                                                   ['goto', '.L' + str(self.zaehler+1)]]), \
                               ('.L' + str(self.zaehler), ['noop'])] + \
                               ergebnis_true + \
                               [(None, ['goto', '.L' + str(self.zaehler+2)])] + \
                               [('.L' + str(self.zaehler+1), ['noop'])]+ \
                               ergebnis_false + \
                               [('.L' + str(self.zaehler+2), ['noop'])]
                self.zaehler = self.zaehler + 3
                return ergebnis_if

        self.zaehler = 0
        if self.quellcode != None:
            return c_programm(self.quellcode)
        else:
            return []

Ein Objekt der Klasse UebersetzerWhileList kann also benutzt werden, um strukturierte While-Programme in strukturierte Goto-Programme zu übersetzen.

from uebersetzerWhileList import *

# Testprogramm
quellcode = [
  ['=', ('VAR', 'x'), [('ZAHL', '24')]], 
  ['=', ('VAR', 'y'), [('ZAHL', '15')]], 
  ['=', ('VAR', 'd'), ['-', ('VAR', 'x'), ('VAR', 'y')]], 
  ['while', ['!=', ('VAR', 'd'), ('ZAHL', '0')], 
    [
      ['if', ['>', ('VAR', 'd'), ('ZAHL', '0')], 
        [
          ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
        ], 
        [
          ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('VAR', 'x')]]
        ]
      ], 
      ['=', ('VAR', 'd'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
    ]
  ]
]
codeerzeuger = UebersetzerWhileList()
# Erzeugung des Zielcodes
codeerzeuger.setQuellcode(quellcode)
zielcode = codeerzeuger.uebersetzen()
# 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 MyWhile-Programme.