Die Backus-Naur-Form

Die Backus-Naur-Form  (BNF ) ist eine kompakte, schriftliche Notation der Aufbaudiagramme, wie sie in der Spezifikation von Programmiersprachen, wie beispielsweise Python, verwendet wird.

Tatsächlich gibt es verschiedene Dialekte  der Backus-Naur-Form. Diese Lektion beschreibt zunächst eine spezielle EBNF-Variante, welche für diesen Kurs verwendet wird. Sie kann sich in Details von anderen Dialekten der BNF unterscheiden.

Heute verwendet man oft Dialekte der BNF, die gegenüber dem Original erweitert sind, und die man daher auch als EBNF  (erweiterte BNF) oder ABNF  (augmentierte BNF) bezeichnet.

Teile der EBNF sind inzwischen so weit bekannt, daß einzelne EBNF-Schreibweisen sogar im Duden ohne Erklärung verwendet werden, etwa zur Angabe des Genitivs von „Wort“ als „Wort[e]s“.

Die Sprache, welche man mit EBNF beschreibt (zum Beispiel Python ), wird auch als Objektsprache  bezeichnet. EBNF wird in diesem Falle als Metasprache  bezeichnet.

Terminalsymbole

Ein Terminalsymbol  ist ein Zeichen oder eine lexikalische Einheit. (Bei Aufbaudiagrammen kennzeichnet ein »|-|« am Eingang, daß das Aufbaudiagramm ein morphologisches Diagramm  ist und die Terminalsymbole darin Zeichen sind, sonst handelt es sich um ein Syntaxdiagramm, und die Terminalsymbole stehen dann für lexikalische Einheiten.)

Im Syntaxdiagramm wird ein Terminalsymbol in runden Kästchen notiert.

Diagrammdarstellung

 .-.    
( - )
 '-'

In der EBNF schreiben wir die Zeichen eines Terminalsymbols zwischen Apostrophe.

EBNF

'-'

auf deutsch

ein Minuszeichen

EBNF

'if'

auf deutsch

Die lexikalische Einheit »if«

Ob es sich um Zeichen oder um lexikalische Einheiten handeln soll, muß gesondert angegeben werden.

Auch Anführungszeichen sind an Stelle von Apostrophen mit gleicher Bedeutung erlaubt.

EBNF

"-"

auf deutsch

„ein Minuszeichen“

Produktionsregeln

Im Syntaxdiagramm wird eine Kategorie als Beschriftung über einem Wegplan geschrieben, wenn der Wegplan angibt, wie jene Kategorie realisiert werden kann.

Diagrammdarstellung

Vorzeichen
     .-.
--->( - )--->
     '-'

In der EBNF werden Kategorienamen in spitzen Klammern geschrieben und erscheinen mit einem »::=« verbunden vor der Beschreibung ihrer Realisierungsmöglichkeiten. Die Produktionsregel endet dann mit einem Punkt „.“.

Erweiterte Backus-Naur-Form

〈Vorzeichen 〉 ::=

'-'.

auf deutsch

„Ein Vorzeichen kann durch ein Minuszeichen realisiert werden.“

Kategorienamen, wie „〈Vorzeichen 〉“ werden auch als Nichtterminalsymbole  bezeichnet.

Alternativen

In Aufbaudiagrammen wird eine Alternative  durch eine Verzweigung  dargestellt.

Diagrammdarstellung

Vorzeichen
             .-.
   --->.--->( + )---.--->
       |     '-'    ^
       |     .-.    |
       '--->( - )---'
             '-'

In der EBNF werden Alternativen durch einen senkrechten Strich  »|« voneinander getrennt.

EBNF

〈Vorzeichen 〉 ::=

'+' | '-'.

auf deutsch

„Ein Vorzeichen kann durch ein Pluszeichen oder durch ein Minuszeichen realisiert werden.“

Beispiele

〈lower_case_latin_letter 〉 ::=

'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z'.

〈upper_case_latin_letter 〉 ::=

'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z'.

Sequenzen

In Aufbaudiagrammen wird eine Sequenz  durch eine Verbindung zweier Bestandteile mit einem Pfeil  dargestellt.

Diagrammdarstellung

Doppelgleich
     .-.      .-. 
--->( = )--->( = )--->
     '-'      '-'

In der EBNF wird eine Sequenz durch Hintereinanderschreibung ausgedrückt.

EBNF

〈Doppelgleich 〉 ::=

'=' '='.

auf deutsch

„Ein Doppelgleich besteht aus einer Folge zweier Gleichheitszeichen.“

Falls die Sequenz als Operation besonders bezeichnet werden soll, verwenden wir eine Größer-Zeichen  „>“.

EBNF

〈Doppelgleich 〉 ::=

'=' > '='.

Prioritäten

Die Priorität des Größer-Zeichens „>“ ist stärker als die Priorität der Alternative „|“. Bei einer Sequenz, die ohne Größer-Zeichen geschrieben wird, kann man die Priorität ermitteln, nachdem man die weggelassenen Größer-Zeichen (gedanklich) hinzugefügt hat.

