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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0c/Ebnf-syntax-diagram.png/110px-Ebnf-syntax-diagram.png)
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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]Einfache Programmiersprache
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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" ;
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/67/Sorted_binary_tree.svg/220px-Sorted_binary_tree.svg.png)
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:
Die Menge der Terminalsymbole ist , die Menge der Nichtterminalsymbole ist und das Startsymbol ist .
Siehe auch
[Bearbeiten | Quelltext bearbeiten]- Backus-Naur-Form
- Angereicherte Backus-Naur-Form
- Kontextfreie Grammatik
- Kellerautomat
- Syntaxdiagramm
- vereinfachte Programmiersprache PL/0 als EBNF-Muster
Weblinks
[Bearbeiten | Quelltext bearbeiten]- 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) ( vom 30. Oktober 2010 im Internet Archive)
- Erzeugen von Syntaxdiagrammen aus EBNF ( vom 1. Dezember 2011 im Internet Archive)
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ 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