Backus-Naur-Form

Version vom 8. November 2026, 08:59 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „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: :<code><begriff> ::= Alternativen</code> Links steht das Nichtterminal, rechts stehen seine Alternativen. Eine BNF-Regel fasst die Regeln eines Nichtterminals zus…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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 Zeichen 0 bis 9.

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:

  1. Das Nichtterminal [math]\displaystyle{ S }[/math] bekommt den Namen <ausdruck>, auf der linken und auf der rechten Seite.
  2. Der Pfeil [math]\displaystyle{ \to }[/math] wird zu ::=.
  3. Die Terminale ( und ) bleiben stehen.
  4. Der Strich [math]\displaystyle{ \mid }[/math] wird zu |.
  5. Das leere Wort bleibt ε.

Es entsteht:

<ausdruck> ::= ( <ausdruck> ) <ausdruck> | ε