Parser und Übersetzer

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

 aufwärts

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.

Additions-/Subtraktions-Ausdrücke

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 Terminal­zeichen,
P : 
expr geht über nachexpr + number  |  expr - number  |  number
number geht über nachdigit
digit geht über nach0  |  ...  |  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 links­rekursiv. So führt die Umsetzung der Alternative expr geht über nachexpr + 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 Eingabe­wortes verarbeitet wird. Dies führt zu einer unendlichen Kette von Aufrufen von expr und damit irgendwann zum Abbruch des Programms mit der Fehler­meldung stack overflow.

Derartige Links­rekursionen müssen also vermieden werden. In Teil 2 hatten wir zwei Methoden kennen­gelernt, die Grammatik entsprechend umzuformen, nämlich indem Links­rekursionen durch Rechts­rekursionen ersetzt werden oder Rekursionen durch Iterationen ersetzt werden.

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

expr geht über nachnumber (+ number  |  - number)*

Programm

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()
        else:
            pass    # Epsilon-Produktion anwenden
    
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 auf­treten, da Leerzeichen in der Grammatik nicht berück­sichtigt sind und vom Parser demzufolge nicht abgearbeitet werden.

Aufgaben

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 beispiels­weise -17+-4+21 gültig sind.

 

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 16.08.2012   Updated: 10.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik