Die Backus-Naur-Form  (BNF, EBNF)

Syntax

Die Syntax  einer formalen Sprache ist eine Menge von Texten  (Zeichenfolgen).

Diese Menge beschreibt sozusagen die in der Sprache möglichen Äußerungen, wie beispielsweise Programme. Ihre Elemente nennen wir auch die syntaktisch-korrekten Texte.

Grammatik

Eine vollständige Aufzählung aller syntaktisch-korrekter Texte ist oft schwierig oder nicht möglich. Daher beschreibt man die syntaktisch-korrekten Text oft, ohne sie alle aufzuzählen.

Die Grammatik  einer formalen Sprache ist eine Beschreibung der Syntax  dieser formalen Sprache.

Die Erweiterte Backus-Naur-Form  (EBNF )

In dieser Lektion wird eine Sprache zur Syntaxbeschreibung vorgestellt, die Erweiterte Backus-Naur-Form  (EBNF ) genannt wird und auf der Backus-Naur-Form  (BNF ) beruht. Allerdings gibt es verschiedene Varianten der erweiterten Backus-Naur-Form, so daß Angaben aus anderen Quellen sich mehr oder weniger von den Angaben dieser Lektion unterscheiden könnten.

Terminalsymbole

In der hier verwendeten Variante der Backus-Naur-Form (BNF ) wird eine Menge mit genau einem Text durch Schreibung des Textes in Hochkommas  angegeben. So ist '7' beispielsweise die Menge { »7« }, also die Menge mit dem Zeichen »7«.

Übungsfrage Wie viele Elemente enthält die Menge '1'? Wie viele Elemente enthält die Menge '2'?

Ein solche Angabe einer Menge wird ein Terminalsymbol  genannt.

Produktionen

Durch eine Produktion  wird eine Inklusionsrelation zwischen zwei Mengen angegeben. Dabei steht links eine zu beschreibende Mengenbezeichnung in spitzen Klammern, die Nichtterminalsymbol  genannt wird, und rechts eine Teilmenge. So besagt die folgende Produktion, daß die Menge 〈Ziffer 〉 eine Obermenge der Menge { »7« } ist. Etwas freier formuliert besagt diese Produktion also, daß »7« eine Ziffer ist oder als Ziffer gelten solle. Man sagt auch, »7« sei eine Realisierung  des Nichtterminalsymbols »Ziffer«.

〈Ziffer 〉 ::=

'7'.

Produktionen werden hier durch das Zeichen ».« beendet.

Ein Nichtterminalsymbol kann auch kurz Symbol  genannt werden, wenn dadurch keine Mißverständnisse zu befürchten sind.

Ein Nichtterminalsymbol und ein Terminalsymbol können dieselbe Menge bezeichnen, wie dies bei dem Nichtterminalsymbol 〈Ziffer 〉 und dem Terminalsymbol '7' gemäß der letzten Produktion der Fall ist.

Übungsaufgabe Schreiben Sie eine Produktion, die sinngemäß besagt „»8« ist eine Ziffer“. Schreiben Sie eine Produktion, die sinngemäß besagt „»A« ist ein Buchstabe.“. Schreiben Sie eine Produktion, die sinngemäß besagt „»+« ist ein Operator.“.

Mehrere Produktionen eines Symbols

Zu einem Symbol kann es mehrere Produktionen  geben, die dann alle gleichzeitig gelten.

〈runde Klammer 〉 ::=

'('.

〈runde Klammer 〉 ::=

')'.

Eine vollständige Liste von Produktionen nennt alle  Teilmengen einer Symbols.

Das Symbol 〈runde Klammer 〉 läßt sich beispielsweise auch in der klassischen Mengenschreibweise notieren, wenn man annimmt, die obige Liste von Produktionen sei vollständig.

〈runde Klammer 〉 = { "(", ")" }

Oft kann man dem Zusammenhang  entnehmen, wann eine Liste von Produktionen vollständig sein soll. Wird eine Sprache durch eine Liste von Produktionen beschrieben, so ist die gesamte Liste eine vollständige Liste von Produktionen, da sonst die Sprachbeschreibung unvollständig wäre.

Übungsaufgabe Schreiben Sie eine Produktion, die eckige Klammern beschreibt. Schreiben Sie eine Produktion, die einige Operatoren beschreibt (dabei sollen die Operatoren für die vier Grundrechenarten berücksichtigt werden).

Aufzählungen

Durch den senkrechten Strich können Alternativen auch auf der rechten Seite einer einzigen Produktion angegeben werden. (Er stellt die Mengenvereinigung dar.) Damit kann die zuvor beschriebene Menge 〈runde Klammer〉 etwas kürzer geschrieben werden.

〈runde Klammer 〉 ::=

'(' | ')'.

Sprich „Eine runde Klammer kann durch '(' oder durch ')' gebildet werden." Die vorangehende Menge ist in klassischer Mengenschreibweise also auch wieder die folgende.

〈runde Klammer〉 = { »(«, »)« }

Ein Nichtterminalsymbol 〈Ziffer 〉 läßt sich beispielsweise durch die folgende vollständige Liste von Produktionen beschreiben.

〈Ziffer 〉 ::=

'0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'.

Leerraum

Leerzeichen oder Zeilenumbrüche außerhalb von Terminalsymbolen sollen in Produktionen keine Bedeutung haben. Daher würde auch die folgende Produktion die Ziffern von Null bis Neun angeben.

〈Ziffer 〉 ::=

'0'      |      '1'      |      '2' |
'3' | '4' | '5' | '6' | '7' | '8' | '9'.

Beispiel “type-qualifier”

In der ISO-C-Norm ISO/IEC 9899:1999 (E)  gibt es Wörter zur Bestimmung von Datentypen. Sie werden folgendermaßen definiert.

〈type-qualifier〉 ::=

'const' | 'restrict' | 'volatile' .

Sequenzen

Wenn A  und B  zwei Mengen sind, so soll die Sequenzmenge A ×B  die Menge aller Hintereinanderschreibungen »ab« sein, wobei »a« ein Element der Menge A und »b« ein Element der Menge B ist. So ist die Sequenzmenge '7'×'8' beispielsweise die Menge '78'. Denn da beide Mengen nur jeweils ein Element haben, gibt es nur diese eine Möglichkeit eine Sequenz aus beiden Mengen in der gegebenen Reihenfolge zu bilden.

〈Zehn 〉 ::=

'1'×'0'.

Übungsaufgabe Wie viele Elemente hat die Menge '7' '89'?

Wenn keine Mißverständnisse möglich sind, so kann das Kreuz »×« für die Hintereinanderschreibung auch weggelassen oder durch ein Leerzeichen ersetzt werden.

〈Zehn 〉 ::=

'1' '0'.

Prioritäten

Die Hintereinanderschreibung »×« hat höhere Priorität (Bindungskraft) als eine Alternative. Daher wird bezeichnet das folgende Beispiel die Textmenge { "A", "BC" } und nicht etwa { "AB", "AC" }.

〈Beispiel 〉 ::=

'A' | 'B'×'C'.

Klammern

Eine Menge kann immer in Klammern geschrieben werden. So kann in dem folgenden Beispiel klargestellt werden, daß »'A' | 'B'« als eine Menge gemeint ist.

〈Beispiel 〉 ::=

( 'A'| 'B' )×'C'.

Falls beide Menge mehrere Elemente haben, so entstehen interessantere Kombinationsmöglichkeiten.

〈Zahl mit Vorzeichen 〉 ::=

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

Übungsaufgabe Wie viele Elemente hat die Menge 〈Zahl mit Vorzeichen 〉? Schreiben Sie die Menge ( '+' | '-' )×( '0' | '1' | '2' ) in der klassischen Aufzählungsschreibweise mit geschweiften Klammern.

Symbole auf der rechten Seite

Auch Nichtterminalsymbole können auf der rechten Seite einer Produktion verwendet werden. So können Produktionen gegliedert werden.

〈Vorzeichen 〉 ::=

( '+' | '-' ).

〈Ziffer 〉 ::=

( '0' | '1' | '2' ).

〈Ausdruck 〉 ::=

〈Vorzeichen 〉 〈Ziffer 〉.

