Backus-Naur-Form: Unterschied zwischen den Versionen
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…“ |
Keine Bearbeitungszusammenfassung |
||
| Zeile 2: | Zeile 2: | ||
==Definition== | ==Definition== | ||
Die '''Backus-Naur-Form''' ist eine Schreibweise für [[Kontextfreie Grammatik|kontextfreie Grammatiken]]. Jede Regel hat die Form: | Die '''Backus-Naur-Form''' ist eine Schreibweise für [[Kontextfreie Grammatik|kontextfreie Grammatiken]]. Wie jede [[Formale Grammatik|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: | ||
:<code><begriff> ::= Alternativen</code> | :<code><begriff> ::= Alternativen</code> | ||
Links steht das Nichtterminal, rechts stehen seine Alternativen. Eine BNF-Regel fasst die Regeln eines Nichtterminals zusammen, so wie <math>A \to \beta_1 \mid \beta_2</math> in der Schreibweise der Grammatiken. Das Startsymbol ist meist das Nichtterminal der ersten Regel. | Links steht das Nichtterminal, rechts stehen seine Alternativen. Eine BNF-Regel fasst die Regeln eines Nichtterminals zusammen, so wie <math>A \to \beta_1 \mid \beta_2</math> in der Schreibweise der Grammatiken. Dabei steht <math>A</math> für ein Nichtterminal, und <math>\beta_1</math> und <math>\beta_2</math> stehen für zwei rechte Seiten. Das Startsymbol ist meist das Nichtterminal der ersten Regel. | ||
==Schreibweise== | ==Schreibweise== | ||
| Zeile 22: | Zeile 22: | ||
| Zeichen ohne spitze Klammern || Terminale, sie stehen direkt da | | Zeichen ohne spitze Klammern || Terminale, sie stehen direkt da | ||
|- | |- | ||
| <code>ε</code> || leeres Wort, die Alternative enthält kein Zeichen | | <code>ε</code> || [[Wort#Leeres Wort|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. | 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 <code>⇒</code> geschrieben. | |||
==Erweiterte Backus-Naur-Form== | ==Erweiterte Backus-Naur-Form== | ||
Die '''erweiterte Backus-Naur-Form''' (EBNF) ergänzt | Die '''erweiterte Backus-Naur-Form''' (EBNF) ergänzt Symbole, die Regeln verkürzen: | ||
{| class="wikitable" | {| class="wikitable" | ||
| Zeile 38: | Zeile 40: | ||
|- | |- | ||
| <code>( ... )</code> || Gruppierung: Der Inhalt zählt als ein Element, etwa für Alternativen | | <code>( ... )</code> || Gruppierung: Der Inhalt zählt als ein Element, etwa für Alternativen | ||
|- | |||
| <code>" ... "</code> || Terminal in Anführungszeichen | |||
|} | |} | ||
Die EBNF beschreibt dieselben Sprachen wie die BNF. Jede EBNF-Regel lässt sich mit zusätzlichen Nichtterminalen in die BNF | 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 <code>|</code>. | ||
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 <code>[ A ]</code> wird durch ein neues Nichtterminal mit den Alternativen <code>ε | A</code> ersetzt. Ebenso möglich sind zwei Alternativen der ganzen Regel: eine mit und eine ohne <code>A</code>. | |||
* Eine Wiederholung <code>{ A }</code> wird durch ein neues Nichtterminal ersetzt, dessen Regel sich selbst verwendet: Seine Alternativen sind <code>ε</code> und <code>A</code> gefolgt vom neuen Nichtterminal. | |||
* Eine Gruppierung <code>( A | B )</code> wird durch ein neues Nichtterminal mit den Alternativen <code>A | B</code> ersetzt. | |||
* Die Anführungszeichen entfallen. Die Terminale stehen in der BNF direkt da. | |||
==Beispiele== | ==Beispiele== | ||
| Zeile 71: | Zeile 81: | ||
Die Regel für <code><ziffern></code> wird zweimal angewendet: zuerst mit der zweiten Alternative, dann mit der ersten. | Die Regel für <code><ziffern></code> wird zweimal angewendet: zuerst mit der zweiten Alternative, dann mit der ersten. | ||
Dieselben Zahlen lassen sich in der erweiterten Form kürzer beschreiben: | |||
<syntaxhighlight lang="text"> | |||
<zahl> ::= [ <vorzeichen> ] <ziffer> { <ziffer> } | |||
<vorzeichen> ::= "+" | "-" | |||
<ziffer> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | |||
</syntaxhighlight> | |||
Das Vorzeichen ist optional. Danach folgt eine Ziffer, auf die beliebig viele weitere Ziffern folgen dürfen. Die Regel für <code><ziffern></code> entfällt. In den Regeln für <code><vorzeichen></code> und <code><ziffer></code> stehen die Terminale jetzt in Anführungszeichen. | |||
===Wörter mit der Backus-Naur-Form prüfen=== | |||
Mit den Regeln für <code><zahl></code> in der BNF aus dem vorigen Beispiel werden vier Zeichenfolgen geprüft. Eine Zeichenfolge ist eine ganze Zahl, wenn sie sich aus <code><zahl></code> ableiten lässt. | |||
{| class="wikitable" | |||
! Zeichenfolge !! Prüfung !! Ergebnis | |||
|- | |||
| <code>+0</code> || <code><zahl></code> wird zu <code><vorzeichen> <ziffern></code>. Das Vorzeichen liefert <code>+</code>, <code><ziffern></code> wird über <code><ziffer></code> zu <code>0</code>. || ableitbar | |||
|- | |||
| <code>305</code> || <code><zahl></code> wird zu <code><ziffern></code>. Die zweite Alternative von <code><ziffern></code> wird zweimal angewendet und liefert jeweils eine Ziffer mit weiteren Ziffern. Die erste Alternative von <code><ziffern></code> liefert die letzte Ziffer. || ableitbar | |||
|- | |||
| <code>--5</code> || Vor den Ziffern erlaubt die Regel für <code><zahl></code> höchstens ein Vorzeichen. Das zweite <code>-</code> ist keine Ziffer. || nicht ableitbar | |||
|- | |||
| <code>4+2</code> || Ein Vorzeichen steht nur am Anfang. Hinter der ersten Ziffer lässt die Regel für <code><ziffern></code> nur weitere Ziffern zu. || nicht ableitbar | |||
|} | |||
Die Ableitung von <code>305</code> ausgeschrieben: | |||
<syntaxhighlight lang="text"> | <syntaxhighlight lang="text"> | ||
<zahl> | <zahl> ⇒ <ziffern> | ||
⇒ <ziffer><ziffern> | |||
⇒ 3<ziffern> | |||
⇒ 3<ziffer><ziffern> | |||
⇒ 30<ziffern> | |||
⇒ 30<ziffer> | |||
⇒ 305 | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Auch die leere Zeichenfolge ist keine ganze Zahl, denn jede Alternative von <code><ziffern></code> enthält mindestens eine Ziffer. | |||
===Grammatik in die Backus-Naur-Form übertragen=== | ===Grammatik in die Backus-Naur-Form übertragen=== | ||
| Zeile 92: | Zeile 133: | ||
<syntaxhighlight lang="text"> | <syntaxhighlight lang="text"> | ||
<ausdruck> ::= ( <ausdruck> ) <ausdruck> | ε | <ausdruck> ::= ( <ausdruck> ) <ausdruck> | ε | ||
</syntaxhighlight> | |||
===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 <code>K</code> oder <code>E</code>, zum Beispiel <code>2K</code> oder <code>1E</code>. Die Regel für <code><ziffer></code> ist dieselbe wie im ersten Beispiel. In der erweiterten Form lautet die Regel für einen Posten: | |||
<syntaxhighlight lang="text"> | |||
<posten> ::= <ziffer> ( "K" | "E" ) | |||
</syntaxhighlight> | |||
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: <code><ziffer> "K" | "E"</code> beschreibt eine Ziffer mit <code>K</code> oder ein einzelnes <code>E</code> ohne Ziffer. | |||
In der BNF ohne Erweiterungen übernimmt ein neues Nichtterminal <code><taste></code> die Gruppe, und die Anführungszeichen entfallen: | |||
<syntaxhighlight lang="text"> | |||
<posten> ::= <ziffer> <taste> | |||
<taste> ::= K | E | |||
</syntaxhighlight> | |||
Beide Fassungen beschreiben dieselben Posten: <code>2K</code> und <code>7E</code> gehören dazu. <code>K</code> gehört nicht dazu, weil die Ziffer fehlt, und <code>2KE</code> 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 <code>{4;0;7}</code>. Die Menge ist hier eine Zeichenfolge ohne Leerzeichen. Mindestens eine Ziffer muss vorkommen. Die Regel für <code><ziffer></code> ist dieselbe wie im ersten Beispiel. In der erweiterten Form genügt eine Regel: | |||
<syntaxhighlight lang="text"> | |||
<menge> ::= "{" <ziffer> { ";" <ziffer> } "}" | |||
</syntaxhighlight> | |||
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 <code><rest></code> die Wiederholung. Es ist entweder leer oder besteht aus einem Semikolon, einer Ziffer und einem weiteren Rest: | |||
<syntaxhighlight lang="text"> | |||
<menge> ::= { <ziffer> <rest> } | |||
<rest> ::= ε | ; <ziffer> <rest> | |||
</syntaxhighlight> | |||
Hier sind die geschweiften Klammern gewöhnliche Terminale, denn die BNF ohne Erweiterungen kennt keine Wiederholungsklammern. Beide Fassungen beschreiben dieselbe Sprache. Für <code>{4;0}</code> wird <code><rest></code> zweimal ersetzt: zuerst durch <code>; <ziffer> <rest></code>, dann durch <code>ε</code>: | |||
<syntaxhighlight lang="text"> | |||
<menge> ⇒ {<ziffer><rest>} | |||
⇒ {4<rest>} | |||
⇒ {4;<ziffer><rest>} | |||
⇒ {4;0<rest>} | |||
⇒ {4;0} | |||
</syntaxhighlight> | </syntaxhighlight> | ||
[[Kategorie:Formale Sprachen]] | [[Kategorie:Formale Sprachen]] | ||
[[Kategorie:AHR I Informatik LK]] | [[Kategorie:AHR I Informatik LK]] | ||