Station - Ein Interpreter für strukturierte MyWhile-Programme

Aufgabe des Interpreters

Aufgabe des Interpretes ist es, strukturierte MyWhile-Programme (Schritt für Schritt) auszuführen.

Die Arbeitsweise des Interpreters soll am dolgenden Beispiel-Programm verdeutlicht werden.

[
  ['=', ('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')]]
    ]
  ]
]

Der Interpreter transformiert jeweils das noch auszuführende Restprogramm und den aktuellen Variablenzustand:

Restprogramm:
[
  ['=', ('VAR', 'x'), [('NAT', '24')]], 
  ...
]
Variablenzustand:
{}

==================================================================

Restprogramm:
[
  ['=', ('VAR', 'y'), [('NAT', '15')]], 
  ...
]
Variablenzustand:
{'x' -> 24, 'y' -> 15}

==================================================================

Restprogramm:
[
  ['=', ('VAR', 'd'), ['-', ('VAR', 'x'), ('VAR', 'y')]], 
  ...
]
Variablenzustand:
{'x' -> 24, 'y' -> 15, 'd' -> 9}

==================================================================

Restprogramm:
[
  ['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')]]
    ]
  ]
]
Variablenzustand:
{'x' -> 24, 'y' -> 15, 'd' -> 9}

======================= Bedingung wahr ===========================

Restprogramm:
[
  ['if', ['>', ('VAR', 'd'), ('NAT', '0')], 
    [
      ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]]
    ], 
    [
      ['=', ('VAR', 'y'), ['-', ('VAR', 'y'), ('VAR', 'x')]]
    ]
  ], 
  ['=', ('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')]]
    ]
  ]
]
Variablenzustand:
{'x' -> 24, 'y' -> 15, 'd' -> 9}

======================= Bedingung wahr ===========================

Restprogramm:
[
  ['=', ('VAR', 'x'), ['-', ('VAR', 'x'), ('VAR', 'y')]],
  ['=', ('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')]]
    ]
  ]
]
Variablenzustand:
{'x' -> 24, 'y' -> 15, 'd' -> 9}

==================================================================

Restprogramm:
[
  ['=', ('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')]]
    ]
  ]
]
Variablenzustand:
{'x' -> 9, 'y' -> 15, 'd' -> 9}

==================================================================

...

==================================================================

Restprogramm:
[
  ['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')]]
    ]
  ]
]
Variablenzustand:
{'x' -> 3, 'y' -> 3, 'd' -> 0}

====================== Bedingung flasch ==========================

Restprogramm:
[
]
Variablenzustand:
{'x' -> 3, 'y' -> 3, 'd' -> 0}

Alles klar?

Implementierung des Interpreters

Zur Verwaltung des Variablenzustans wird ein Objekt der Klasse Variablenzustand benutzt. Dieses Objekt stellt Operationen bereit, mit denen ein Variablenwert ermittelt und auch ein Variablenwert neu gesetzt werden kann.

class Variablenzustand(object):
    def __init__(self):
        self.variablen = {}

    def initVariablen(self):
        self.variablen = {}

    def getVariable(self, bezeichner):
        return self.variablen[bezeichner]

    def setVariable(self, bezeichner, wert):
        self.variablen[bezeichner] = wert

Der Interpreter wird durch ein Objekt der Klasse InterpreterWhileList realisiert. Dieses Objekt verfügt insbesondere über eine Methode anweisungAusfuehren, die letztlich für das Auswerten von Anweisungen zuständig ist.

class InterpreterWhileList(object):
    def __init__(self, v):
        self.programm = None
        self.variablenzustand = v

    def setProgramm(self, p):
        self.programm = p

    def getProgramm(self):
        return self.programm

    def getVariablenzustand(self):
        return self.variablenzustand

    def anweisungAusfuehren(self):
        if self.programm != []:
            anweisung = self.programm[0]
            bezeichner = anweisung[0]
            if bezeichner == "=":
                self.verarbeiteZuweisung(anweisung)
                self.programm = self.programm[1:]
            if bezeichner == "pass":
                self.programm = self.programm[1:]
            elif bezeichner == "while":
                bedingung = anweisung[1]
                if self.verarbeiteBedingung(bedingung):
                    self.programm = anweisung[2] + self.programm
                else:
                    self.programm = self.programm[1:]
            elif bezeichner == "if":
                bedingung = anweisung[1]
                if self.verarbeiteBedingung(bedingung):
                    self.programm = anweisung[2] + self.programm[1:]
                else:
                    self.programm = anweisung[3] + self.programm[1:]

    def verarbeiteZuweisung(self, anweisung):
        variable = anweisung[1][1]
        term = anweisung[2]
        self.variablenzustand.setVariable(variable, self.wertTerm(term))

    def wertOperand(self, operand):
        if operand[0] == "ZAHL":
            return int(operand[1])
        elif operand[0] == "VAR":
            return self.variablenzustand.getVariable(operand[1])

    def wertTerm(self, term):
        if len(term) == 1:
            return self.wertOperand(term[0])
        else:
            wertOperand1 = self.wertOperand(term[1])
            wertOperand2 = self.wertOperand(term[2])
            op = term[0]
            if op == "+":
                return wertOperand1 + wertOperand2
            elif op == "-":
                return wertOperand1 - wertOperand2
                
    def verarbeiteBedingung(self, bedingung):
        wertOperand1 = self.wertOperand(bedingung[1])
        wertOperand2 = self.wertOperand(bedingung[2])
        rel = bedingung[0]
        if rel == "!=":
            return (wertOperand1 != wertOperand2)
        elif rel == ">":
            return (wertOperand1 > wertOperand2)
        elif rel == "<":
            return (wertOperand1 < wertOperand2)
        elif rel == "==":
            return (wertOperand1 == wertOperand2)

Objekte der vorgestellten Klassen können jetzt direkt genutzt werden, um strukturierte MyWhile-Programme auszuführen.

from interpreterWhileList import *
from variablenzustand import *

# Testprogramm
programm = [
  ['=', ('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')]]
    ]
  ]
]

# Erzeugung des Interpreters
variablenzustand = Variablenzustand()
interpreter = InterpreterWhileList(variablenzustand)
# Initialisierung des Programms
interpreter.setProgramm(programm)

# Ausführung des Programms und Ausgabe der Zustände
print('Restprogramm:')
print(interpreter.programm)
print('Variablenzustand')
print(variablenzustand.variablen)
print('---------------------------')
while interpreter.getProgramm() != []:
    interpreter.anweisungAusfuehren()
    print('Restprogramm:')
    print(interpreter.programm)
    print('Variablenzustand')
    print(variablenzustand.variablen)
    print('---------------------------')

Aufgabe 1

Probiere das selbst einmal aus. Teste verschiedene strukturierte MyWhile-Programme.