Backus-Naur-Form
Die Backus-Naur-Form (BNF) ist eine knappe Schreibweise für Grammatiken. Programmiersprachen werden damit in ihren Handbüchern festgelegt.
Definition
Die Backus-Naur-Form ist eine Schreibweise für kontextfreie Grammatiken. Wie jede formale Grammatik unterscheidet sie Nichtterminale und Terminale: Nichtterminale sind Platzhalter, die noch durch Regeln ersetzt werden. Terminale sind die Zeichen, aus denen die fertigen Wörter bestehen. Jede Regel hat die Form:
<begriff> ::= Alternativen
Links steht das Nichtterminal, rechts stehen seine Alternativen. Eine BNF-Regel fasst die Regeln eines Nichtterminals zusammen, so wie [math]\displaystyle{ A \to \beta_1 \mid \beta_2 }[/math] in der Schreibweise der Grammatiken. Dabei steht [math]\displaystyle{ A }[/math] für ein Nichtterminal, und [math]\displaystyle{ \beta_1 }[/math] und [math]\displaystyle{ \beta_2 }[/math] stehen für zwei rechte Seiten. Das Startsymbol ist meist das Nichtterminal der ersten Regel.
Schreibweise
Die BNF kommt mit wenigen Symbolen aus:
| Symbol | Bedeutung |
|---|---|
<begriff> |
Nichtterminal, in spitzen Klammern |
::= |
„ist definiert als“, trennt das Nichtterminal von seinen Alternativen |
| |
Alternative: Eine der Möglichkeiten wird gewählt |
| Zeichen ohne spitze Klammern | Terminale, sie stehen direkt da |
ε |
leeres Wort, die Alternative enthält kein Zeichen |
Eine Regel darf ihr eigenes Nichtterminal auf der rechten Seite verwenden. Das ist eine Rekursion. So lassen sich beliebig lange Wiederholungen beschreiben. Leerzeichen zwischen den Symbolen dienen nur der Lesbarkeit.
Ein Wort gehört zur beschriebenen Sprache, wenn es sich aus dem Startsymbol ableiten lässt: In jedem Schritt wird ein Nichtterminal durch eine seiner Alternativen ersetzt, bis nur noch Terminale übrig sind. Ein solcher Schritt wird mit dem Pfeil ⇒ geschrieben.
Erweiterte Backus-Naur-Form
Die erweiterte Backus-Naur-Form (EBNF) ergänzt Symbole, die Regeln verkürzen:
| Symbol | Bedeutung |
|---|---|
[ ... ] |
Option: Der Inhalt darf einmal vorkommen oder fehlen |
{ ... } |
Wiederholung: Der Inhalt kommt beliebig oft vor, auch keinmal |
( ... ) |
Gruppierung: Der Inhalt zählt als ein Element, etwa für Alternativen |
" ... " |
Terminal in Anführungszeichen |
Weil eckige, geschweifte und runde Klammern in der erweiterten Form eine eigene Bedeutung haben, stehen Terminale dort in Anführungszeichen. Das ist zwingend, wenn eine Klammer selbst ein Terminal der Sprache ist. Innerhalb der Klammern dürfen Alternativen stehen, getrennt durch |.
Die EBNF beschreibt dieselben Sprachen wie die BNF. Jede EBNF-Regel lässt sich mit zusätzlichen Nichtterminalen in die BNF überführen:
- Eine Option
[ A ]wird durch ein neues Nichtterminal mit den Alternativenε | Aersetzt. Ebenso möglich sind zwei Alternativen der ganzen Regel: eine mit und eine ohneA. - Eine Wiederholung
{ A }wird durch ein neues Nichtterminal ersetzt, dessen Regel sich selbst verwendet: Seine Alternativen sindεundAgefolgt vom neuen Nichtterminal. - Eine Gruppierung
( A | B )wird durch ein neues Nichtterminal mit den AlternativenA | Bersetzt. - Die Anführungszeichen entfallen. Die Terminale stehen in der BNF direkt da.
Beispiele
Ganze Zahl beschreiben
Eine ganze Zahl besteht aus einer oder mehreren Ziffern. Davor darf ein Vorzeichen stehen. In der BNF lautet die Beschreibung:
<zahl> ::= <ziffern> | <vorzeichen> <ziffern>
<ziffern> ::= <ziffer> | <ziffer> <ziffern>
<vorzeichen> ::= + | -
<ziffer> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<zahl>: Eine Zahl besteht aus Ziffern, mit oder ohne Vorzeichen davor.<ziffern>: Das ist eine Ziffer oder eine Ziffer, auf die weitere Ziffern folgen. Die Regel verwendet sich selbst und beschreibt so beliebig viele Ziffern.<vorzeichen>: Das Vorzeichen ist+oder-.<ziffer>: Eine Ziffer ist eines der Zeichen0bis9.
Die Zahl -12 entsteht, indem immer das erste Nichtterminal von links ersetzt wird:
<zahl> ⇒ <vorzeichen><ziffern>
⇒ -<ziffern>
⇒ -<ziffer><ziffern>
⇒ -1<ziffern>
⇒ -1<ziffer>
⇒ -12
Die Regel für <ziffern> wird zweimal angewendet: zuerst mit der zweiten Alternative, dann mit der ersten.
Dieselben Zahlen lassen sich in der erweiterten Form kürzer beschreiben:
<zahl> ::= [ <vorzeichen> ] <ziffer> { <ziffer> }
<vorzeichen> ::= "+" | "-"
<ziffer> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Das Vorzeichen ist optional. Danach folgt eine Ziffer, auf die beliebig viele weitere Ziffern folgen dürfen. Die Regel für <ziffern> entfällt. In den Regeln für <vorzeichen> und <ziffer> stehen die Terminale jetzt in Anführungszeichen.
Wörter mit der Backus-Naur-Form prüfen
Mit den Regeln für <zahl> in der BNF aus dem vorigen Beispiel werden vier Zeichenfolgen geprüft. Eine Zeichenfolge ist eine ganze Zahl, wenn sie sich aus <zahl> ableiten lässt.
| Zeichenfolge | Prüfung | Ergebnis |
|---|---|---|
+0 |
<zahl> wird zu <vorzeichen> <ziffern>. Das Vorzeichen liefert +, <ziffern> wird über <ziffer> zu 0. |
ableitbar |
305 |
<zahl> wird zu <ziffern>. Die zweite Alternative von <ziffern> wird zweimal angewendet und liefert jeweils eine Ziffer mit weiteren Ziffern. Die erste Alternative von <ziffern> liefert die letzte Ziffer. |
ableitbar |
--5 |
Vor den Ziffern erlaubt die Regel für <zahl> höchstens ein Vorzeichen. Das zweite - ist keine Ziffer. |
nicht ableitbar |
4+2 |
Ein Vorzeichen steht nur am Anfang. Hinter der ersten Ziffer lässt die Regel für <ziffern> nur weitere Ziffern zu. |
nicht ableitbar |
Die Ableitung von 305 ausgeschrieben:
<zahl> ⇒ <ziffern>
⇒ <ziffer><ziffern>
⇒ 3<ziffern>
⇒ 3<ziffer><ziffern>
⇒ 30<ziffern>
⇒ 30<ziffer>
⇒ 305
Auch die leere Zeichenfolge ist keine ganze Zahl, denn jede Alternative von <ziffern> enthält mindestens eine Ziffer.
Grammatik in die Backus-Naur-Form übertragen
Die kontextfreie Grammatik [math]\displaystyle{ S \to (S)S \mid \varepsilon }[/math] für korrekt geklammerte Ausdrücke wird in die BNF übertragen:
- Das Nichtterminal [math]\displaystyle{ S }[/math] bekommt den Namen
<ausdruck>, auf der linken und auf der rechten Seite. - Der Pfeil [math]\displaystyle{ \to }[/math] wird zu
::=. - Die Terminale
(und)bleiben stehen. - Der Strich [math]\displaystyle{ \mid }[/math] wird zu
|. - Das leere Wort bleibt
ε.
Es entsteht:
<ausdruck> ::= ( <ausdruck> ) <ausdruck> | ε
Gruppierung in der erweiterten Form verwenden
Die Bestellliste eines Kaffeeautomaten nennt für jedes Getränk einen Posten: zuerst die Anzahl als eine Ziffer, dann die Taste K oder E, zum Beispiel 2K oder 1E. Die Regel für <ziffer> ist dieselbe wie im ersten Beispiel. In der erweiterten Form lautet die Regel für einen Posten:
<posten> ::= <ziffer> ( "K" | "E" )
Die runden Klammern fassen die beiden Alternativen zu einem Element zusammen, das auf die Ziffer folgt. Ohne die Klammern hätte die Regel eine andere Bedeutung: <ziffer> "K" | "E" beschreibt eine Ziffer mit K oder ein einzelnes E ohne Ziffer.
In der BNF ohne Erweiterungen übernimmt ein neues Nichtterminal <taste> die Gruppe, und die Anführungszeichen entfallen:
<posten> ::= <ziffer> <taste>
<taste> ::= K | E
Beide Fassungen beschreiben dieselben Posten: 2K und 7E gehören dazu. K gehört nicht dazu, weil die Ziffer fehlt, und 2KE nicht, weil nur eine Taste erlaubt ist.
Erweiterte Form in die Backus-Naur-Form überführen
Eine Menge von Ziffern wird in geschweiften Klammern geschrieben, die Ziffern sind durch Semikolons getrennt, zum Beispiel {4;0;7}. Die Menge ist hier eine Zeichenfolge ohne Leerzeichen. Mindestens eine Ziffer muss vorkommen. Die Regel für <ziffer> ist dieselbe wie im ersten Beispiel. In der erweiterten Form genügt eine Regel:
<menge> ::= "{" <ziffer> { ";" <ziffer> } "}"
Die geschweiften Klammern in Anführungszeichen sind Terminale: Sie stehen wörtlich in jeder Menge. Die geschweiften Klammern ohne Anführungszeichen kennzeichnen die Wiederholung: Auf die erste Ziffer folgen beliebig oft ein Semikolon und eine weitere Ziffer.
In der BNF ohne Erweiterungen übernimmt ein neues Nichtterminal <rest> die Wiederholung. Es ist entweder leer oder besteht aus einem Semikolon, einer Ziffer und einem weiteren Rest:
<menge> ::= { <ziffer> <rest> }
<rest> ::= ε | ; <ziffer> <rest>
Hier sind die geschweiften Klammern gewöhnliche Terminale, denn die BNF ohne Erweiterungen kennt keine Wiederholungsklammern. Beide Fassungen beschreiben dieselbe Sprache. Für {4;0} wird <rest> zweimal ersetzt: zuerst durch ; <ziffer> <rest>, dann durch ε:
<menge> ⇒ {<ziffer><rest>}
⇒ {4<rest>}
⇒ {4;<ziffer><rest>}
⇒ {4;0<rest>}
⇒ {4;0}