Auf der rechten Seite kann für jede Produktion auch wieder ihre bisherige Darstellung durch Operatoren und Terminalsymbole eingesetzt werden. Dann ergibt sich für 〈Ausdruck 〉 wieder die vorherige Produktion.

〈Ausdruck 〉 ::=

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

Man beachte, daß die mehrmalige Verwendung des gleichen  Nichtterminalsymbols nicht  bedeutet, daß bei jeder einzelnen Verwendung dieses Nichtterminalsymbols die gleiche Ersetzung durchzuführen ist.

〈Zweiklammern 〉 ::=

〈runde Klammer 〉 〈runde Klammer 〉.

Das Nichtterminalsymbol 〈Zweiklammern〉 muß also nicht als Text "((" oder Text "))" geschrieben werden, auch der Text "()" oder der Text ")(" ist erlaubt, wobei für das Nichtterminalsymbol 〈runde Klammer 〉 in der rechten Seite der Produktion von 〈Zweiklammern 〉 einmal eine öffnende runde Klammer und einmal eine schließende runde Klammer eingesetzt wurde.

Beispiel “letter ”

In einigen Programmiersprachen werden Buchstaben verwendet. Die Definition des Nichtterminalsymbols 〈letter 〉 (Englisch für „Buchstabe“) kann dann wie folgt aussehen.

〈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'.

〈latin_letter 〉 ::=

〈lower_case_latin_letter 〉 | 〈upper_case_latin_letter 〉.

Übungsaufgabe Definieren Sie eine Produktion für die Kategorie 〈Umlaut 〉. Dieses Nichtterminalsymbol soll die sechs Umlaute der deutschen Sprache (ohne das Eszett) enthalten.

Übungsaufgabe Welche Menge ist 〈Elf 〉 in klassischer Mengenschreibweise, wenn die folgende vollständige Liste von Produktionen gegeben ist?

〈w 〉 ::=

'1'.

〈Elf 〉 ::=

〈w 〉 〈w 〉.

Übungsaufgabe Welche Menge ist 〈Text 〉 als klassische Mengenaufzählung?

〈Teil 〉 ::=

'sonnen'.

〈Teil 〉 ::=

'blumen'.

〈Text 〉 ::=

〈Teil 〉 〈Teil 〉.

〈Text 〉 = { …?… }

Übungsaufgabe Welche Menge ist 〈x 〉 in klassischer Mengenschreibweise, wenn die folgende vollständige Liste von Produktionen gegeben ist?

〈x 〉::=

〈y 〉 〈z 〉.

〈z 〉::=

〈t 〉 〈t 〉.

〈t 〉::=

'u'.

〈y 〉::=

't'.

Beispiel “statement ”

In der Norm für die Programmiersprache C  "ISO/IEC 9899:1999 (E)" gibt es verschiedene Typen von Anweisungen (Anweisung heißt auf englisch „statement “). Die Menge aller Anweisungen wird dort folgendermaßen definiert.

〈statement 〉 ::=

〈labeled-statement 〉 |

〈compound-statement 〉 |

〈expression-statement 〉 |

〈selection-statement 〉 |

〈iteration-statement 〉 |

〈jump-statement 〉 .

Das Nichtterminalsymbol 〈statement 〉 umfaßt alle Anweisungen dieser Programmiersprache, und—wie man der hier wiedergegebenen Produktion entnehmen kann—gibt es sechs Möglichkeiten, wie eine Anweisung gebildet werden kann. Wie diese sechs Möglichkeiten im einzelnen aussehen, wird dann wieder durch weitere Produktionen bestimmt, die aber hier nicht mehr aus der Norm zitiert werden.

Startsymbole

Falls zur Beschreibung der Syntax einer formalen Sprache mehrere Symbole definiert werden, so ist nicht klar, welches  Symbol nun die Syntax der formalen Sprache angeben soll. Um dies klarzustellen, muß also noch gesagt werden, welches Symbols dies ist. Dieses Symbol wird Startsymbol  genannt. Zu einer Grammatik mit mehreren Symbolen gehört also immer noch die Angabe des Startsymbols.

Beispiel Startsymbol

Welchen Sinn könnte die folgende formale Sprache mit dem Startsymbol 〈x 〉 haben?

〈a 〉 ::=

