Erweiterte Backus-Naur Form

Die Erweiterte Backus-Naur-Form, kurz EBNF, ist eine Erweiterung der Backus-Naur-Form (BNF), die ursprünglich von Niklaus Wirth zur Darstellung der Syntax der Programmiersprache Pascal eingeführt wurde. Sie ist eine formale Metasyntax (Metasprache), die benutzt wird, um kontextfreie Grammatiken darzustellen.

Die EBNF ist von der ISO als ISO/IEC 14977:1996(E) standardisiert. Gelegentlich werden auch andere erweiterte Varianten der BNF als EBNF bezeichnet.

Grundlagen

Ein Text, etwa Quelltext eines Computerprogramms, besteht zunächst aus Terminalsymbolen, das heißt, aus sichtbaren Zeichen − Buchstaben, Ziffern, Satzzeichen, Leerzeichen, etc.

Die EBNF definiert Produktionsregeln, in denen Symbolfolgen jeweils einem Nichtterminalsymbol zugeordnet werden, etwa

ZifferAußerNull   = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
Ziffer            = "0" | ZifferAußerNull ;

In dieser Produktionsregel wird das Nichtterminalsymbol Ziffer definiert, das stets auf der linken Seite steht. Der vertikale Strich stellt eine Alternative dar, die Terminalsymbole werden in Anführungszeichen eingeschlossen und mit einem Semikolon als Endezeichen abgeschlossen. Eine Ziffer ist also eine 0 oder eine ZifferAußerNull, die wiederum 1 oder 2 oder 3 usw. bis 9 sein kann.

Eine Produktionsregel kann auch eine Folge von Terminal- oder Nichtterminalsymbolen enthalten, etwa:

Zwoelf                       = "1" "2" ;
Zweihundertundeins           = "2" "0" "1" ;
Dreihundertzwölf             = "3" Zwoelf ;
ZwoelfTausendzweihunderteins = Zwoelf Zweihundertundeins ;

Ausdrücke, die ausgelassen oder wiederholt werden dürfen, können mit geschweiften Klammern dargestellt { ... } werden:

NatuerlicheZahl = ZifferAußerNull { Ziffer } ;

Hier passen die Texte 1, 2, ...,10,...,12345,... . Zu beachten ist, dass alles, was innerhalb der geschweiften Klammern steht, beliebig oft, jedoch auch keinmal vorkommen kann.

Eine Option kann durch eckige Klammen [ ... ] dargestellt werden:

GanzeZahl = "0" | [ "-" ] NatuerlicheZahl ;

Eine ganze Zahl ist also die Null (0) oder eine natürliche Zahl, der optional ein Minuszeichen vorangestellt werden kann. Hier passen also alle ganzen Zahlen wie 0, -3, 1234 etc.

Erweiterungen nach ISO

Nach dem Standard ISO 14977 ist es möglich, Nichtterminalsymbole auch aus mehr als einem Wort bestehen zu lassen, indem die Einzelteile durch ein Komma verbunden werden.

Ganze Zahl = "0" | [ "-" ] , Natuerliche Zahl ;

Außerdem ist die Möglichkeit vorgesehen, eine definierbare Anzahl an Wiederholungen zu erlauben.

LeerzeichenAlsTab = 4 * " " , "Yes" ;

Hier wird vor der Zeichenfolge "Yes" viermal das " "-Zeichen erwartet.

Motivation zur Erweiterung der BNF

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 verwendet. 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).

Alle Formulierungen in einer EBNF-Syntax lassen sich auch in BNF ausdrücken. Die EBNF wurde von Wirth aus Gründen der besseren Lesbarkeit und kompakteren Schreibweise geschaffen.

Zahldefinition in BNF

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> | 0
<Positive Zahl> ::= <Ziffer außer Null><Optionale Ziffernfolge>
<Optionale Ziffernfolge> ::= <Ziffer> <Optionale Ziffernfolge> |

Lies: Eine Zahl ist entweder eine positive Zahl oder ein Minuszeichen gefolgt von einer positiven Zahl oder das Zeichen Null. Eine positive Zahl ist eine Ziffer außer Null gefolgt von einer optionalen Ziffernfolge. Eine optionale Ziffernfolge ist eine Ziffer gefolgt von einer optionalen Ziffernfolge oder leer.

Zahldefinition in EBNF

In EBNF kann man dies in einer einzigen Regel ohne Rekursion darstellen:

EBNF

Zahl = [ '-' ] ZifferAußerNull { Ziffer }  | '0'  ;

Lies: Eine Zahl besteht aus einem optionalen Minuszeichen, gefolgt von einer Ziffer außer Null, gefolgt von beliebig vielen weiteren Ziffern (auch keiner weiteren Ziffer). Oder: Eine Zahl besteht aus dem Zeichen Null.

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 (<Optionale Ziffernfolge> enthält sich selbst in der eigenen Definition).

Die EBNF kennzeichnet Terminalsymbole durch Anführungszeichen und verwendet ein Endezeichen. Nichtterminalsymbole werden nicht in spitze Klammern eingeschlossen. Durch die Anführungszeichen sind Verwechslungen ausgeschlossen.

Andere Ergänzungen und Modifikationen

Die EBNF beseitigt 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über hinaus 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 lässt sich jede in EBNF definierte Grammatik auch durch Regeln in der BNF darstellen, was jedoch häufig in einer wesentlich umfangreicheren Beschreibung resultiert.

Die EBNF ist von der ISO standardisiert unter der Nummer ISO/IEC 14977:1996(E).

Unter Umständen wird auch jede erweiterte BNF als EBNF bezeichnet. So nutzt das W3C eine EBNF zur Spezikation von XML.

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- bzw. 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	;
Alternative	|
Option	[ ... ]
Optionale Wiederholung	{ ... }
Gruppierung	( ... )
Anführungszeichen, 1. Variante	" ... "
Anführungszeichen, 2. Variante	' ... '
Kommentar	(* ... *)
Spezielle Sequenz	? ... ?
Ausnahme	-

Siehe auch

• Backus-Naur-Form
• vereinfachte Programmiersprache PL/0 als EBNF-Muster

Weblinks

• ISO/IEC 14977 : 1996(E) − ISO Standard zu EBNF (final draft version SC22/N2249) Anmerkung: Dieses Dokument ist ein Entwurf, der noch Fehler enthält. „Meta-Identifiers“ etwa werden im Text mit Bindestrichen verbunden (siehe Abschnitt 4: „written as one or more words joined together by hyphens“), in den Beispielen hingegen werden bis auf einige Kommentare diese Meta-Identifiers mit Leerzeichen geschrieben. Anmerkung 2: In den Beispielen können (bis auf eben in den Kommentaren) die Bindestriche gar nicht verwendet werden, da diese das „Except-Symbol“ repräsentieren und man dadurch die im Dokument spezifizierten EBNF-Syntaxregeln verletzte...
• ISO/IEC 14977 : 1996(E) − ISO Standard zu EBNF (1st Edition) (ZIP-komprimiertes PDF, 2,2 MB)
• Varianten der BNF und EBNF im Überblick
• Vergleich der BNF-Varianten (englisch)
• Syntaxdiagramme von EBNF
• Erzeugen von Syntaxdiagrammen aus EBNF