Systematische Programmentwicklung

Als Nächstes erstellen Sie einen Recursive-Descent-Parser für Additions-/Subtraktions-Ausdrücke. Die Ausdrücke liegen als Strings vor, die Zahlen in den Ausdrücken sind zunächst nur einstellig, später auch mehrstellig. 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 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 links­rekursiv. So führt die Umsetzung der Alternative expr expr + number zu folgendem Programm:

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 Sie also vermeiden. Im Artikel über mehrstellige Zahlen haben Sie zwei Methoden kennen­gelernt, die Grammatik entsprechend umzuformen, nämlich indem Sie Links­rekursionen durch Rechts­rekursionen ersetzen oder indem Sie Rekursionen durch Iterationen ersetzen.

Wenn Sie die zweite Methode anwenden, erhalten Sie für expr die Produktion

expr

number (+ number  |  - number)*

Programm

Die umgeformte Grammatik setzen Sie unmittelbar in folgendes Programm um:

Den Parser testen Sie mit folgendem Programm:

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.