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. 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. 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.
Erweiterte Backus-Naur-Form
Die erweiterte Backus-Naur-Form (EBNF) ergänzt drei 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 |
Die EBNF beschreibt dieselben Sprachen wie die BNF. Jede EBNF-Regel lässt sich mit zusätzlichen Nichtterminalen in die BNF übersetzen: Eine Option bekommt eine leere Alternative, eine Wiederholung eine rekursive Regel mit leerer Alternative.
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.
Dieselbe Zahl lässt sich in der erweiterten Form kürzer beschreiben:
<zahl> ::= [<vorzeichen>] <ziffer> {<ziffer>}
Das Vorzeichen ist optional. Danach folgt eine Ziffer, auf die beliebig viele weitere Ziffern folgen dürfen. Die Regel für <ziffern> entfällt. Die Regeln für <vorzeichen> und <ziffer> bleiben unverändert.
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> | ε