1. Backus-Naur-Form (BNF)
Formale Sprachen werden durch Grammatiken eindeutig beschrieben. Die Backus-Naur-Form (BNF) ist eine Beschreibungssprache für solche Grammatiken. Sie kennt die Elemente "terminale Symbole", "nicht terminale Symbole" und "Produktionen".
Terminale Symbole sind Zeichen (Buchstaben, Zahlen, Sonderzeichen), die sich nicht weiter aufgliedern lassen. Nicht terminale Symbole (im Weiteren "Variablen" genannt) werden durch Produktionsregeln schrittweise in terminale Symbole überführt. Die Summe aller Produktionen bilden die Grammatik.
Eine Produktionsregel hat den Aufbau
Variable ::= Ausdruck.
Der Ausdruck auf der rechten Seite beschreibt dabei den Aufbau des nicht terminalen Symbols auf der linken Seite. Er besteht aus einer Aufzählung von terminalen und/oder nicht terminalen Symbolen. Variablen-Namen werden zur besseren Lesbarkeit in spitze Klammern gesetzt. Ein senkrechter Strich bedeutet "oder".
Ein Beispiel soll dies verdeutlichen. In der Programmiersprache C müssen Bezeichner folgenden Regeln folgen: "Bezeichner bestehen aus Ziffern, Buchstaben und Unterstrichen, wobei das erste Zeichen keine Ziffer sein darf".
Beispiele für gültige Bezeichner sind:
x, _x21, _a_b_c_, a1_b2
Beispiele für ungültige Bezeichner sind:
123, 2_a, 42bcd
Eine Grammatik gemäß BNF beschreibt die Regeln für Bezeichner so:
[1] <Bezeichner> ::= <Buchstabe> | _ | <Buchstabe> <Rest> | _ <Rest>
[2] <Rest> ::= <Buchstabe> | _ | <Ziffer> | <Buchstabe> <Rest>
| _ <Rest> | <Ziffer> <Rest>
[3] <Buchstabe> ::= A | ... | Z | a | ... | z
[4] <Ziffer> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Zu beachten ist dabei die Rekursion in Regel [2], die eine beliebige Anzahl weiterer Buchstaben, Ziffern und Unterstriche erlaubt. Regel [3] ist außerdem in einer Kurzform geschrieben, die eigentlich nicht Bestandteil der BNF ist.
[Zurück zum Inhaltsverzeichnis]
2. Erweiterte Backus-Naur-Form (EBNF)
Durch das Hinzufügen folgender Elemente wird aus der BNF die EBNF:
- Gruppierung durch Klammerung
- Optionalität
- Wiederholungen
Außerdem werden Variablen nicht in spitze Klammern gesetzt, dafür werden terminale Symbole von einfachen oder doppelten Anführungszeichen umschlossen.
Die Zeichen für Optionalität und Wiederholung haben folgende Bedeutung:
| ? | – | eines oder keines |
| * | – | beliebig viele (auch keines) |
| + | – | beliebig viele, mindestens jedoch eines |
Das obige Beispiel des C-Bezeichners wird in der EBNF so geschrieben:
[1] Bezeichner ::= (Buchstabe | '_') (Buchstabe | '_' | Ziffer)* [2] Buchstabe ::= 'A' | ... | 'Z' | 'a' | ... | 'z' [3] Ziffer ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Man sieht, dass man durch die Erweiterungen der EBNF eine Regel gegenüber der BNF einspart und zu einer kompakteren Darstellung kommt. Die "Rest"-Regel wird nicht mehr benötigt und die verbleibende "Bezeichner"-Regel ist kompakter und übersichtlicher formuliert und dadurch lesbarer als [1] und [2] in der BNF-Darstellung.