Parser und Übersetzer

Recursive-Descent-Methode

 aufwärts

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.

In diesem Beispiel soll ein Parser für Zeichen­folgen, die einstellige ganze Zahlen mit oder ohne negatives Vorzeichen darstellen, konstruiert werden. 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 unserem Beispiel sollen die Zahlen 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 geht über nachsign digit
sign geht über nach+  |  -  |  ε
digit geht über nach0  |  ...  |  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.

Bild 1: Ableitungsbaum für -5
Bild 1: Ableitungsbaum für -5

Recursive-Descent-Methode

Bei der Recursive-Descent-Methode wird für jede Variable, die auf der linken Seite einer Produktion vorkommt, eine Funktion geschrieben. In der Funktion wird die rechte Seite der jeweiligen Produktion behandelt. Für jede dort vorkommende Variable wird ein ent­sprechender Funktions­aufruf durchgeführt, für jedes Terminal­zeichen wird das ent­sprechende Zeichen vom Eingabewort abgearbeitet.

Durch Aufruf der Funktion, die dem Startsymbol der Grammatik entspricht, steigt das Verfahren 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 Funktions­aufruf für sign gefolgt von einem Funktions­aufruf für digit.

def number():
    sign()
    digit()

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

Die Funktion für die Variable sign unter­scheidet die beiden Alternativen der Produktion in ent­sprechender Weise: Wenn das nächste Zeichen des Eingabewortes ein Pluszeichen ist, wird die erste Alternative angewendet, wenn es ein Minuszeichen ist, wird die zweite Alternative angewendet, anderenfalls die dritte.

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

def sign():
    if comes("+"):
        consume()
    elif comes("-"):
        consume()
    else:
        pass    # Epsilon-Produktion: tue nichts

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 die Variable digit behandelt alle Alternativen in gleicher Weise und ist daher recht einfach. Mit comesDigit wird geprüft, ob das nächste Zeichen des Eingabewortes eines der Zeichen "0", ..., "9" ist, mit consume wird es dann abgearbeitet. Wenn keine Ziffer gefunden wird, löst die Funktion einen Fehler aus. Der Fehler wird in einer über­geordneten Funktion abgefangen und ausgewertet.

def digit():
    if comesDigit():
        consume()
    else:
        raise Exception("Ziffer erwartet")

Modul SimpleNumberParser

Die angegebenen drei Funktionen für die Variablen der Grammatik sind Bestandteil des Moduls SimpleNumberParser. Es enthält außerdem noch die Funktion comesDigit, die prüft, ob der noch nicht abge­arbeitete Teil des Eingabewortes mit einer Ziffer beginnt. Das Modul importiert die grund­legenden Funktionen comes, comesAnyOf und consume aus dem Basismodul Parser.

from Parser import *

def number():
    sign()
    digit()

def sign():
    if comes("+"):
        consume()
    elif comes("-"):
        consume()
    else:
        pass    # Epsilon-Produktion: tue nichts

def digit():
    if comesDigit():
        consume()
    else:
        raise Exception("Ziffer erwartet")

def comesDigit():
    return comesAnyOf("0123456789")

 

Im Haupt­programm wird der SimpleNumberParser dann folgender­maßen getestet, hierbei wird der Funktion parse das Eingabewort und der Name der Funktion, die dem Startsymbol der Grammatik entspricht, übergeben.

from SimpleNumberParser import *

parse("-5", number)
showErrorPosition()

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

--5
-^
Ziffer erwartet

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; diese werden wir im einzelnen noch angeben.

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

In den folgenden Teilen finden sich weitere Beispiele für die Erzeugung von Recursive-Descent-Parsern.

 

Weiter mit:   [Recursive-Descent-Parser für mehrstellige Zahlen]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 16.08.2012   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik