Erweiterte Backus-Naur-Form

Begriff und Grundprinzip

Die Erweiterte Backus-Naur-Form (EBNF) ist eine formale Metasprache zur Darstellung kontextfreier Grammatiken. Sie beschreibt also die Syntax, nach der Texte wie der Quelltext eines Computerprogramms aufgebaut sein dürfen. Ursprünglich führte Niklaus Wirth sie für die Syntax der Programmiersprache Pascal ein. Die EBNF ist als ISO/IEC 14977:1996(E) standardisiert; die dargestellte Schreibweise folgt diesem ISO-Standard.

Ein Text besteht zunächst aus Terminalsymbolen: sichtbaren Zeichen wie Buchstaben, Ziffern, Satzzeichen und Leerzeichen. EBNF-Regeln ordnen Folgen solcher Zeichen oder weiterer Symbole einem Nichtterminalsymbol zu. Nichtterminale stehen links von = und bezeichnen zusammengesetzte Bestandteile der Grammatik. Terminalsymbole werden in Anführungszeichen geschrieben, beispielsweise "0".

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

Ziffer = "0" | ZifferAusserNull ;

Der senkrechte Strich | trennt exklusive Alternativen: Es ist jeweils nur eine der Möglichkeiten erlaubt. Das Semikolon ; beendet eine Regel. Folgen von Symbolen werden mit Kommas geschrieben, etwa Zwoelf = "1", "2" ;. Nichtterminale können dabei auf andere Regeln verweisen, zum Beispiel Dreihundertzwoelf = "3", Zwoelf ;.

Optionen, Wiederholungen und Gruppen

Die wichtigsten zusätzlichen EBNF-Mittel machen Grammatiken kürzer und leichter lesbar:

• [ … ] kennzeichnet eine Option. Der eingeschlossene Inhalt kann vorkommen, muss es aber nicht.
• { … } kennzeichnet eine optionale Wiederholung. Der Inhalt darf beliebig oft, aber auch keinmal vorkommen.
• ( … ) gruppiert mehrere Elemente zu einer Einheit.
• " … " oder ' … ' kennzeichnen Terminalsymbole.
• (* … *) ist ein Kommentar, ? … ? eine spezielle Sequenz und - eine Ausnahme.
• n * legt eine definierbare Wiederholungszahl fest.

So beschreibt NatuerlicheZahl = ZifferAusserNull {, Ziffer } ; natürliche Zahlen wie 1, 10 oder 12345: Nach einer Ziffer von 1 bis 9 können null oder mehr weitere Ziffern folgen. GanzeZahl = "0" | [ "-" ], NatuerlicheZahl ; erlaubt entweder 0 oder eine natürliche Zahl mit einem optionalen Minuszeichen, zum Beispiel -3 und 1234. In LeerzeichenAlsTab = 4 * " " , "Yes" ; werden vor "Yes" genau vier Leerzeichen erwartet.

Kontrollstrukturen lassen sich auch in Syntaxdiagrammen darstellen. Ein Regelende wird normalerweise durch ;, bei manchen Autoren durch einen Punkt markiert. Die Standardsymbole dürfen bei Bedarf abgewandelt werden.

Unterschied zur BNF

Die Backus-Naur-Form (BNF) hat keine direkte Schreibweise für Optionen [ … ] und optionale Wiederholungen { … }. In BNF müssen diese Fälle durch Alternativen mit |, Rekursion oder leeren Inhalt ausgedrückt werden. Wirth ergänzte nach der bereits in PL/1 verwendeten eckigen Klammer für Optionen die geschweiften Klammern für Wiederholungen.

Eine Zahl mit möglichem Minuszeichen benötigt in BNF mehrere Regeln und Rekursion:

<Zahl> ::= <Positive Zahl> | - <Positive Zahl> | 0

<Positive Zahl> ::= <Ziffer ausser Null><Optionale Ziffernfolge>

<Optionale Ziffernfolge> ::= <Ziffer> <Optionale Ziffernfolge> | ε

Dabei bedeutet ε leer. Dieselbe Struktur lässt sich in EBNF kompakter schreiben:

Zahl = ([ "-" ], ZifferAusserNull, { Ziffer }) | "0" ;

Das Minuszeichen ist optional, und die Wiederholung weiterer Ziffern kann leer sein. EBNF markiert Terminalsymbole durch Anführungszeichen, verwendet ein Endezeichen und braucht Nichtterminale nicht in spitze Klammern einzuschließen. Dadurch werden Verwechslungen vermieden. Auch die BNF-Symbole <, >, | und ::= können sonst problematisch sein, wenn sie selbst in der definierten Sprache vorkommen; außerdem sind BNF-Regeln eigentlich nur einzeilig.

Trotz dieser Ergänzungen ist EBNF nicht mächtiger als BNF: Jede EBNF-Grammatik lässt sich grundsätzlich in BNF-Regeln umformen, doch wird die Beschreibung häufig wesentlich umfangreicher. Mit „EBNF“ sind gelegentlich auch andere erweiterte BNF-Varianten gemeint; das W3C verwendet beispielsweise eine EBNF zur Spezifikation von XML.

Einsatz und Grenze

EBNF kann formale Sprachen ausdrücken und wird besonders in der Informatik verwendet: zur Definition von Programmiersprachen, regulären Ausdrücken und Parsern, zum Beispiel Spirit. Auch Metasprachen wie HTML können in EBNF definiert werden.

Sie legt jedoch nur die Syntax fest, nicht die Semantik, also nicht die Bedeutung einer Sprache. EBNF kann daher wesentliche eindeutige Sachverhalte gar nicht oder mehrfach definieren; daraus können logische Lücken oder Widersprüche entstehen. Auch die Zuweisungskompatibilität von Ausdrücken kann durch EBNF nicht festgelegt werden.

Beispiel einer kleinen Programmiersprache

Eine einfache Sprache für Zuweisungen beginnt mit PROGRAM, einem Bezeichner und BEGIN; danach folgen beliebig viele Zuweisungen mit Semikolon, und sie endet mit END und einem Punkt:

Programm = 'PROGRAM', Bezeichner, 'BEGIN', { Zuweisung, ";" }, 'END', "." ;

Eine Zuweisung besteht aus einem Bezeichner, := und entweder einer Zahl, einem weiteren Bezeichner oder einem String. Ein Bezeichner beginnt mit einem Buchstaben und darf danach beliebig viele Buchstaben oder Ziffern enthalten. Eine Zahl hat ein optionales '-' und mindestens eine Ziffer. Ein String beginnt und endet mit "; dazwischen dürfen beliebig viele sichtbare Zeichen außer " stehen.

Daher ist das gezeigte Programm syntaktisch zulässig: Es enthält unter anderem A0:=3;, H:=-100023;, C:=A; und TEXTZEILE:="Hallo, Welt!";. Die EBNF sagt dabei nur, dass diese Form zulässig ist, nicht ob etwa Bezeichner bereits definiert wurden oder Zuweisungen inhaltlich sinnvoll sind.

Beispiel Binärbaum

Ein Binärbaum in Pre-order-Darstellung kann als Zeichenkette beschrieben werden:

BinaryTree = Identifier, "(", BinaryTree, ")(", BinaryTree, ")" | [Identifier] ;

Ein nichtleerer Baum besteht aus einem Identifier und zwei in Klammerpaaren dargestellten Teilbäumen. Ein leerer Baum ist durch die optionale Form möglich. Ein Identifier beginnt mit einem Großbuchstaben von A bis Z und kann danach weitere Buchstaben oder Ziffern von 0 bis 9 enthalten.

Für den dargestellten Baum lautet die Pre-order-Darstellung F(B(A)(D(C)(E)))(G()(I(H)())). In der entsprechenden Grammatik sind die Terminalsymbole T = {(,), A, B, …, Z, 0, 1, …, 9}, die Nichtterminalsymbole N = {S,I,E,L,D} und das Startsymbol ist S.