'0' | '1' | '2'.

〈b 〉 ::=

〈a 〉 | '3' | '4' | '5'.

〈c 〉 ::=

〈b 〉 | '6' | '7' | '8' | '9'.

〈x 〉 ::=

〈a 〉 〈c 〉 ':' 〈b 〉 〈c 〉.

Rekursion

Es ist nicht ausgeschlossen, daß ein Symbol direkt oder indirekt auf der rechten Seite einer Produktion verwendet wird, auf deren linker Seite es steht. Die Bedeutung der sich so ergebenden Produktion kann aufgrund der bisherigen Regeln erschlossen werden.

Übungsaufgabe Ist der Text "x" eine Realisierung des Nichtterminalsymbols 〈S 〉 der folgenden Produktion? Wie sieht ein anderer Text aus, der dieses Nichtterminalsymbol realisiert? Wie kann man in Worten beschreiben, welche Elemente die Menge 〈S 〉 hat? Wieviele Elemente hat diese Menge?

〈S 〉 ::=

'x' | 'x' 〈S 〉.

Durch diese sogenannte Rekursion  können mit den bereits vorhandenen Grundregeln auch kompliziertere Ausdrücke und Vorrangregeln beschrieben werden. Die folgenden Produktionen sind eine Vereinfachung von Produktionen der Programmiersprache C.

〈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 〉.

Übungsaufgabe Erklären Sie, warum folgende Zeichenfolgen eine 〈expression 〉 sind: »1«, »1+1«, »1+1*1«, »1*1+1«, »1*(1+1)«. Wie bringen die obigen Produktionen die Regel „Punktrechnung geht vor Strichrechnung“ zum Ausdruck?

Übungsaufgabe Schreiben Sie eine Grammatik für Numerale natürlicher Zahlen und eine weitere Grammatik für Numerale ganzer Zahlen.

Zusatzaufgabe Schreiben Sie eine Grammatik für Numerale von Gleitkommazahlen.

Iteration

Die mögliche Wiederholung eines Gebildes kann durch Rekursion zum Ausdruck gebracht werden kann. Eine andere Möglichkeit, nämlich die Verwendung einer speziellen Schreibweise zur Notation der Wiederholung, soll jetzt noch vorgestellt werden.

Um eine mögliche Wiederholung eines Gebildes aus einer Textmenge anzugeben, kann diese auch in geschweifte  Klammern geschrieben werden.

〈x-Sequenz 〉 ::=

{ 'x' }.

Die geschweiften Klammern stehen innerhalb von Produktionen also nicht   für eine Menge. Sie können in der erweiterten Backus-Naur-Form diesem Sinne verwendet werden, weil die klassische Mengenschreibweise in der erweiterten Backus-Naur-Form nicht verwendet wird und daher keine Verwechslungen mit den geschweiften Klammern einer Mengenaufzählung möglich sind. Die Menge 〈x 〉 enthält also die Texte »«, »x«, »xx«, »xxx«, u.s.w.

Beispiel Eine Textdatei ist eine Folge von Zeilen.

〈Textdatei 〉 ::=

{ 〈Zeile 〉 }.

Übungsfrage Wie kann das Symbol 〈x-Sequenz 〉 rekursiv ohne Verwendung geschweifter Klammern beschrieben werden?

Optionen

Wenn ein Symbol verwendet werden kann  (aber nicht verwendet werden muß ) spricht man von einer möglichen (optionalen) Angabe. Zur Notation schließt man das optionale Symbol in eckige Klammern ein.

〈T  〉 ::=

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

Die voranstehende Produktion steht also für die folgende Textmenge.

〈T  〉 = { "ac", "abc" }

Übungsfrage Die eckigen Klammern sind nicht wirklich notwendig, sondern nur einer Vereinfachung. Wie kann das Symbol 〈T  〉 ohne Verwendung der eckigen Klammern beschrieben werden?

Beispiel “expression-statement ”

In der C -Norm "ISO/IEC 9899:1999 (E)" ist ein 〈expression-statement 〉 ein Semikolon, dem ein Ausdruck (〈expression 〉) vorangehen kann.

〈expression-statement〉 ::=

[〈expression 〉] ';'.

