Parser und Übersetzer

Erweiterte Backus-Naur-Form

Die erweiterte Backus-Naur-Form (EBNF), benannt nach J.W. Backus und P. Naur, dient zur knappen und übersichtlichen Darstellung der Produktionen einer kontextfreien 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 Programmierung von Recursive-Descent-Parsern und -Übersetzern erleichtert. Im Folgenden wird auf entsprechende Implementierungen eingegangen.

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

In unserer Darstellung werden zudem die Zeichen unterschiedlicher Funktion in unterschiedlichen Farben gekennzeichnet:

rot		Terminalzeichen der Grammatik, die letztlich in der erzeugten Sprache vorkommen,
blau		Variablen der Grammatik, die für den Ableitungsprozess gebraucht werden, (in den untenstehenden Beispielen Wortsymbole wie z.B. expr oder term).
schwarz		Meta-Zeichen, die zur Darstellung der Produktionen der Grammatik dienen.

Eine Produktion einer kontextfreien Grammatik wird in Backus-Naur-Form beispielsweise wie folgt geschrieben:

expr

term + expr

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

def 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 entsprechenden Funktionsaufruf umgesetzt, jedes Terminalzeichen in einen Aufruf der Funktion match. Die Funktion match arbeitet das entsprechende Terminalzeichen vom Eingabewort ab.

Eine Produktion mit mehreren Alternativen wird implementiert, indem eine Fallunterscheidung getroffen wird. Je nach dem nächsten Zeichen des Eingabewortes 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 ¹).

Beispielsweise wird die Produktion

factor

number | ( expr )

wie folgt implementiert:

def factor():
    if comesDigit():
        number()
    elif comes("("):
        match("(")
        expr()
        match(")")
    else:
        raise Exception("Erwartet: Ziffer oder (")

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

Eine Produktion der Form

X

u | ε

wird in erweiterter Backus-Naur-Form geschrieben als

X

u^?

Eine Produktion mit einer Option, beispielsweise

secondterm

(+ term)^?

wird folgendermaßen implementiert.

def 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.

Eine rekursive Produktion der Form

X

uX | ε

oder

X

Xu | ε

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

X

u*

Eine Produktion mit einer Iteration, beispielsweise

moreterms

(+ term)*

wird folgendermaßen implementiert.

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

Solange also ein weiteres Pluszeichen kommt, wird + term abgearbeitet.

Eine rekursive Produktion der Form

X

u | uX

oder

X

u | Xu

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

X

u⁺

Eine Produktion mit einer nichtleeren Iteration wie beispielsweise

number

digit⁺

wird normalerweise mit einer Do-Schleife implementiert. In Python gibt es jedoch keine Do-Schleifen, daher wird u⁺ wie uu* implementiert:

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

¹) Wenn sich das leere Wort ε aus der Variablen ableiten lässt, sind noch weitergehende Betrachtungen erforderlich.

Weiter mit: [up]

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

Parser und Übersetzer

Erweiterte Backus-Naur-Form

Zeichen

Produktion

Alternativen

Option

Iteration

Nichtleere Iteration