Parser und Übersetzer

Die sehr einfache Grammatik für einstellige ganze Zahlen mit oder ohne Vorzeichen aus Teil 1 wird nun auf mehrstellige ganze Zahlen erweitert. Dabei werden mögliche Probleme bei der Umsetzung einer Grammatik in einen Recursive-Descent-Parser angesprochen und ent­sprechende Lösungs­möglichkeiten angegeben.

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 kann anhand des jeweils nächsten Zeichens des Eingabe­wortes nicht unter­schieden werden, welche der beiden Alternativen der Produktion für integer anzuwenden ist, 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.

Grammatiken, die sich unmittelbar nicht für einen Recursive-Descent-Parser eignen, lassen sich in den meisten Fällen umformen. Einige 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 jede Produktion der Form

X

u  |  Xw

ersetzt wird 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 lässt sich auch direkt durch eine Grammatik mit einer rechts­rekursiven Produktion für integer ausdrücken:

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

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

Da aber beide Alternativen mit digit beginnen, lässt sich digit ausklammern. 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 lässt sich als Recursive-Descent-Parser implementieren.

Rekursion durch Iteration ersetzen

Eine andere Möglichkeit, Links- oder Rechts­rekursionen zu beseitigen, besteht darin, diese durch Iterationen zu ersetzen. Hierzu wird die Grammatik umgeformt und in erweiterter Backus-Naur-Form (EBNF) dargestellt.

Die allgemeine Vorgehens­weise für Links­rekursionen ist die folgende. Jede Produktion der Form

Xu  |  Xw

wird ersetzt 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 lässt sich in einem Recursive-Descent-Parser implementieren.

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

Xu  |  wX

wird ersetzt durch die Produktion

Xw*u

Aufgaben