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.

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 geht über nachsign digit
sign geht über nach+  |  -  |  ε
digit geht über nach0  |  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.

Bild 1: Ableitungsbaum für - 5
Bild 1: Ableitungsbaum für - 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. 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 geht über nachsign 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.

void number()
{
    sign();
    digit();
}

 

Die Funktion für die Produktion sign geht über nach+ | - | ε 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.

void sign()
{
    if (comes("+"))   // Produktion sign -> + anwenden
        match("+");
    else if (comes("-"))   // Produktion sign -> - anwenden
        match("-");
    else;    // Produktion sign -> epsilon anwenden: tue nichts
}

 

Die Funktion für die Produktion der Variablen digit lässt sich grund­sätzlich in ähnlicher Weise durch zehn Fall­unter­scheidungen implementieren. Wir behandeln hier alle Alternativen in gleicher Weise unter Verwendung einer Funktion comesDigit. Die Funktion comesDigit liefert true, wenn das verbliebene Eingabewort mit einem der Zeichen "0", ..., "9" anfängt. In diesem Fall wird diese Ziffer durch die Funktion consume abgearbeitet. Wenn dagegen keine Ziffer gefunden wird, löst die Funktion einen Fehler aus. Der Fehler wird in einer über­geordneten Funktion abgefangen und ausgewertet.

void digit()
{
    if (comesDigit())
        consume(1);
    else
        throw new RuntimeException("Ziffer erwartet");
}

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, consume, 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.

 

class SimpleNumberParser extends Parser
{
    // Startsymbol ist number
    @Override
    protected void startSymbol()
    {
        number();
    }

    // number -> sign digit
    private void number()
    {
        sign();
        digit();
    }

    // sign -> + | - | epsilon
    private void sign()
    {
        if (comes("+"))   // Produktion sign -> + anwenden
            match("+");
        else if (comes("-"))   // Produktion sign -> - anwenden
            match("-");
        else;    // Produktion sign -> epsilon anwenden: tue nichts
    }

    // digit -> 0 | 1 | ... | 9
    private void digit()
    {
        if (comesDigit())
            consume(1);
        else
            throw new RuntimeException("Ziffer erwartet");
    }

    // Test
    public static void main(String[] args)
    {
        Parser p=new SimpleNumberParser();
        String x="+5";
        p.parse(x);
        System.out.println(x);
        System.out.println(p.errorPointer());
        System.out.println(p.errormessage);
    }

}    // end class SimpleNumberParser

 

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.

 

Weiter mit:   [Parser für Additions-Subtraktions-Ausdrücke]   oder   up

 

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

Hochschule Flensburg
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