Übersetzer für arithmetische Ausdrücke

Ein Übersetzer, der Programmtext in Maschinencode übersetzt, wird als Compiler bezeichnet. Aber du kannst auch andere Texte, die nach den Regeln einer Grammatik aufgebaut sind, in beliebige andere Ausgabeformate übersetzen. Im Folgenden übersetzt du einen beliebigen arithmetischen Ausdruck in seinen Wert, also zum Beispiel "1+2*3" in den Zahlenwert 7.

Übersetzer programmieren

Das Ganze nennt sich syntaxgesteuerte Übersetzung. Du programmierst also nicht einfach drauflos, sondern gehst systematisch vor. Dies erleichtert es dir, am Ende eine korrekte Implementierung zu erhalten.

Ausgangspunkt ist eine Grammatik.
Entsprechend dieser Grammatik programmierst du zuerst einen Parser.
Dann fügst du zu jeder Funktion bestimmte Übersetzungsaktionen hinzu.

Wenn du noch unsicher bist, was genau eine Grammatik ist, oder wenn du noch nicht weißt, wie du auf Basis einer Grammatik einen Parser programmierst, dann lies dir diese Artikel noch einmal durch.

Vom Parser zum Übersetzer

Den Parser programmierst du ja so, dass du für jedes Nichtterminalzeichen der Grammatik eine Funktion gleichen Namens schreibst. Eine solche Funktion gibt zunächst keinen Rückgabewert zurück, sondern sie arbeitet lediglich einen Teil des Eingabewortes ab.

Dies ändert sich, wenn du den Parser zu einem Übersetzer umprogrammierst. Du versiehst jede dieser Funktionen mit einem Rückgabewert. Wenn die Funktion ein bestimmtes Teilwort des Eingabewortes abgearbeitet hat, gibt sie das Ergebnis der Übersetzung dieses Teilwortes zurück.

Konkret arbeitest du die folgenden vier einfachen Schritte ab.

Du überlegst dir zunächst, was das Ziel der Übersetzung ist.
Du fertigst Kopien der Module Parser und ExprParser an und benennst sie in Compiler und ExprCompiler um.
Du änderst im Modul ExprCompiler jede Funktion, die einem Nichtterminalzeichen entspricht, so um, dass sie einen Rückgabewert liefert.
Du änderst im Modul Compiler die Funktion parse in die Funktion compile um, sodass sie einen Rückgabewert liefert.

Im Folgenden übersetzt du einen arithmetischen Ausdruck in seinen Zahlenwert. Das Programm basiert auf dem Parser, den du bereits programmiert und getestet hast.

Wenn du den Parser noch nicht programmiert hast, kannst du an dieser Stelle nicht weiterarbeiten.

Vom Modul ExprParser zum Modul ExprCompiler

Am besten fängst du unten an, bei der Funktion digit. Die Funktion digit arbeitet ja eine einzelne Ziffer ab, auf die sie im Eingabewort stößt. Folgerichtig gibst du den Zahlenwert dieser Ziffer als Rückgabewert der Funktion digit zurück.

Funktion digit

Du änderst also die bisherige Funktion digit folgendermaßen ab, indem du Return-Anweisungen einfügst, mit denen du den jeweiligen Zahlenwert zurückgibst.

def digit():
    if comes("0"):
        match("0")
        return 0
    elif comes("1"):
        match("1")
        return 1
    elif comes("2"):
        match("2")
        return 2
    elif comes("3"):
        match("3")
        return 3
    elif comes("4"):
        match("4")
        return 4
    elif comes("5"):
        match("5")
        return 5
    elif comes("6"):
        match("6")
        return 6
    elif comes("7"):
        match("7")
        return 7
    elif comes("8"):
        match("8")
        return 8
    elif comes("9"):
        match("9")
        return 9
    else:
        raise Exception("Ziffer erwartet")

Funktion number

Dann kommt die Funktion number an die Reihe. Zunächst soll number ja nur einstellige Zahlen abarbeiten und deren Wert zurückgeben. Du änderst die bisherige Funktion einfach so ab:

def number():
    return digit()

Das ist alles. Die Funktion number gibt den Wert zurück, den digit zurückgibt.

Funktion factor

So ähnlich machst du es bei der Funktion factor. Du gibst entweder den Wert zurück, den expr liefert oder den Wert, den number liefert. Da du aber die schließende Klammer hinter expr noch mit match(")") abarbeiten musst, kannst du nicht einfach return expr() schreiben, sondern du machst es so:

def factor():
    if comes("("):
        match("(")
        v=expr()
        match(")")
    else:
        v=number()
    return v

Funktion expr

Die Funktion expr änderst du in ähnlicher Weise ab:

def expr():
    v=term()
    while comes("+") or comes("-"):
        if comes("+"):
            match("+")
            v+=term()
        else:
            match("-")
            v-=term()
    return v

Du speicherst den Wert, den term() liefert, in der Variablen v. Und dann wiederholst du das Folgende:

Wenn du ein Pluszeichen abarbeitest, addierst du zu v den Wert, den der darauffolgende Term liefert,
und wenn du ein Minuszeichen abarbeitest, subtrahierst du von v den Wert, den der darauffolgende Term liefert.

Funktion term

Die Funktion term implementierst du ganz analog zur Funktion expr.

ExprCompiler noch einmal umbenennen

Damit hast du alle Funktionen, die der Grammatik entsprechen, in der Weise geändert, dass sie jeweils einen Wert zurückgeben. Und zwar denjenigen Wert, der genau dem jeweils abgearbeiteten Teilwort des Eingabewortes entspricht. Bei der Funktion expr ist dieses Teilwort das gesamte Eingabewort, da expr das Startsymbol der Grammatik ist.

Weil du Ausdrücke in ihren Wert übersetzt, benennst du am besten das Modul ExprCompiler noch einmal in ExprToValueCompiler um.

Python-Modul Compiler programmieren

Das Python-Modul Compiler erhältst du, indem du das Modul Parser kopierst und ein klein wenig umprogrammierst.

Du benötigst das Modul Compiler für jeden konkreten Übersetzer, so auch für den ExprToValueCompiler. Schreibe also als erste Zeile im Modul ExprToValueCompiler:

from Compiler import *

Funktion compile

Die wichtigste Funktion im Python-Modul Compiler ist die Funktion compile. Diese Funktion geht aus der bisherigen Funktion parse dadurch hervor, dass sie am Ende einen Wert zurückgibt, und zwar denjenigen Wert, den die Funktion startSymbol liefert. Nötig sind nur kleine Änderungen.

# Uebernimmt einen Eingabestring x und ruft das Startsymbol der
# Grammatik auf; erzeugt ggf. eine Fehlermeldung und bestimmt
# die Position des Fehlers im Eingabestring
def compile(x, startSymbol):
    global inputstring, originalinput, errormessage, errorposition
    inputstring=originalinput=x
    errormessage="ok"
    v=None
    try:
        v=startSymbol()    # arbeitet Eingabestring ab
        if inputstring!="":
            raise Exception("Zu viele Zeichen: "+inputstring)
    except Exception as e:
        errormessage=str(e)
    errorposition=len(originalinput)-len(inputstring)
    return v

Findest du die 3 kleinen Änderungen gegenüber der Funktion parse?

An den restlichen Funktionen im Modul Compiler ändert sich nichts.

Compiler ausprobieren

Im Hauptprogramm rufst du nun die Funktion compile auf und gibst den Wert, der als Ergebnis der Übersetzung herausgekommen ist, auf dem Bildschirm aus (in der Python-Version 2.7 lässt du die Klammern bei der Print-Anweisung weg).

# Hauptprogramm
if __name__=="__main__":
    # String uebersetzen mit expr als Startsymbol
    v=compile("1+2*3", expr)    
    showErrorPosition()
    print("Ergebnis:", v)

Wenn du nun das Programm startest, erhältst du als Ausgabe:

1+2*3
-----^
ok
Ergebnis: 7

Aufgaben

Probiere einmal verschiedene korrekte arithmetische Ausdrücke aus und überprüfe, ob dein Compiler richtig rechnet.

Ändere die Grammatik so ab, dass auch mehrstellige ganze Zahlen akzeptiert werden. Dazu änderst du die Produktion für number in der Weise, wie in der Aufgabe im Artikel Parser beschrieben. Implementiere anschließend die Funktion number. Überlege dir, wie du den Zahlenwert einer mehrstelligen Zahl hier am geschicktesten berechnest.

Ändere die Grammatik so ab, dass auch negative Vorzeichen berücksichtigt werden. Hierzu ergänzt du die Produktion für factor um $\textit {factor} = -\textit {factor}$ . Implementiere anschließend die Funktion factor neu.

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?