Erweiterte Backus-Naur-Form
Die Erweiterte Backus-Naur-Form, kurz EBNF ist eine Erweiterung der Backus-Naur-Form (BNF). Sie ist formale Metasyntax die benutzt wird um kontextfreie Grammatiken darzustellen, beispielsweise die Syntax von Programmiersprachen.
Motivation
Die BNF benötigt teilweise umständliche Konstrukte, um optionale Elemente, also Elemente, die ausgelassen werden dürfen, sowie sich wiederholende Elemente, darzustellen. In der Spezifikation von PL/1 wurden bereits eckige Klammern "[...]" für Optionen eingeführt. Niklaus Wirth hat in der Definition der Sprache Pascal zusätzlich geschweifte Klammern "{...}" für Wiederholungen in die BNF eingeführt und nannte dies extended BNF (erweiterte BNF).
Einführung mit Beispiel
Die BNF sowie auch die EBNF bestehen aus zwei Arten von wichtigen Symbolen. Da wären zunächst die Terminalsymbole und die Nichtterminalsymbole.
Die EBNF ist so aufgebaut, dass auf der linken Seite immer ein Nichtterminalsymbol steht. Dann folgt ein Gleichheitszeichen (=) als Zuweisung und auf der rechten Seite (also das was zugewiesen wird) ist eine Folge von Terminal- und Nichtterminalsymbolen.
Terminalsymbol
Ein Terminalsymbol ist, wie der Name schon sagt, ein Symbol das terminiert. Es ist in der EBNF das letzte Glied in der Kette. Dieses Zeichen kann nicht weiter aufgelöst, aufgedröselt werden. Es steht also für sich selbst!
Nichtterminalsymbol
Die Nichtterminalsymbole sind Platzhalter (Namen) die sich wiederum aus anderen Terminal- oder Nichtterminalsymbolen zusammen setzen können. Ein Nichtterminalsymbol besteht also immer aus einer Folge von Terminal- und/oder Nichtterminalsymbolen.
Im Folgenden ein einfaches Beispiel zu den natürlichen Zahlen wodurch die Definition von Terminal- und Nichtterminalsymbol verständlicher werden dürfte.
Die natürlichen Zahlen in EBNF
Startsymbol: natZahl
Grundmenge: keine
Regel:
natZahl = ZifferOhneNull {Ziffer} .
ZifferOhneNull = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
Ziffer = "0" | ZifferOhneNull .
Erläuterung zum Beispiel
Die fett markierten Wörter sind normalerweise immer anzugeben (es gibt wohl verschiedene Ausführungen / Dialekte der EBNF die sich in solchen Kleinigkeiten unterscheiden).
Alle Terminalsymbole sind in Anführungszeichen gesetzt. Das logische Oder ( | ) stellt eine Auswahlmöglichkeit zwischen einem der Symbole dar. Die geschweiften Klammern { } stellen eine freiwillige Wiederholung dar. Für unser Beispiel heißt das, dass man hinter eine Ziffer, außer der Null ( Menge: ZifferOhneNull ), optional beliebig viele Ziffern aus der Menge Ziffer darstellen kann oder nicht.
Die Unterscheidung mit ZifferOhneNull muss sein, da laut Definition die natürlichen Zahlen mit der Ziffer 1 beginnen, nich mit der 0.
Ein Unterschied zum Beispiel weiter unten ist auch das Endzeichen jeder Regel zu nennen. Hier wurde der Punkt benutzt, weiter unten wird das Semikolon als Endzeichen benutzt.
Eine tabellarische Zeichenerklärung findet sich am Ende des Artikels.
Unterschied BNF und EBNF mit Beispiel
Eine Zahl ist eine Ziffernfolge mit optionalem Minuszeichen als Vorzeichen. In BNF muss man mehrere Alternativen und eine Rekursion für die Ziffernwiederholung verwenden:
BNF
<Zahl> ::= <Positive Zahl> | - <Positive Zahl> <Positive Zahl> ::= <Ziffer> | <Ziffer> <Positive Zahl>
Lies: Eine Zahl ist entweder eine positive Zahl oder ein Minuszeichen gefolgt von einer positiven Zahl. Eine positive Zahl ist entweder eine Ziffer oder eine Ziffer gefolgt von einer positiven Zahl.
In EBNF kann man dies in einer einzigen Regel ohne Rekursion darstellen:
EBNF
Zahl = [ '-' ] Ziffer { Ziffer } ;
Lies: Eine Zahl ist ein optionales Minuszeichen, gefolgt von einer Ziffer, gefolgt von keiner oder beliebig vielen weiteren Ziffern.
Das Minuszeichen kann weggelassen werden. Die Wiederholung kann auch keinmal auftreten (optionale Wiederholung). Die EBNF benötigt hier nur eine einzige Regel ohne Alternative, während die BNF zwei Regeln mit vier Alternativen benötigt, inklusive einer Rekursion (<Positive Zahl> enthält sich selbst in der eigenen Definition).
Andere Ergänzungen und Modifikationen
Zusätzlich beseitigt die EBNF einige Schwachstellen der BNF:
- Die BNF verwendet selbst die Symbole (<, >, |, ::=). Wenn diese in der definierten Sprache auftauchen, kann die BNF nicht ohne Modifikation oder Erklärung verwendet werden.
- Eine BNF-Syntax kann eigentlich nur einzeilige Regeln enthalten.
Die EBNF löst diese Probleme:
- Terminalsymbole werden grundsätzlich in Anführungszeichen geschrieben ("..." oder '...'). Auf die spitzen Klammern ("<...>") bei Nichtterminalsymbolen kann dann verzichtet werden.
- Ein Endezeichen, normalerweise das Semikolon, kennzeichnet das Ende jeder Regel.
Darüberhinaus sind Erweiterungsmechanismen, Definition der Wiederholungszahl, Herausnehmen von Alternativen (zum Beispiel alle Zeichen ohne Anführungszeichen), Kommentare usw. vorgesehen.
Trotz aller Erweiterungen ist die EBNF nicht "mächtiger" als die BNF in Hinsicht der Sprachen, die sie definieren kann. Prinzipiell ließe sich jede in EBNF definierte Grammatik auch nach BNF übertragen, allerdings mit vermutlich wesentlich höherem Aufwand.
Die EBNF ist von der ISO standardisiert unter der Nummer ISO/IEC 14977:1996(E). Manchmal wird auch jede BNF, die mindestens um eckige Klammern für Optionen und geschweifte Klammern für optionale Wiederholung ergänzt wurde, als EBNF bezeichnet.
Beispiel
Eine ganz einfache Programmiersprache, die nur Zuweisungen erlaubt, kann in EBNF so definiert werden:
(* ein einfaches Beispiel in EBNF - Wikipedia *)
Programm = 'PROGRAM' Bezeichner
'BEGIN' { Zuweisung [";"] } 'END' "." ;
Bezeichner = Buchstabe { ( Buchstabe | Ziffer ) } ;
Zahl = [ "-" ] Ziffer { Ziffer } ;
String = '"' { AlleZeichen - '"'} '"' ;
Zuweisung = Bezeichner ":=" ( Zahl |
Bezeichner |
String ) ;
Buchstabe = "A" | "B" | "C" | "D" | "E" | "F" | "G"
| "H" | "I" | "J" | "K" | "L" | "M" | "N"
| "O" | "P" | "Q" | "R" | "S" | "T" | "U"
| "V" | "W" | "X" | "Y" | "Z" ;
Ziffer = "0" | "1" | "2" | "3" | "4" | "5" | "6"
| "7" | "8" | "9" ;
AlleZeichen = ? alle sichtbaren Zeichen ? ;
Hier wurden die Standardsymbole ("=" für Definitionen, ";" als Endezeichen usw.) verwendet. Bei Bedarf darf davon abgewichen werden.
Ein syntaktisch zulässiges Programm wäre dann
PROGRAM DEMO1 BEGIN A0:=3; B:=45; H:=-100023; C:=A; D123:=B34A; ESEL:=GIRAFFE; TEXTZEILE:="Hallo, Welt!" END.
Die Sprache kann leicht um Kontrollstrukturen, arithmetische Ausdrücke und Ein- beziehungsweise Ausgabeanweisungen ergänzt werden. Dann entstünde bereits eine brauchbare, kleine Programmiersprache.
Die folgenden Zeichen, die im Standard als normale Darstellung empfohlen werden, wurden hier verwendet:
| Verwendung | Zeichen |
|---|---|
| Definition | = |
| Endezeichen | ; |
| Logisches Oder | | |
| Option | [ ... ] |
| Optionale Wiederholung | { ... } |
| Gruppierung | ( ... ) |
| Anführungszeichen, 1. Variante | " ... " |
| Anführungszeichen, 2. Variante | ' ... ' |
| Kommentar | (* ... *) |
| Spezielle Sequenz | ? ... ? |
| Ausnahme | - |
Weiterführende Informationen
Siehe auch ...
- BNF Backus-Naur-Form
- Programmiersprachen Die EBNF wird genutzt um bspw. den Aufbau von Programmiersprachen darzustellen