Systematische Programmentwicklung

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.

Zeichen

In der erweiterten Backus-Naur-Form werden ähnlich wie in regulären Ausdrücken das hoch­gestellte Fragezeichen ? für eine Option sowie der Stern * für die Iteration und das hoch­gestellte Pluszeichen + für die nichtleere Iteration verwendet.

In der folgenden Darstellung werden zudem die Zeichen unter­schiedlicher Funktion in unter­schiedlichen Farben gekenn­zeichnet:

rot Terminal­zeichen der Grammatik, die letztlich in der erzeugten Sprache vorkommen,
blau Nicht-Terminal­zeichen 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 schreiben Sie in Backus-Naur-Form beispiels­weise wie folgt:

expr geht über nachterm + expr

 

In einem Recursive-Descent-Parser implementieren Sie diese Produktion dann als folgende Funktion:

def expr():
    term()
    match("+")
    expr()

Die Funktion erhält denselben Namen wie das Nicht-Terminal­zeichen auf der linken Seite der Produktion, hier expr. Jede Variable auf der rechten Seite der Produktion setzen Sie in einen ent­sprechenden Funktions­aufruf um, 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 implementieren Sie, indem Sie eine Fall­unter­scheidung treffen. Je nach dem nächsten Zeichen des Eingabe­wortes wenden Sie diejenige Alternative an, 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 implementieren Sie die Produktion

factor geht über nachnumber  |  ( expr )

wie folgt:

def factor():
    if comesDigit():
        number()
    elif comes("("):
        match("(")
        expr()
        match(")")
    else:
        raise Exception("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  |  ε

schreiben Sie in erweiterter Backus-Naur-Form als

Xgeht über nachu?

 

Eine Produktion mit einer Option, beispiels­weise

secondterm geht über nach(+ term)?

implementieren Sie folgender­maßen:

def secondterm():
    if comes("+"):
        match("+")
        term()

Sie versuchen also, + term abzuarbeiten. Wenn dies nicht möglich ist, weil das Zeichen + nicht kommt, tun Sie nichts.

Iteration

Eine rekursive Produktion der Form

Xgeht über nachuX  |  ε

oder

Xgeht über nachXu  |  ε

kürzen Sie in erweiterter Backus-Naur-Form ab als

Xgeht über nachu*

 

Eine Produktion mit einer Iteration, beispiels­weise

moreterms geht über nach(+ term)*

implementieren Sie folgender­maßen:

def moreterms():
    while comes("+"):
        match("+")
        term()

Solange also ein weiteres Pluszeichen kommt, arbeiten Sie + term ab.

Nichtleere Iteration

Eine rekursive Produktion der Form

Xgeht über nachuX  |  u

oder

Xgeht über nachXu  |  u

kürzen Sie in erweiterter Backus-Naur-Form ab als

Xgeht über nachu+

 

Eine Produktion mit einer nichtleeren Iteration wie beispiels­weise

number geht über nachdigit+

implementieren Sie normaler­weise mit einer Do-Schleife. In Python gibt es jedoch keine Do-Schleifen, daher implementieren Sie u+ wie uu*:

def number():
    digit()
    while comesDigit():
        digit()

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

 

[up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden