Parser und Übersetzer

Erweiterte Backus-Naur-Form

Die erweiterte Backus-Naur-Form (EBNF), benannt nach J.W. Backuszur Person und P. Naurzur Person, dient zur knappen und über­sicht­lichen Darstellung der Produktionen einer kontext­freien Grammatik. Gegenüber der einfachen Backus-Naur-Form erlaubt die erweiterte Backus-Naur-Form die Verwendung von Optionen und Iterationen. Hierdurch wird zugleich auch die Pro­grammierung von Recursive-Descent-Parsern und -Übersetzern erleichtert. Im Folgenden wird auf ent­sprechende Implementierungen eingegangen.

Zeichen

Wir verwenden im Folgenden, wie in regulären Ausdrücken, das hoch­gestellte Fragezeichen ? für eine Option sowie den Stern * für die Iteration und das hoch­gestellte Pluszeichen + für die nichtleere Iteration.

In unserer Darstellung werden zudem die Zeichen unterschiedlicher Funktion in unterschiedlichen Farben gekenn­zeichnet:

rot Terminal­zeichen der Grammatik, die letztlich in der erzeugten Sprache vorkommen,
blau Variablen der Grammatik, die für den Ableitungs­prozess gebraucht werden, (in den unten­stehenden Beispielen Wortsymbole wie z.B. expr oder term).
schwarz Meta-Zeichen, die zur Darstellung der Produktionen der Grammatik dienen.

Produktion

Eine Produktion einer kontext­freien Grammatik wird in Backus-Naur-Form beispiels­weise wie folgt geschrieben:

expr geht über nachterm + expr

 

In einem Recursive-Descent-Parser wird diese Produktion als folgende Funktion implementiert:

void expr()
{
    term();
    match("+");
    expr();
}

Die Funktion erhält denselben Namen wie die Variable auf der linken Seite der Produktion, hier expr. Jede Variable auf der rechten Seite der Produktion wird in einen ent­sprechenden Funktions­aufruf umgesetzt, jedes Terminal­zeichen in einen Aufruf der Funktion match. Die Funktion match arbeitet das ent­sprechende Terminal­zeichen vom Eingabewort ab.

Alternativen

Eine Produktion mit mehreren Alternativen wird implementiert, indem eine Fall­unter­scheidung getroffen wird. Je nach dem nächsten Zeichen des Eingabe­wortes wird diejenige Alternative angewendet, die mit diesem Zeichen beginnt, oder die mit einer Variablen beginnt, aus der sich ein Wort ableiten lässt, das mit diesem Zeichen beginnt 1).

 

Beispiels­weise wird die Produktion

factor geht über nachnumber  |  ( expr )

wie folgt implementiert:

void factor()
{
    if (comesDigit())
        number();
    else if (comes("("))
    {
        match("(");
        expr();
        match(")");
    }
    else
        throw new RuntimeException("Erwartet: Ziffer oder (");
}

Option

Ein Spezialfall mehrerer Alternativen ist die Option. Eine Option liegt vor, wenn eine der Alternativen das leere Wort ε ist.

Eine Produktion der Form

Xgeht über nachu  |  ε

wird in erweiterter Backus-Naur-Form geschrieben als

Xgeht über nachu?

 

Eine Produktion mit einer Option, beispiels­weise

secondterm geht über nach(+ term)?

wird folgender­maßen implementiert.

void secondterm()
{
    if (comes("+"))
    {
        match("+");
        term();
    }
}

Es wird also versucht, + term abzuarbeiten. Wenn dies nicht möglich ist, weil das Zeichen + nicht kommt, wird nichts getan.

Iteration

Eine rekursive Produktion der Form

Xgeht über nachuX  |  ε

oder

Xgeht über nachXu  |  ε

wird in erweiterter Backus-Naur-Form abgekürzt als

Xgeht über nachu*

 

Eine Produktion mit einer Iteration, beispiels­weise

moreterms geht über nach(+ term)*

wird folgender­maßen implementiert.

void moreterms()
{
    while (comes("+"))
    {
        match("+");
        term();
    }
}

 

Es wird also versucht, + term so lange abzuarbeiten wie ein weiteres Zeichen + kommt.

Nichtleere Iteration

Eine rekursive Produktion der Form

Xgeht über nachuX  |  u

oder

Xgeht über nachXu  |  u

wird in erweiterter Backus-Naur-Form abgekürzt als

Xgeht über nachu+

 

Eine Produktion mit einer nichtleeren Iteration wie beispiels­weise

number geht über nachdigit+

wird folgender­maßen implementiert.

void number()
{
    do
        digit();
    while (comesDigit());
}

 

Es wird also zunächst eine digit abgearbeitet und dann weitere digits, solange noch welche kommen.

1)  Wenn sich das leere Wort ε aus der Variablen ableiten lässt, sind noch weiter­gehende Betrachtungen erforderlich.

 

Weiter mit:   [up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 29.10.2009   Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden