Parser und Übersetzer

Recursive-Descent-Parser für einfache Ausdrücke

In einem weiteren Beispiel soll ein Recursive-Descent-Parser für Additions-/Subtraktions-Ausdrücke erstellt werden. Die Ausdrücke liegen als Strings vor, die Zahlen in den Ausdrücken sind zunächst nur einfache Ziffern. Beispiele für solche Ausdrücke sind etwa 9-3-4 oder 3-5+0-1 oder auch 2.

Eine kontextfreie Grammatik G = (V, T, P, S) für die Ausdrücke ist wie folgt gegeben. Es sind

V =

{ expr, number, digit } die Menge der Variablen,

T =

{ 0, ..., 9, +, - } die Menge der Terminalzeichen,

P :

expr		expr + number \| expr - number \| number
number		digit
digit		0 \| ... \| 9

die Produktionen und

S =

expr das Startsymbol.

Leider verträgt sich die gegebene Grammatik nicht mit der Recursive-Descent-Methode, denn die ersten beiden Alternativen der Produktion für expr sind linksrekursiv. So führt die Umsetzung der Alternative expr geht über nach expr + number zu folgendem Programm:

def expr():
    expr()
    match("+")
    number()

Hier tritt in der ersten Anweisung bereits wieder ein rekursiver Aufruf von expr auf, ohne dass ein Zeichen des Eingabewortes verarbeitet wird. Dies führt zu einer unendlichen Kette von Aufrufen von expr und damit irgendwann zum Abbruch des Programms mit der Fehlermeldung stack overflow.

Derartige Linksrekursionen müssen also vermieden werden. In Teil 2 hatten wir zwei Methoden kennengelernt, die Grammatik entsprechend umzuformen, nämlich indem Linksrekursionen durch Rechtsrekursionen ersetzt werden oder Rekursionen durch Iterationen ersetzt werden.

Wir wenden die zweite Methode an und erhalten für expr die Produktion

expr

number (+ number | - number)*

Die umgeformte Grammatik lässt sich unmittelbar in folgendes Programm umsetzen:

from Parser import *

def expr():
    number()
    while comesAnyOf("+-"):
        if comes("+"):
            consume()
            number()
        elif comes("-"):
            consume()
            number()

def number():
    digit()

def digit():
    if comesDigit():
        consume()
    else:
        raise Exception("Ziffer erwartet")

def comesDigit():
    return comesAnyOf("0123456789")

Der Parser lässt sich mit folgendem Programm testen:

from SimpleExprParser import *

parse("9-3-4", expr)
showErrorPosition()

Achtung: Es dürfen keine Leerzeichen im Eingabewort auftreten, da Leerzeichen in der Grammatik nicht berücksichtigt sind und vom Parser demzufolge nicht abgearbeitet werden.

Aufgabe 3: Kombinieren Sie die Grammatik für Additions-/Subtraktions-Ausdrücke mit der Grammatik für mehrstellige ganze Zahlen mit mehreren Vorzeichen aus Aufgabe 2 in Teil 2, sodass auch Ausdrücke wie beispielsweise -17+-4+21 gültig sind.

Weiter mit: [Recursive-Descent-Übersetzer] oder [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 16.08.2012 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden

Parser und Übersetzer

Recursive-Descent-Parser für einfache Ausdrücke

Additions-/Subtraktions-Ausdrücke

Programm

Aufgaben