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. Die Beispiele in diesem Artikel richten sich nach dem ISO-Standard. 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 wie Buchstaben, Ziffern, Satzzeichen, Leerzeichen etc.

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

 ZifferAusserNull   = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
 Ziffer             = "0" | ZifferAusserNull ;

In dieser Produktionsregel wird das Nichtterminalsymbol Ziffer definiert, das stets auf der linken Seite steht. Der vertikale Strich stellt eine (exklusive) Alternative dar, die Terminalsymbole werden in Anführungszeichen eingeschlossen und mit einem Semikolon als Endezeichen abgeschlossen. Eine Ziffer ist also eine 0 oder eine ZifferAusserNull, die wiederum eine natürliche Zahl zwischen 1 und 9 sein kann.

Eine Produktionsregel kann auch eine Folge von Terminal- oder Nichtterminalsymbolen enthalten, wobei die Bestandteile durch Kommata verbunden werden, etwa:

 Zwoelf                       = "1", "2" ;
 Zweihundertundeins           = "2", "0", "1" ;
 Dreihundertzwoelf            = "3", Zwoelf ;
 ZwoelfTausendzweihunderteins = Zwoelf, Zweihundertundeins ;

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

 NatuerlicheZahl = ZifferAusserNull, { 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 Klammern [ … ] 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.

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, da sie – anders als die EBNF – nicht "[…]" für Optionen oder "{…}" für optionale Wiederholungen kennt, sondern diese Fälle durch entsprechende Alternativen (mittels '|'-Fällen), Rekursion oder auch 'leerem Inhalt' löst.

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 ausser 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 = ([ "-" ], ZifferAusserNull, { 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 drei 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, bei manchen Autoren ein Punkt, 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.

Unter Umständen wird auch jede erweiterte BNF als EBNF bezeichnet. So nutzt das W3C eine EBNF zur Spezifikation von XML.^[1]

Kontrollstrukturen

Ein Syntaxdiagramm, das eine Erweiterte Backus-Naur-Form darstellt

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 ISO/IEC Standard als normale Darstellung empfohlen werden, wurden hier verwendet:

Verwendung	Erklärung	Zeichen
Definition		=
Aufzählung		,
Endezeichen		;
Alternative	Trennt die möglichen Alternativen. Es ist aber als exklusives Oder zu lesen, da nur das eine oder das andere erlaubt ist. Beides gleichzeitig geht nicht.	\|
Option	Umschließt optionale Angaben. Diese Inhalte können, müssen aber nicht gesetzt werden.	[ … ]
Optionale Wiederholung	Umschlossene Elemente dürfen beliebig oft wiederholt werden. Die Elemente dürfen aber auch ausgelassen werden.	{ … }
Gruppierung	Fasst umschlossene Elemente als eine Einheit zusammen.	( … )
Anführungszeichen, 1. Variante		" … "
Anführungszeichen, 2. Variante		' … '
Kommentar		(* … *)
Spezielle Sequenz		? … ?
Ausnahme		-

Diese Kontrollstrukturen können auch als Syntaxdiagramm dargestellt werden. Die Abbildung rechts zeigt einige Beispiele.

Anwendungen

Viele Metasprachen, wie beispielsweise HTML können in der EBNF definiert werden.^[2]

Im Prinzip können alle formalen Sprachen in der EBNF ausgedrückt werden. Insbesondere in der Informatik bei der Definition von Programmiersprachen, regulären Ausdrücken oder Parsern (siehe zum Beispiel Spirit) wird EBNF häufig eingesetzt.^[3]

EBNF ist nicht geeignet, um die Semantik einer Sprache festzulegen. So ist es zum Beispiel ohne weiteres möglich, wesentliche eindeutige Sachverhalte gar nicht oder mehrfach zu definieren, so dass es zu logischen Lücken oder Widersprüchen kommen kann. Ferner kann die Zuweisungskompatibilität von Ausdrücken durch EBNF nicht festgelegt werden.^[2]

Beispiele

Einfache Programmiersprache

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', "." ;
 Zuweisung = Bezeichner, ":=", ( Zahl |
                               Bezeichner |
                               String ) ;
 Bezeichner = Buchstabe, { ( Buchstabe | Ziffer ) } ;
 Zahl = [ '-' ], Ziffer, { Ziffer } ;
 String = '"', { AlleZeichen - '"' }, '"' ;
 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.

Binärbäume

Die Darstellung von Binärbaumen in pre-order als Zeichenkette kann in EBNF so definiert werden:

BinaryTree = Identifier, "(", BinaryTree, ")(", BinaryTree, ")" | [Identifier] ;
Identifier = Letter, { ( Letter | Digit ) } ;
Letter = "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" ;
Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Ein Binärbaum

Der Binärbaum rechts hat dann die pre-order Darstellung F(B(A)(D(C)(E)))(G()(I(H)())).

Die Produktionsregeln dieser EBNF können auch wie folgt dargestellt werden:

{\begin{aligned}S&\rightarrow I(S)(S)\\S&\rightarrow I\\S&\rightarrow \varepsilon \\I&\rightarrow LE\\E&\rightarrow LE\\E&\rightarrow DE\\E&\rightarrow \varepsilon \\L&\rightarrow \mathrm {A} \\L&\rightarrow \mathrm {B} \\&\cdots \\L&\rightarrow \mathrm {Z} \\D&\rightarrow 0\\D&\rightarrow 1\\&\cdots \\D&\rightarrow 9\\\end{aligned}}

Die Menge der Terminalsymbole ist $T=\{(,),\mathrm {A} ,\mathrm {B} ,\ldots ,\mathrm {Z} ,0,1,\ldots ,9\}$ , die Menge der Nichtterminalsymbole ist $N=\{S,I,E,L,D\}$ und das Startsymbol ist $S$ .

Siehe auch

Backus-Naur-Form
Angereicherte Backus-Naur-Form
Kontextfreie Grammatik
Kellerautomat
Syntaxdiagramm
vereinfachte Programmiersprache PL/0 als EBNF-Muster

Weblinks

SELFHTML: Backus Naur Form
GeeksforGeeks: BNF Notation in Compiler Design
Christian-Albrechts-Universität zu Kiel: EBNF (Erweiterte Backus-Naur-Form)
ISO/IEC 14977: 1996(E) – ISO-Standard zu EBNF (final draft version SC22/N2249) (PDF) 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…“ (PDF-Datei; 79 kB)
ISO/IEC 14977: 1996(E) – ISO-Standard zu EBNF (1st Edition) (ZIP-komprimiertes PDF, 2,2 MB)
Varianten der BNF und EBNF im Überblick
EBNF Parser & Renderer auf Basis PHP
Parser & Renderer in PHP5
Vergleich der BNF-Varianten (englisch) (Memento vom 30. Oktober 2010 im Internet Archive)
Erzeugen von Syntaxdiagrammen aus EBNF (Memento vom 1. Dezember 2011 im Internet Archive)

Einzelnachweise

↑ Notation. W3C ®, abgerufen am 1. April 2019 (englisch).
↑ ^a ^b Federico Tomassetti: EBNF: How to Describe the Grammar of a Language vom 1. August 2017, abgerufen am 6. August 2019
↑ Niklaus Wirth: What can we do about the unnecessary diversity of notation for syntactic definitions?, Communications of the ACM, Volume 20, Issue 11, November 1977, 822–823, ACM New York

[1] Notation. W3C ®, abgerufen am 1. April 2019 (englisch).

[tomasetti-2] Federico Tomassetti: EBNF: How to Describe the Grammar of a Language vom 1. August 2017, abgerufen am 6. August 2019

[3] Niklaus Wirth: What can we do about the unnecessary diversity of notation for syntactic definitions?, Communications of the ACM, Volume 20, Issue 11, November 1977, 822–823, ACM New York

[1]

[2]

[3]