EBNF

〈primary-expression 〉 ::=

'1' |

'(' 〈expression 〉 ')'.

EBNF

〈primary-expression 〉 ::=

'1' |

'(' > 〈expression 〉 > ')'.

auf deutsch

„Eine 〈primary-expression 〉 ist entweder das Zeichen '1' oder eine Folge aus einer Klammer auf '(', einer 〈expression 〉 und einer Klammer zu ')'.“

Oft werden Alternativen untereinander (auf mehrere Zeilen) geschrieben und Sequenzen nebeneinander (auf einer Zeile), obwohl die Art und Weise der Aufteilung eines EBNF-Termes auf Zeilen keine Bedeutung hat.

Klammern

Um Operanden zu kennzeichnen können Klammern  verwendet werden.

EBNF

〈Vorzeichenausdruck 〉 ::=

( '+' | '-' )( '0' | '1' ).

auf deutsch

„Ein Vorzeichenausdruck besteht aus einem Vorzeichen ('+' oder '-') gefolgt von einer Ziffer ('0' oder '1').“

In Aufbaudiagrammen  sind solche Klammern nicht nötig, da die Führung der Pfeile es erlaubt, das Gemeinte auch ohne Klammern auszudrücken.

Referenzen

In einem Syntaxdiagramm werden Bezüge auf eine Kategorie durch eckige Kästchen dargestellt.

Syntaxdiagramm

Vorzeichenausdruck
     .-.     .---------.
--->( - )--->| Literal |--->
     '-'     '---------'

In einem EBNF-Term werden Bezüge durch Verwendung des Namens einer Kategorie (in spitzen Klammern) hergestellt.

EBNF

〈Vorzeichenausdruck 〉 ::=

'-' 〈Literal 〉.

auf deutsch

„Ein Vorzeichenausdruck besteht aus einem Minuszeichen '-' und einem folgenden 〈Literal 〉.“

Beispiel

〈latin_letter 〉 ::=

〈lower_case_latin_letter 〉 | 〈upper_case_latin_letter 〉.

〈statement 〉 ::=

〈labeled-statement 〉 |

〈compound-statement 〉 |

〈expression-statement 〉 |

〈selection-statement 〉 |

〈iteration-statement 〉 |

〈jump-statement 〉 .

〈primary-expression 〉 ::=

'1' |

'(' 〈expression 〉 ')'.

〈multiplicative-expression 〉 ::=

〈primary-expression 〉 |

〈multiplicative-expression 〉 '*' 〈primary-expression 〉 |

〈multiplicative-expression 〉 '/' 〈primary-expression 〉.

〈expression 〉 ::=

〈multiplicative-expression 〉 |

〈expression 〉 '+' 〈multiplicative-expression 〉 |

〈expression 〉 '-' 〈multiplicative-expression 〉.

Wiederholungen

In einem Aufbaudiagramm wird die Möglichkeit des mehrfachen Durchlaufens eines Weges durch die Pfeilführung  ausgedrückt.

morphologisches Diagramm

Zeichenfolge
|-|--->.------------------.--->|-|
       ^                  |
       |   .---------.    |
       '---| Zeichen |<---'
           '---------'

In einem EBNF-Term wird etwas, das beliebig oft (auch nullmal!) wiederholt werden kann in geschweifte Klammern eingeschlossen.

EBNF

〈Textdatei 〉 ::=

{ 〈Zeile 〉 }.

auf deutsch

„Eine Textdatei besteht aus einer Folge beliebig vieler Zeilen.“

Diese Verwendung geschweifter Klammern ist nicht mit der Verwendung geschweifter Klammern in Apostrophen oder Anführungszeichen zu verwechseln, durch die ein wörtliche geschweifte Klammer ausgedrückt wird.

Optionen

In einem Aufbaudiagramm wird die Möglichkeit des optionalen Durchlaufens eines Weges durch die Pfeilführung  ausgedrückt.

morphologisches Diagramm

Optionales Zeichen
       .------------------.
       |                  |
       |   .---------.    v
|-|--->'---| Zeichen |----'--->|-|
           '---------'

In einem EBNF-Term wird etwas, das auch weggelassen werden kann, in eckige Klammern eingeschlossen.

EBNF

〈T  〉 ::=

'a' [ 'b' ] 'c'.

auf deutsch

„Ein 〈T  〉 besteht aus einem 'a' und einem 'c', zwischen denen noch ein 'b' stehen darf.“

Diese Schreibweise ist inzwischen so weit bekannt, daß sie sogar im Duden ohne Erklärung verwendet wird, etwa zur Angabe des Genitivs von „Wort“ als „Wort[e]s“.

weiteres Beispiel

〈expression-statement〉 ::=

[〈expression 〉] ';'.

Angaben außerhalb der EBNF

