Parser für arithmetische Ausdrücke

Ein Parser analysiert die Syntax eines Eingabewortes anhand einer vorgegebenen Grammatik.

Parser programmieren

Um einen Parser für eine kontextfreie Grammatik zu programmieren, brauchst du "nur" die folgenden beiden Schritte auszuführen. "Nur" deswegen, weil das Konzept sehr einfach ist – die Anführungszeichen deswegen, weil letztlich doch einiges an Schreibarbeit zusammenkommt.

Für jede Produktion der Grammatik schreibst du eine Funktion; du benennst die Funktion genauso wie das Nichtterminalzeichen auf der linken Seite der Produktion.
Im Funktionskörper realisierst du die rechte Seite der jeweiligen Produktion, und zwar rufst du bei jedem dort vorkommenden Nichtterminalzeichen die zugehörige Funktion auf, und bei jedem vorkommenden Terminalzeichen rufst du die Funktion match auf.

Die Funktion match arbeitet ein Zeichen vom Anfang des Eingabewortes ab. Auf diese Weise wird das Eingabewort kürzer und kürzer – wenn es am Ende leer ist, hast du das Eingabewort erkannt.

Für die angegebene Grammatik der arithmetischen Ausdrücke brauchst du die Funktionen expr, term, factor, number und digit. Was du im jeweiligen Funktionskörper programmierst, richtet sich nach den entsprechenden rechten Seiten der Produktionen.

Produktionen implementieren

Der einfachste Fall liegt bei der Produktion für number vor. Die Produktion lautet

$\textit{number}\rightarrow \textit{digit}$

Im Funktionskörper der Funktion number rufst du also lediglich die Funktion digit auf.

def number():
    digit()

Das ist alles. Die Funktion digit kümmert sich um den Rest.

Wenn Alternativen auf der rechten Seite einer Produktion vorkommen, wie etwa bei der Produktion

$\textit {factor}\rightarrow (\textit {expr})~|~\textit {number}$

dann behandelst du diese mit If-Else-Anweisungen. Du führst im Funktionskörper eine Fallunterscheidung durch: Wenn das verbliebene Eingabewort mit einer öffnenden Klammer beginnt, arbeitest du (expr) ab, ansonsten arbeitest du number ab.

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

Welche der beiden Alternativen du wählst, entscheidest du also nach dem ersten Zeichen des verbliebenen Eingabewortes: Ist dieses Zeichen eine öffnende Klammer, wählst du die erste Alternative, ansonsten die zweite.

Die erste Alternative enthält zunächst einen Aufruf der Funktion match, um die öffnende Klammer abzuarbeiten, dann einen Aufruf der Funktion expr, und dann wieder einen Aufruf der Funktion match, um die schließende Klammerabzuarbeiten. Die zweite Alternative besteht hingegen nur aus einem Aufruf der Funktion number.

Wenn eine Iteration, also ein $^*$ -Ausdruck, auf der rechten Seite einer Produktion vorkommt, wie etwa bei der Produktion

$\textit{expr}\rightarrow\textit{term}~(+\textit{term}~|-\textit{term})^*$

dann behandelst du die Iteration mit einer While-Schleife. Bei dieser Produktion ist innerhalb der While-Schleife noch eine Fallunterscheidung nötig.

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

Genau wie es die Produktion der Grammatik vorgibt, rufst du im Funktionskörper der Funktion expr zunächst die Funktion term auf. Die Funktion term arbeitet diejenigen Zeichen am Anfang des Eingabewortes ab, die einem Term entsprechen. Dann implementierst du die Iteration durch eine While-Schleife. Du durchläufst die While-Schleife so lange, wie im jeweils verbliebenen Eingabewort ein Plus- oder ein Minus-Zeichen kommt. Innerhalb der While-Schleife führst du eine Fallunterscheidung durch: Je nachdem, ob ein Plus- oder ein Minus-Zeichen kommt, arbeitest du dieses mit der Funktion match ab und rufst anschließend, wie die Produktion der Grammatik es vorgibt, die Funktion term auf. Das ist alles – die Funktion term kümmert sich um den Rest.

Die Funktion term implementierst du ganz analog zur Funktion expr. Die Produktion für term lautet:

$\textit {term} \rightarrow \textit {factor} ~(* \textit {factor} ~|~ / \textit {factor})^*$

Achte bitte darauf, dass du jede vorgegebene Produktion der Grammatik exakt auf diese Weise implementierst. Führe in deiner Implementierung keine Optimierungen durch! Überführe die Produktion rein mechanisch in dein Programm, sozusagen "ohne nachzudenken". Es ist wichtig, dass deine Implementierung exakt die zugehörige Produktion wiedergibt – nur so ist die Korrektheit der Implementierung gesichert.

Die Funktion digit ist etwas mühsam zu implementieren, weil sie viele Alternativen enthält, aber mit Copy-and-Paste hast du dies schnell erledigt.

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

Damit hast du alle Funktionen, die der Grammatik entsprechen, beisammen. Am besten schreibst du diese Funktionen in ein Python-Modul ExprParser.

Es fehlt noch das Drumherum. Dieses Drumherum ist für alle Grammatiken gleich, daher schreibst du dies in ein eigenes Python-Modul Parser. Das Modul Parser importierst du in jeder konkreten Parser-Implementierung, zum Beispiel in ExprParser. Du schreibst dort also als erste Zeile

from Parser import *

Python-Modul Parser

Funktion parse

Die wichtigste Funktion im Python-Modul Parser ist die Funktion parse.

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

Du übergibst der Funktion parse als Parameter x den String, der geparst werden soll, zum Beispiel den arithmetischen Ausdruck 2+3*4. Dieser String stellt das Eingabewort dar; er wird in den globalen Variablen inputstring und originalinput gespeichert. Während der String inputstring beim Parsen abgearbeitet wird, behält der String originalinput das ursprüngliche Eingabewort.

Globale Variablen sind Variablen, auf die in allen Funktionen zugegriffen werden kann. Sie werden in der Programmiersprache Python durch global gekennzeichnet.

Weitere globale Variablen sind errormessage und errorposition. Denn es kann vorkommen, dass das Eingabewort keinen korrekten arithmetischen Ausdruck nach den Regeln der Grammatik darstellt. Wenn du dies beim Parsen erkennst, löst du eine Exception aus und das Programm bricht ab. Den entsprechenden Fehler vermerkst du in der Variablen errormessage. Die Stelle im Eingabewort, an welcher der Fehler aufgetreten ist, speicherst du später in der Variablen errorposition.

Nun kommt das Wichtigste: Du rufst diejenige Funktion auf, die dem Startsymbol der Grammatik entspricht. Welche Funktion dies ist, übergibst du der Funktion parse im Parameter startSymbol, also beispielsweise die Funktion expr. Dieser Parameter enthält also einen Funktionsnamen – in Python ist es möglich, Funktionsnamen als Parameter zu übergeben.

Die Funktion startSymbol, also konkret beispielsweise die Funktion expr, arbeitet nun das Eingabewort ab. Wichtig ist dabei, zu überprüfen, ob am Ende das Eingabewort leer ist oder ob noch Zeichen übrig sind. Wenn noch Zeichen übrig sind, wird eine Exception ausgelöst.

Dieser Teil des Programms ist von einem Try-Catch-Block eingerahmt. Denn wenn beim Parsen eine Exception ausgelöst wird oder wenn das Eingabewort am Ende nicht leer ist und hierdurch eine Exception ausgelöst wird, bricht das Programm ab. Im Catch-Block fängst du die Exception ein und wertest sie aus – hier indem du die Fehlermeldung in der globalen Variablen errormessage speicherst.

Zum Schluss bestimmst du noch die Position des Fehlers anhand der Längen des zum Teil abgearbeiteten Eingabewortes inputstring und des ursprünglichen ganzen Eingabewortes originalinput.

In der Funktion parse hast du drei Elemente der höheren Programmierkunst kennengelernt:

globale Variablen benutzen,
einen Funktionsnamen als Parameter einer Funktion übergeben,
eine Exception auslösen und einfangen.

Funktionen comes und match

Es fehlen jetzt nur noch zwei Funktionen: die Funktion comes und die Funktion match.

Mit der Funktion comes überprüfst du, ob ein bestimmter String x am Anfang des verbliebenen Eingabewortes steht.

# liefert true, wenn das verbliebene Eingabewort mit x anfaengt
def comes(x):
    global inputstring
    return inputstring.startswith(x)

Mit der Funktion match überprüfst du, ob das verbliebene Eingabewort mit einem String x beginnt – wenn ja, entfernst du diesen String vom Anfang des Eingabewortes, wenn nein, löst du eine Exception aus.

# Wenn das verbliebene Eingabewort mit String x beginnt,
# dann wird der String x vom Anfang des Eingabewortes
# entfernt. Anderenfalls wird eine Exception ausgeloest
def match(x):
    if comes(x):
        # Laenge von x bestimmen und entsprechend
        # viele Zeichen vom Eingabestring abarbeiten
        consume(len(x))
    else:
        raise Exception("Erwartet: "+x)

Mit der Funktion consume entfernst du eine bestimmte Anzahl von Zeichen vom Anfang des Eingabewortes.

# entfernt die ersten k Zeichen vom Eingabewort
def consume(k=1):
    global inputstring
    inputstring=inputstring[k:]

Parser ausprobieren

Ob das Ganze funktioniert, überprüfst du, indem du im Modul ExprParser ein entsprechendes Hauptprogramm schreibst.

# Hauptprogramm
if __name__=="__main__":
    parse("1+2*3", expr)    # String parsen mit expr als Startsymbol
    showErrorPosition()

Die hier verwendete Funktion showErrorPosition bringst du noch schnell im Modul Parser unter:

def showErrorPosition():
    global originalinput, errorposition, errormessage
    s=originalinput+"\n"
    s+=errorposition*"-"
    s+="^\n"    # Zeiger nach oben: Position des Fehlers zeigen
    s+=errormessage
    print(s)

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

1+2*3
-----^
ok

Du hast also das Eingabewort vollständig abgearbeitet, als "Fehlermeldung" erhältst du "ok".

Fehlerhaftes Eingabewort

Wenn du stattdessen

parse("(1+2(*3", expr)

aufrufst, erhältst du als Ausgabe:

(1+2(*3
----^
Erwartet: )

Der Parser zeigt dir, an welcher Stelle der eingegebene Ausdruck nicht korrekt ist.

Als nicht korrekt wird der Ausdruck angesehen, wenn er nicht den Regeln der vorgegebenen Grammatik entspricht. Die Grammatik lässt (noch) keine mehrstelligen Zahlen zu, auch keine Leerzeichen und auch keine negativen Vorzeichen.

Wenn du dich also vielleicht wunderst, dass ein eigentlich als korrekt anzusehender Ausdruck nicht akzeptiert wird, kann es an diesen Beschränkungen der Grammatik liegen.

1 + 2*3
-^
Zu viele Zeichen: + 2*3

Hier hat der Parser den Ausdruck "1" abgearbeitet. Er stößt dann auf ein Zeichen, mit dem er nichts anfangen kann, nämlich das Leerzeichen. Daraufhin bricht er die weitere Bearbeitung des Eingabewortes ab.

Achte bitte darauf, dass deine arithmetischen Ausdrücke nur einstellige Zahlen und keine Leerzeichen und keine Vorzeichen enthalten.

Du kannst jetzt beliebig komplizierte arithmetische Ausdrücke parsen. Wenn du einen fehlerhaften arithmetischen Ausdruck eingibst, erhältst du eine sehr konkrete Fehlermeldung.

Der Parser analysiert exakt die Struktur des arithmetischen Ausdrucks; er beachtet gemäß den Regeln der Grammatik auch "Punktrechnung geht vor Strichrechnung". Dies ist für den nächsten Schritt wichtig, wenn du den Parser in einen Übersetzer umformst. Der Übersetzer übernimmt den arithmetischen Ausdruck als Eingabewort und übersetzt ihn in seinen Wert, also zum Beispiel das Eingabewort "1+2*3" in den Zahlenwert 7.

Schau dir einmal an, wie du aus dem Parser einen Übersetzer machst...

Aufgaben

Probiere einmal verschiedene korrekte und nicht korrekte arithmetische Ausdrücke aus und schaue dir die entsprechenden Fehlermeldungen an.

Sicher möchtest du auch mehrstellige Zahlen verarbeiten. Der Weg dahin ist folgender:

Ändere in der Grammatik die Produktion für number entsprechend.
Implementiere die Funktion für number gemäß der geänderten Produktion.

Du änderst die Produktion für number so, dass number aus einer einzelnen digit besteht, gefolgt möglicherweise von weiteren digits. Du brauchst also einen *-Ausdruck.

In der Implementierung der Funktion number realisierst du den *-Ausdruck durch eine While-Schleife. Als Bedingung für die While-Schleife verwendest du einen Aufruf einer Funktion comesDigit. Diese Funktion musst du noch schreiben; sie liefert True, wenn das erste Zeichen des verbliebenen Eingabewortes eine Ziffer ist. Am besten bringst du diese Funktion im Modul Parser unter.

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