imported>SchlurcherBot: Bot: http → https

2025-07-10T15:44:21Z

Bot: http → https

Neue Seite

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 (Programmiersprache)|Pascal]] eingeführt wurde. Sie ist eine formale Metasyntax ([[Metasprache]]), die benutzt wird, um [[kontextfreie Grammatik]]en darzustellen.

Die EBNF ist von der [[International Organization for Standardization|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 [[Computerprogramm]]s, besteht zunächst aus [[Terminalsymbol]]en, das heißt, aus sichtbaren Zeichen wie Buchstaben, Ziffern, Satzzeichen, Leerzeichen etc.

Die EBNF definiert [[Produktionsregel]]n, in denen Symbolfolgen jeweils einem Nichtterminalsymbol zugeordnet werden, etwa
<syntaxhighlight lang="ebnf">
ZifferAusserNull = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
Ziffer = "0" | ZifferAusserNull ;
</syntaxhighlight>

In dieser Produktionsregel wird das Nichtterminalsymbol Ziffer definiert, das stets auf der linken Seite steht. Der vertikale Strich stellt eine [[Kontravalenz|(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:
<syntaxhighlight lang="ebnf">
Zwoelf = "1", "2" ;
Zweihundertundeins = "2", "0", "1" ;
Dreihundertzwoelf = "3", Zwoelf ;
ZwoelfTausendzweihunderteins = Zwoelf, Zweihundertundeins ;
</syntaxhighlight>

Ausdrücke, die ausgelassen oder wiederholt werden dürfen, können mit geschweiften Klammern dargestellt { … } werden:
<syntaxhighlight lang="ebnf">
NatuerlicheZahl = ZifferAusserNull {, Ziffer } ;
</syntaxhighlight>

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:
<syntaxhighlight lang="ebnf">
GanzeZahl = "0" | [ "-" ], NatuerlicheZahl ;
</syntaxhighlight>

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.
<syntaxhighlight lang="ebnf">
LeerzeichenAlsTab = 4 * " " , "Yes" ;
</syntaxhighlight>

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 (Programmiersprache)|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 (Zahl)|Vorzeichen]]. In BNF muss man mehrere Alternativen und eine Rekursion für die Ziffernwiederholung verwenden:

'''BNF'''
<syntaxhighlight lang="bnf">
<Zahl> ::= <Positive Zahl> | - <Positive Zahl> | 0
<Positive Zahl> ::= <Ziffer ausser Null><Optionale Ziffernfolge>
<Optionale Ziffernfolge> ::= <Ziffer> <Optionale Ziffernfolge> | ε
</syntaxhighlight>

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'''
<syntaxhighlight lang="ebnf">
Zahl = ([ "-" ], ZifferAusserNull, { Ziffer }) | "0" ;
</syntaxhighlight>

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:
* [[Terminalsymbol]]e 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 [[Extensible Markup Language|XML]].<ref>{{cite web | url=http://www.w3c.org/TR/REC-xml#sec-notation | title=Notation | publisher=W3C ® | language=englisch | accessdate=2019-04-01}}</ref>

== Kontrollstrukturen ==
[[Datei:Ebnf-syntax-diagram.png|mini|982x982px|Ein [[Syntaxdiagramm]], das eine Erweiterte Backus-Naur-Form darstellt]]
Die Sprache kann leicht um [[Kontrollstruktur]]en, 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:

{| class="wikitable"
! 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.
! <nowiki>|</nowiki>
|-
| 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 [[Metasprache]]n, wie beispielsweise [[HTML]] können in der EBNF definiert werden.<ref name="tomasetti">Federico Tomassetti: [https://tomassetti.me/ebnf/ EBNF: How to Describe the Grammar of a Language] vom 1. August 2017, abgerufen am 6. August 2019</ref>

Im Prinzip können alle [[Formale Sprache|formalen Sprachen]] in der EBNF ausgedrückt werden. Insbesondere in der Informatik bei der Definition von Programmiersprachen, [[Regulärer Ausdruck|regulären Ausdrücken]] oder [[Parser]]n (siehe zum Beispiel [[Spirit (Parser)|Spirit]]) wird EBNF häufig eingesetzt.<ref>[[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</ref>

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.<ref name="tomasetti"></ref>

== Beispiele ==

=== Einfache Programmiersprache ===
Eine ganz einfache Programmiersprache, die nur Zuweisungen erlaubt, kann in EBNF so definiert werden:

<syntaxhighlight lang="ebnf">
(* 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 ? ;
</syntaxhighlight>

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
<syntaxhighlight lang="pascal">
PROGRAM DEMO1
BEGIN
A0:=3;
B:=45;
H:=-100023;
C:=A;
D123:=B34A;
ESEL:=GIRAFFE;
TEXTZEILE:="Hallo, Welt!";
END.
</syntaxhighlight>

=== Binärbäume ===
Die Darstellung von [[Binärbaum|Binärbaumen]] in [[Binärbaum#Tiefensuche|pre-order]] als [[Zeichenkette]] kann in EBNF so definiert werden:<syntaxhighlight lang="ebnf">
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" ;
</syntaxhighlight>[[Datei:Sorted binary tree.svg|mini|Ein [[Binärbaum]]]]Der [[Binärbaum]] rechts hat dann die [[Binärbaum#Tiefensuche|pre-order]] Darstellung F(B(A)(D(C)(E)))(G()(I(H)())).

Die [[Produktionsregel|Produktionsregeln]] dieser EBNF können auch wie folgt dargestellt werden:
:<math>\begin{align}
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{align}
</math>

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

== Siehe auch ==
* [[Backus-Naur-Form]]
* [[Angereicherte Backus-Naur-Form]]
* [[Kontextfreie Grammatik]]
* [[Kellerautomat]]
* [[Syntaxdiagramm]]
* vereinfachte Programmiersprache [[PL/0]] als EBNF-Muster

== Weblinks ==
* SELFHTML: [https://wiki.selfhtml.org/wiki/Backus_Naur_Form ''Backus Naur Form'']
* GeeksforGeeks: [https://www.geeksforgeeks.org/bnf-notation-in-compiler-design/ ''BNF Notation in Compiler Design'']
* Christian-Albrechts-Universität zu Kiel: [https://www.informatik.uni-kiel.de/~mh/lehre/pps20/vorlesung/kap21.pdf ''EBNF (Erweiterte Backus-Naur-Form)'']
* [https://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf 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)
* [https://standards.iso.org/ittf/PubliclyAvailableStandards/s026153_ISO_IEC_14977_1996(E).zip ''ISO/IEC 14977: 1996(E) – ISO-Standard zu EBNF (1st Edition)''] (ZIP-komprimiertes PDF, 2,2 MB)
* [https://www.cs.man.ac.uk/~pjj/bnf/ebnf.html ''Varianten der BNF und EBNF im Überblick'']
* [https://karmin.ch/ebnf/index ''EBNF Parser & Renderer''] auf Basis PHP
* [https://github.com/Weltraumschaf/ebnf ''Parser & Renderer in PHP5'']
* {{Webarchiv|url=http://www-cgi.uni-regensburg.de/~brf09510/grammartypes.html|wayback=20101030132932|text=''Vergleich der BNF-Varianten'' (englisch)}}
* {{Webarchiv|url=http://homepages.uni-regensburg.de/~brf09510/syntax.html|wayback=20111201001222|text=''Erzeugen von Syntaxdiagrammen aus EBNF''}}

== Einzelnachweise ==
<references/>

[[Kategorie:Compilerbau]]
[[Kategorie:Theorie formaler Sprachen]]

Erweiterte Backus-Naur-Form - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https