Systematische Programmentwicklung

Anhand von Beispielen erlernen Sie im Folgenden die Recursive-Descent-Methode zur Konstruktion von Parsern und Übersetzern. Das erste Beispiel ist bewusst sehr einfach gewählt, um Ihnen das Prinzip der Recursive-Descent-Methode zu ver­anschaulichen.

In diesem Beispiel konstruieren Sie einen Parser für Zeichen­folgen, die einstellige ganze Zahlen mit oder ohne Vorzeichen darstellen. Ein Parser ist ein Programm, das ein Eingabewort in seine syntaktischen Bestandteile zerlegt und erkennt, ob es den vorgegebenen Syntaxregeln entspricht oder nicht.

Syntax

Die Syntaxregeln werden formal durch eine kontextfreie Grammatik angegeben.

In diesem Beispiel bestehen die Zahlen zunächst nur aus einer Ziffer. Das Vorzeichen ist ein Plus- oder ein Minuszeichen oder es fehlt. Dazu benutzen Sie die folgende Grammatik G = (V, T, P, S). Hierbei sind

V  =		{number, sign, digit}  die Menge der Nicht-Terminal­zeichen,
T  =		{ 0, ..., 9, +, - }  die Menge der Terminal­zeichen,
P :		number sign digit sign +  |  -  |  ε digit 0  |  ...  |  9
		die Produktionen und
S  =		number das Startsymbol.

Syntaktisch korrekte Zeichen­folgen entsprechend dieser Grammatik sind also beispiels­weise 3, -5, +0 oder +6. Bild 1 zeigt den Ableitungsbaum für -5.

Recursive-Descent-Methode

Bei der Recursive-Descent-Methode schreiben Sie für jedes Nicht-Terminal­zeichen, das auf der linken Seite einer Produktion vorkommt, eine Funktion. In der Funktion behandeln Sie die rechte Seite der jeweiligen Produktion. Für jedes dort vorkommende Nicht-Terminal­zeichen führen Sie einen ent­sprechender Funktions­aufruf durch, für jedes Terminal­zeichen arbeiten Sie das ent­sprechende Zeichen vom Eingabewort ab.

Durch Aufruf der Funktion, die dem Startsymbol der Grammatik entspricht, steigen Sie rekursiv im Ableitungs­baum hinab bis zum Eingabewort, das sich an den Blättern des Ableitungs­baumes befindet – daher die Bezeichnung recursive descent.

Das Startsymbol der oben angegebenen Grammatik ist number. Die Funktion number besteht, entsprechend der Produktion für number, aus einem Aufruf der Funktion sign gefolgt von einem Aufruf der Funktion digit.

Hat eine Produktion auf der rechten Seite mehrere Alternativen, so führen Sie in der Funktion eine ent­sprechende Fall­unter­scheidung durch. Grundlage der Entscheidung, welche Alternative angewendet wird, ist das nächste abzu­arbeitende Zeichen des Eingabe­wortes (der Lookahead). Die Grammatik muss so gestaltet sein, dass aufgrund des Lookaheads immer eine Entscheidung möglich ist.

In der Funktion für das Nicht-Terminal­zeichen sign unter­scheiden Sie die beiden Alternativen der Produktion in ent­sprechender Weise: Wenn das nächste Zeichen des Eingabe­wortes ein Pluszeichen ist, wenden Sie die erste Alternative an, wenn es ein Minuszeichen ist, wenden Sie die zweite Alternative an, anderenfalls die dritte.

Die Funktion comes prüft das nächste Zeichen des Eingabe­wortes; die Funktion consume arbeitet das Zeichen ab. Die Implementierung dieser Funktionen ist im Basismodul Parser angegeben.

Der Else-Teil für die Anwendung der Epsilon-Produktion ist hier nur der Deutlichkeit halber angegeben; da er nichts bewirkt, kann er auch entfallen.

Die Funktion für das Nicht-Terminal­zeichen digit behandelt alle Alternativen in gleicher Weise und ist daher recht einfach. Mit comesDigit prüfen Sie, ob das nächste Zeichen des Eingabe­wortes eines der Zeichen "0", ..., "9" ist, mit consume arbeiten Sie es dann ab. Wenn Sie keine Ziffer finden, lösen Sie einen Fehler aus. Der Fehler wird in einer über­geordneten Funktion abgefangen und ausgewertet.

Modul SimpleNumberParser

Die angegebenen drei Funktionen für die Nicht-Terminal­zeichen der Grammatik sind Bestandteil des Moduls SimpleNumberParser. Es enthält außerdem noch dir Funktion comesDigit, mithilfe derer Sie prüfen, ob das verbliebene Eingabewort mit einer Ziffer beginnt.

Das Modul importiert die grund­legenden Funktionen comes und consume aus dem Basismodul Parser.

Im Haupt­programm testen Sie den SimpleNumberParser dann folgender­maßen. Hierbei übergeben Sie der Funktion parse das Eingabewort und den Namen der Funktion, die dem Startsymbol der Grammatik entspricht.

Im Fehlerfall, etwa bei Eingabe des Wortes - -5, wird die Fehler­position mit showErrorPosition ausgegeben:

Zusammenfassung

Eine kontextfreie Grammatik besteht aus Regeln zur Erzeugung von Wörtern einer Sprache. Um ein bestimmtes Wort zu erzeugen, wird ausgehend vom Startsymbol der Grammatik eine bestimmte Folge von Ableitungs­schritten, also Anwendungen von Produktionen, ausgeführt. Einer solchen Ableitungs­folge entspricht ein Ableitungs­baum für das Wort (vgl. Bild 1).

Ein Recursive-Descent-Parser erzeugt implizit diesen Ableitungs­baum und durchläuft ihn dabei. Damit dies in deterministischer Weise funktioniert, muss die Grammatik bestimmte Eigen­schaften haben.

Die Systematik der Umformung von Produktionen der Grammatik in ent­sprechende Funktionen des Parsers finden Sie im Artikel über die Erweiterte Backus-Naur-Form für Produktionen.