Bei der Beschreibung einer Sprache mit Hilfe von EBNF-Produktionsregeln werden verschiedene Regelung außerhalb der EBNF-Notation festgelegt:

• Ob ein Terminalsymbol ein Zeichen oder eine lexikalische Einheit darstellen soll.
• Ob/Wann Leerraum zwischen Terminalsymbolen erlaubt ist.
• Wann Leerraum zwischen Terminalsymbolen notwendig ist.
• Ob Groß- und Kleinschreibung signifikant ist.
• Wie Leerraum realisiert wird wird..
• Wie Text auf mehrere Zeilen aufgeteilt werden kann.

Wenn eine Grammatik für eine Sprache angegeben werden soll, dann muß noch gesagt werden, welches Symbol ein „Programm“ dieser Sprache darstellen soll. Auch dieses sogenannte Startsymbol  wird außerhalb der EBNF-Notation festgelegt.

Quellen zur BFN  und zur EBNF  ⃗

Die hier vorgestellte Notation ähnelt der BNF  oder ENBF. Von diesen Notationen gibt es aber verschiedenen Varianten, zu denen hier einige Quellen angegeben sind:

Naur 60 Peter Naur  (ed.), Revised Report on the Algorithmic Language ALGOL 60, Communications of the ACM, Vol. 3 No. 5, pp. 299–314, 1960-05.

RFC 2234 Overell Crocker, Augmented BNF for Syntax Specifications: ABNF, RFC 2234, 1997-11.

ISO 14977 ISO/IEC 14977:1996(E), Information technology: Syntactic metalanguage ISO/IEC 14977 : 1996(E), Extended BNF.

Seltener gebrauchte Notationen ⃗

In diesem Abschnitt werden noch einige Notationen für spezielle Fälle festgelegt, die aber selten benötigt und verwendet werden.

Groß- und Kleinschreibung ⃗

Normalerweise wird außerhalb der EBNF-Notation angegeben, ob Großschreibung signifikant ist.

Falls in einem speziellen Falle doch einmal innerhalb der EBNF-Notation ausgedrückt werden soll, daß Großschreibung nicht  signifikant ist, so wird dem Terminalsymbol direkt ein senkrechter Strich  „|“ vorangestellt.

EBNF

|'AB'

Soll  zwischen Groß- und Kleinschreibung unterschieden werden, so wird den verwendeten Hochkommas direkt ein Gleichheitszeichen  „=“ vorangestellt, falls dies in einem Einzelfall nötig ist oder betont werden soll.

EBNF

='AB'

Spezielle Schreibweisen für Zeichen ⃗

Ein einzelnes Zeichen kann auch durch seine dezimale Unicode-Codepunkt-Kennzahl angegeben werden.

EBNF

%d65

auf deutsch

ein großes A

Alternativ kann auch eine hexadezimale Unicode-Codepunkt-Kennzahl angegeben werden.

EBNF

%x41

auf deutsch

ein großes A

Bereiche von Zeichen ⃗

Zeichenbereiche können angegeben werden, wenn es sich um Teilbereiche des englischen Alphabets oder der Ziffern von „0“ bis „9“ handelt.

EBNF

'g' - 'm'.

EBNF

'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm'

auf deutsch

„Ein Zeichen von 'g' (einschließlich) bis 'm' (einschließlich).“

Leeraum ⃗

Ob Leerraum zwischen den einzelnen Bestandteilen einer Sequenz erlaubt ist, wird in der Regel zusätzlich  zu den EBNF-Produktionsregeln angegeben. Falls in einem bestimmten Fall ausnahmsweise kein  Leerraum erlaubt ist oder das Verbot des Leerraums besonders betont werden soll, schreiben wir einen Doppelpunkt  „:“ an die Stelle eines Größer-Zeichens.

EBNF

〈Doppelgleich 〉 ::=

'=' : '='.

Falls in einem bestimmten Fall ausnahmsweise Leerraum erlaubt ist  oder die Möglichkeit der Verwendung von Leerraums besonders betont werden soll, schreiben wir einen Grundstrich  „_“ an Stelle eines Größer-Zeichens.

EBNF

〈Doppelgleich 〉 ::=

'=' _ '='.

Wann Leerraum zwischen den einzelnen Bestandteilen einer Sequenz notwendig  ist, wird in der Regel zusätzlich  zu den EBNF-Produktionsregeln angegeben. Falls die Notwendigkeit des Leerraums besonders betont werden soll, schreiben wir zwei Grundstriche  „_“ an Stelle eines Größerzeichens.

EBNF

〈Doppelgleich 〉 ::=

'=' _ _ '='.

Beschreibungen ⃗

Beschreibende Nichtterminalsymbole, die nicht weiter definiert sind, werden durch eine Tilde »~« nach der öffnenden spitzen Klammer gekennzeichnet.

〈preprocessing-token 〉 ::=

〈~each non-white-space character that cannot be one of the above 〉.