Kennzahlen für Zeichen

Falls Sonderzeichen nicht direkt als Text in einer Produktion geschrieben werden können oder sollen, so können sie durch ein Prozentzeichen, einen Basisspezifikator und ihre Unicode-Kennzahl  notiert werden. (Unicode legt für jedes Zeichen eine Kennzahl fest.) Der Basisspezifikator ist "d", "b" oder "x" für „dezimale“, „binäre“ bzw. „hexadezimale“ Zahlen. Er gibt an, in welchem Zahlensystem das folgende Numeral zu interpretieren ist, um die Kennzahl zu gewinnen.

〈x 〉 ::=

%d65.

Solch eine Spezifikation muß durch Leeraum von der Umgebung abgetrennt werden, wenn sonst Mißverständnisse möglich sind.

Diese Produktion beschreibt eine Menge mit dem Unicodezeichen 65 (Buchstabe "A") also die folgenden Menge.

〈x 〉={ "A" }

Da die Anführungszeichen in der BNF Texte begrenzen, können sie nicht selber in einem Text enthalten sein. Das normale Anführungszeichen kann aber durch "%d34" spezifiziert werden, das einfache Anführungszeichen durch "%d39". So beschreibt die folgende Produktion einen Text mit einem normalen Anführungszeichen, das in zwei einfachen Anführungszeichen eingeschlossen ist.

〈y 〉 ::=

%d39 %d34 %d39.

Die hier vorgestellte Notation kann auch dazu dienen, nicht druckbare Zeichen anzugeben, also Steuerzeichen, die keine graphische Darstellung haben.

Mehrere hintereinander zu schreibende Zeichen können durch einen Punkt getrennt hintereinander spezifiziert werden, ohne daß das Prozentzeichen und der Basisspezifikator »d« wiederholt werden müssen.

〈y 〉 ::=

%d65.67.

Das ist das gleiche wie folgende Schreibweise.

〈y 〉 ::=

%d65%d67.

Diese Produktion beschreibt eine Menge mit dem Unicodezeichen 65 (Buchstabe "A") gefolgt vom Unicodezeichen 67 (Buchstabe "C") also die folgenden Menge.

〈x 〉={ "AC" }

(Diese Schreibweise mit dem Prozentzeichen ist eine Erweiterung dieses Textes und wird in anderen EBNF-Varianten nicht verwendet.)

Bereiche von Zeichenkennzahlen

Mit numerisch spezifizierten Zeichenschlüsseln können auch Bereichsangaben verwendet werden.

〈x 〉 ::=

%d65–68.

Hierdurch werden dann Alternativen bestimmt: Für das Symbol kann also eines der Zeichen aus dem angegebenen Bereich gewählt werden. Die vorangehende Produktion ist also der folgenden gleich.

〈x 〉 ::=

%d65 | %d66 | %d67 | %d68.

Diese Produktion beschreibt eine Menge vom Unicodezeichen 65 (Buchstabe "A") bis zum Unicodezeichen 68 (Buchstabe "D") also die folgenden Menge.

〈x 〉={ "A", "B", "C", "D" }

Groß- und Kleinschreibung

Soll zwischen Groß- und Kleinschreibung nicht  unterschieden werden, so wird den verwendeten Hochkommas direkt ein $ vorangestellt.

〈x 〉 ::=

$'AB'.

Diese Produktion beschreibt also die folgenden Menge.

x  = { "AB", "Ab", "aB", "ab" }

Falls in einer formalen Sprache grundsätzlich nie zwischen Groß- und Kleinschreibung unterschieden werden soll, so kann auch auf die Angabe des Dollarzeichens verzichtet werden, wenn dies im Begleittext der Grammatik angegeben wird.

(Diese Schreibweise mit dem Dollarzeichen ist eine Erweiterung dieses Textes und wird in anderen EBNF-Varianten nicht verwendet.)

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

Hier soll die Beschreibung in englischer Sprache für einen Leser, der englische Texte verstehen kann, eindeutig und konsistent angeben, welche Menge gemeint ist.

(Diese Schreibweise mit der Tilde ist eine Erweiterung dieses Textes und wird in anderen EBNF-Varianten nicht verwendet.)

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.