Systematische Programmentwicklung

Im Folgenden erweitern Sie die sehr einfache Grammatik für einstellige ganze Zahlen mit oder ohne Vorzeichen nun auf mehrstellige ganze Zahlen. Dabei begegnen Ihnen mögliche Probleme bei der Umsetzung einer Grammatik in einen Recursive-Descent-Parser und Sie lernen ent­sprechende Lösungs­möglichkeiten kennen.

Mehrstellige ganze Zahlen

Die Grammatik G mit folgenden Produktionen beschreibt mehrstellige ganze Zahlen ohne Vorzeichen.

integer		digit  |  integer digit
digit		0  |  ...  |  9

Eine Integer-Zahl besteht also aus einer einzelnen Ziffer oder aus einer (kürzeren) Integer-Zahl gefolgt von einer Ziffer. Diese Grammatik ist aber aus zwei Gründen nicht für einen Recursive-Descent-Parser geeignet. Zum einen können Sie anhand des jeweils nächsten Zeichens des Eingabe­wortes nicht unter­scheiden, welche der beiden Alternativen der Produktion für integer Sie anwenden müssen, denn beide beginnen mit einer Ziffer. Zum anderen ist die Produktion integer integer digit links­rekursiv. In der Implementierung ruft die Funktion integer sich selbst auf, ohne dass ein Zeichen des Eingabe­wortes abgearbeitet wird. Dies führt zu einer unendlichen Aufrufkette.

Jedoch können Sie eine kontextfreie Grammatik, die sich unmittelbar nicht für einen Recursive-Descent-Parser eignet, gegebenen­falls umformen. Verschiedene Methoden hierfür sind im Folgenden angegeben.

Linksrekursion durch Rechtsrekursion ersetzen

Die Grammatik G soll so umgeformt werden, dass sie keine linksrekursiven Produktionen enthält.

Die allgemeine Vorgehens­weise hierfür besteht darin, dass Sie jede Produktion der Form

X

u  |  Xw

ersetzen durch die Produktionen

X		uR
R		wR  |  ε

Hierbei ist R eine neu eingeführte Variable.

Angewandt auf die Grammatik G führt dies zu folgenden Produktionen. Hierbei steht integer für X, digit für u und w, ferner steht moredigits für die neu eingeführte Variable R.

integer		digit moredigits
moredigits		digit moredigits  |  ε

Faktorisierung

Offenbar beschreibt integer eine nichtleere Folge von Ziffern. Dies drücken Sie auch durch eine Grammatik mit einer rechts­rekursiven Produktion für integer aus:

integer		digit  |  digit integer
digit		0  |  ...  |  9

Hier tritt jedoch das schon erwähnte Problem auf, dass beide Alternativen der Produktion für integer mit digit beginnen. Somit können Sie anhand des nächsten Zeichens des Eingabe­wortes nicht unter­scheiden, welche der beiden Alternativen anzuwenden ist.

Da aber beide Alternativen mit digit beginnen, klammern Sie digit einfach aus. Dies führt zu folgender Grammatik:

integer		digit (ε  |  integer)
digit		0  |  ...  |  9

Diese Vorgehens­weise des Ausklammerns wird als Faktorisierung bezeichnet.¹) Die so umgeformte Grammatik implementieren Sie ohne Weiteres in einem Recursive-Descent-Parser.

Rekursion durch Iteration ersetzen

Eine andere Möglichkeit, Links- oder Rechts­rekursionen zu beseitigen, besteht darin, diese durch Iterationen zu ersetzen.

Die allgemeine Vorgehens­weise für Links­rekursionen ist die folgende, dargestellt in erweiterter Backus-Naur-Form (EBNF). Jede Produktion der Form

Xu  |  Xw

ersetzen Sie durch die Produktion

Xuw*

Ausgehend von der ursprüng­lichen links­rekursiven Produktion für integer ergibt sich folgende umgeformte Produktion:

integer

digit digit*

Hierbei steht wieder integer für X sowie digit für u und w. Diese Produktion implementieren Sie entsprechend in einem Recursive-Descent-Parser.

Für Rechts­rekursionen gilt eine ähnliche Vorgehens­weise. Jede Produktion der Form

Xu  |  wX

ersetzen Sie durch die Produktion

Xw*u