Parser und Übersetzer

Die Methode der Übersetzung durch rekursiven Abstieg (engl.: recursive descent) wird im Folgenden anhand von Beispielen dargestellt. Das erste Beispiel ist bewusst sehr einfach gewählt, um das Prinzip der Recursive-Descent-Methode darzustellen.

Im ersten Beispiel soll ein Parser für einstellige ganze Zahlen mit oder ohne Vorzeichen erstellt werden. Ein Parser ist ein Programm, das eine Zeichenreihe in ihre syntaktischen Bestandteile zerlegt und erkennt, ob die Zeichenreihe den vorgegebenen Syntaxregeln entspricht oder nicht.

Syntax

Die Syntaxregeln werden formal durch eine kontextfreie Grammatik angegeben.

Die Zahlen sollen zunächst nur aus einer Ziffer bestehen. Wir benutzen folgende Grammatik G = (V, T, P, S); es sind

V  =		{ number, sign, digit }  die Menge der Variablen,
T  =		{ 0, ..., 9, +, - }  die Menge der Terminal­zeichen,
P :		number sign digit sign +  |  -  |  ε digit 0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9
		die Produktionen und
S  =		number das Startsymbol.

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

Recursive-Descent-Parser

Grundlage für die Konstruktion eines Recursive-Descent-Parsers ist eine kontextfreie Grammatik. Die Grammatik muss bestimmte Eigen­schaften haben; diese werden im Folgenden später noch heraus­gearbeitet.

Die Grammatik ist in der Weise gegeben, dass Produktionen mit gleicher linker Seite zu einer Produktion mit mehreren Alternativen auf der rechten Seite zusammen­gefasst sind.

Bei der Recursive-Descent-Methode wird für jede dieser Produktionen eine Funktion geschrieben. Die Funktion erhält denselben Namen wie die Variable auf der linken Seite der Produktion. Auf diese Weise wird erreicht, dass die Grammatik sich sozusagen "selbst ausführt" und das Eingabewort auf das Startsymbol reduziert.

In der Funktion werden alle Alternativen, die auf der rechten Seite der Produktion vorkommen, durch Fall­unter­scheidung getrennt behandelt. Eine Alternative wird implementiert, indem für jede dort vorkommende Variable ein ent­sprechender Funktions­aufruf durchgeführt wird, und für jedes dort vorkommende Terminal­zeichen das ent­sprechende Zeichen vom Eingabewort abgearbeitet wird.

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.

Die Funktion für die Produktion number sign digit ist sehr einfach. Da die rechte Seite nicht aus mehreren Alternativen besteht, ist keine Fall­unter­scheidung erforderlich. Die Implementierung besteht lediglich aus einem Funktions­aufruf für sign gefolgt von einem Funktions­aufruf für digit.

Die Funktion für die Produktion sign + | - | ε muss die drei Alternativen der Produktion unter­scheiden. Wenn das nächste Zeichen des Eingabe­wortes ein Pluszeichen ist, wird die erste Alternative angewendet, wenn es ein Minuszeichen ist, die zweite, und ansonsten die dritte.

Die Funktion comes prüft, mit welchem Zeichen das (verbliebene) Eingabewort anfängt; die Funktion match arbeitet das Zeichen ab. Die genaue Implementation dieser Funktionen ist weiter unten angegeben.

Die Funktion für die Produktion der Variablen digit lässt sich in ähnlicher Weise durch zehn Fall­unter­scheidungen implementieren. Dies mag umständlich erscheinen, aber wir implementieren damit streng die Regeln der Grammatik. Es ist gute Praxis, sich nicht zu "Optimierungen" verleiten zu lassen, sondern die Grammatik exakt nachzubilden.

Klasse SimpleNumberParser

Die angegebenen drei Funktionen sind eingebettet in eine Klasse SimpleNumberParser, die von einer abstrakten Basisklasse Parser abgeleitet ist. Die Klasse Parser enthält eine Funktion parse, in der eine zunächst abstrakte Funktion startSymbol aufgerufen wird. Diese wird in der abgeleiteten Klasse SimpleNumberParser implementiert, indem die Startsymbol-Funktion number aufgerufen wird.

Das zu analysierende Eingabewort inputstring sowie die grund­legenden Funktionen wie etwa comes, match und andere sind einer abstrakten Klasse ParserFunctions implementiert, von der wiederum die Klasse Parser abgeleitet ist.

Wir verwenden diese mehrstufige Klassen­hierarchie, weil wir später von der Klasse ParserFunctions auch eine abstrakte Klasse Compiler und von dieser wiederum konkrete Compiler ableiten wollen, um Eingabe­wörter nicht nur syntaktisch zu prüfen, sondern sie gleichzeitig auch noch zu übersetzen.

Im Haupt­programm wird zunächst ein Objekt p vom Typ SimpleNumberParser erzeugt und ein Eingabewort x festgelegt. Dieses wird mit p.parse(x) analysiert. Anschließend wird entweder "ok" oder eine Fehler­meldung ausgegeben und die Position des Fehlers angezeigt.

Basisklasse Parser

Alle konkreten Parser, die eine bestimmte Grammatik zugrunde legen, werden von der abstrakten Klasse Parser abgeleitet. Die Klasse Parser greift wiederum auf eine abstrakte Klasse ParserFunctions zurück.

[Basisklassen]

Zusammenfassung

Bei der Recursive-Descent-Methode wird die gegebene kontextfreie Grammatik direkt in einen Parser überführt.

Dies geschieht, indem für jede Produktion der Grammatik eine Funktion geschrieben wird. Die Funktion erhält denselben Namen wie die Variable, die auf der linken Seite der Produktion steht. In der Funktion werden alle auf der rechten Seite der Produktion stehenden Alternativen durch Fall­unter­scheidung getrennt implementiert.

Eine Alternative auf der rechten Seite einer Produktion wird implementiert, indem für jede dort vorkommende Variable die ent­sprechende Funktion aufgerufen wird. Für jedes Terminal­zeichen wird die Funktion match aufgerufen.

Die Fall­unter­scheidung, welche Alternative einer Produktion anzuwenden ist, wird anhand des ersten Zeichens des jeweils verbliebenen, noch nicht abge­arbeiteten Eingabe­wortes durchgeführt.