www.wikidata.de-de.nina.az

Erweiterte Backus Naur Form Die kurz EBNF ist eine Erweiterung der Backus Naur Form BNF die ursprünglich von Niklaus Wir

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

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

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

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

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

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.

Anwendungen Bearbeiten

Viele Metasprachen, wie beispielsweise HTML können in der EBNF definiert werden.

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.

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.

Beispiel Programmiersprache 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.

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. Ist es 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 -

Siehe auch Bearbeiten

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Notation. W3C ®, abgerufen am 1. April 2019 (englisch).
  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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Erweiterte Backus Naur Form kurz EBNF ist eine Erweiterung der Backus Naur Form BNF die ursprunglich von Niklaus Wirth zur Darstellung der Syntax der Programmiersprache Pascal eingefuhrt 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 Inhaltsverzeichnis 1 Grundlagen 2 Motivation zur Erweiterung der BNF 2 1 Zahldefinition in BNF 2 2 Zahldefinition in EBNF 3 Andere Erganzungen und Modifikationen 4 Anwendungen 5 Beispiel Programmiersprache 6 Siehe auch 7 Weblinks 8 EinzelnachweiseGrundlagen BearbeitenEin Text etwa Quelltext eines Computerprogramms besteht zunachst aus Terminalsymbolen das heisst 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 Anfuhrungszeichen eingeschlossen und mit einem Semikolon als Endezeichen abgeschlossen Eine Ziffer ist also eine 0 oder eine ZifferAusserNull die wiederum eine naturliche 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 Ausdrucke die ausgelassen oder wiederholt werden durfen konnen 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 naturliche Zahl der optional ein Minuszeichen vorangestellt werden kann Hier passen also alle ganzen Zahlen wie 0 3 1234 etc Ausserdem ist die Moglichkeit 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 BearbeitenDie BNF benotigt teilweise umstandliche Konstrukte um optionale Elemente also Elemente die ausgelassen werden durfen sowie sich wiederholende Elemente darzustellen da sie anders als die EBNF nicht fur Optionen oder fur optionale Wiederholungen kennt sondern diese Falle durch entsprechende Alternativen mittels Fallen Rekursion oder auch leerem Inhalt lost In der Spezifikation von PL 1 wurden bereits eckige Klammern fur Optionen verwendet Niklaus Wirth hat in der Definition der Sprache Pascal zusatzlich geschweifte Klammern fur Wiederholungen in die BNF eingefuhrt und nannte dies extended BNF erweiterte BNF Alle Formulierungen in einer EBNF Syntax lassen sich auch in BNF ausdrucken Die EBNF wurde von Wirth aus Grunden der besseren Lesbarkeit und kompakteren Schreibweise geschaffen Zahldefinition in BNF Bearbeiten Eine Zahl ist eine Ziffernfolge mit optionalem Minuszeichen als Vorzeichen In BNF muss man mehrere Alternativen und eine Rekursion fur die Ziffernwiederholung verwenden BNF lt Zahl gt lt Positive Zahl gt lt Positive Zahl gt 0 lt Positive Zahl gt lt Ziffer ausser Null gt lt Optionale Ziffernfolge gt lt Optionale Ziffernfolge gt lt Ziffer gt lt Optionale Ziffernfolge gt 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 ausser Null gefolgt von einer optionalen Ziffernfolge Eine optionale Ziffernfolge ist eine Ziffer gefolgt von einer optionalen Ziffernfolge oder leer Zahldefinition in EBNF 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 ausser 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 benotigt hier nur eine einzige Regel ohne Alternative wahrend die BNF drei Regeln mit vier Alternativen benotigt inklusive einer Rekursion lt Optionale Ziffernfolge gt enthalt sich selbst in der eigenen Definition Die EBNF kennzeichnet Terminalsymbole durch Anfuhrungszeichen und verwendet ein Endezeichen Nichtterminalsymbole werden nicht in spitze Klammern eingeschlossen Durch die Anfuhrungszeichen sind Verwechslungen ausgeschlossen Andere Erganzungen und Modifikationen BearbeitenDie EBNF beseitigt einige Schwachstellen der BNF Die BNF verwendet selbst die Symbole lt gt Wenn diese in der definierten Sprache auftauchen kann die BNF nicht ohne Modifikation oder Erklarung verwendet werden Eine BNF Syntax kann eigentlich nur einzeilige Regeln enthalten Die EBNF lost diese Probleme Terminalsymbole werden grundsatzlich in Anfuhrungszeichen geschrieben oder Auf die spitzen Klammern lt gt bei Nichtterminalsymbolen kann dann verzichtet werden Ein Endezeichen normalerweise das Semikolon bei manchen Autoren ein Punkt kennzeichnet das Ende jeder Regel Daruber hinaus sind Erweiterungsmechanismen Definition der Wiederholungszahl Herausnehmen von Alternativen zum Beispiel alle Zeichen ohne Anfuhrungszeichen Kommentare usw vorgesehen Trotz aller Erweiterungen ist die EBNF nicht machtiger als die BNF in Hinsicht der Sprachen die sie definieren kann Prinzipiell lasst sich jede in EBNF definierte Grammatik auch durch Regeln in der BNF darstellen was jedoch haufig in einer wesentlich umfangreicheren Beschreibung resultiert Unter Umstanden wird auch jede erweiterte BNF als EBNF bezeichnet So nutzt das W3C eine EBNF zur Spezifikation von XML 1 Anwendungen BearbeitenViele Metasprachen wie beispielsweise HTML konnen in der EBNF definiert werden 2 Im Prinzip konnen alle formalen Sprachen in der EBNF ausgedruckt werden Insbesondere in der Informatik bei der Definition von Programmiersprachen regularen Ausdrucken oder Parsern siehe zum Beispiel Spirit wird EBNF haufig eingesetzt 3 EBNF ist nicht geeignet um die Semantik einer Sprache festzulegen So ist es zum Beispiel ohne weiteres moglich wesentliche eindeutige Sachverhalte gar nicht oder mehrfach zu definieren so dass es zu logischen Lucken oder Widerspruchen kommen kann Ferner kann die Zuweisungskompatibilitat von Ausdrucken durch EBNF nicht festgelegt werden 2 Beispiel Programmiersprache BearbeitenEine 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 fur Definitionen als Endezeichen usw verwendet Bei Bedarf darf davon abgewichen werden Ein syntaktisch zulassiges Programm ware 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 Ausdrucke und Ein bzw Ausgabeanweisungen erganzt werden Dann entstunde bereits eine brauchbare kleine Programmiersprache Die folgenden Zeichen die im ISO IEC Standard als normale Darstellung empfohlen werden wurden hier verwendet Verwendung Erklarung ZeichenDefinition Aufzahlung Endezeichen Alternative Trennt die moglichen Alternativen Ist es aber als exklusives Oder zu lesen da nur das eine oder das andere erlaubt ist Beides gleichzeitig geht nicht Option Umschliesst optionale Angaben Diese Inhalte konnen mussen aber nicht gesetzt werden Optionale Wiederholung Umschlossene Elemente durfen beliebig oft wiederholt werden Die Elemente durfen aber auch ausgelassen werden Gruppierung Fasst umschlossene Elemente als eine Einheit zusammen Anfuhrungszeichen 1 Variante Anfuhrungszeichen 2 Variante Kommentar Spezielle Sequenz Ausnahme Siehe auch BearbeitenBackus Naur Form Angereicherte Backus Naur Form Syntaxdiagramm vereinfachte Programmiersprache PL 0 als EBNF MusterWeblinks BearbeitenSELFHTML Backus Naur Form GeeksforGeeks BNF Notation in Compiler Design Christian Albrechts Universitat 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 enthalt 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 konnen bis auf eben in den Kommentaren die Bindestriche gar nicht verwendet werden da diese das Except Symbol reprasentieren 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 Uberblick EBNF Parser amp Renderer auf Basis PHP Parser amp 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 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 Abgerufen von https de wikipedia org w index php title Erweiterte Backus Naur Form amp oldid 239651782