Backus-Naur-Form

Einführung

Die Backus-Naur-Form oder Backus-Normalform (kurz BNF) ist eine kompakte formale Metasprache zur Darstellung kontextfreier Grammatiken. Eine Sprache besteht zunächst aus – auf Bildschirm oder Papier – sichtbaren Zeichen. Die sichtbaren Zeichen werden zu den Terminalsymbolen gerechnet.

Die BNF verwendet so genannte Ableitungsregeln (Produktionen), in denen Nichtterminalsymbole definiert werden. Dabei dient das Zeichen | (vertikaler Strich) als Alternative, die Zeichenfolge ::= wird zur Definition verwendet und die Nichtterminalsymbole (auch syntaktische Variablen genannt) werden mit spitzen Klammern <…> umschlossen.

Beispiel

Alternative

<Ziffer ausser Null> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Eine Ziffer außer Null ist also entweder eine 1, oder eine 2, oder eine 3 usw. Es lassen sich auch Terminalfolgen definieren, also eine Sequenz. Als Elemente dürfen Terminalsymbole und Nichtterminalsymbole auftreten.

Sequenz

<Zweiundvierzig> ::= 42

Eine Ziffer ist also eine 0 oder eine Ziffer außer Null. Eine zweistellige Zahl ist eine Ziffer außer Null gefolgt von einer Ziffer. Zweiundvierzig ist eine 4 gefolgt von einer 2.

Wiederholungen

Wiederholungen müssen in BNF über Rekursionen definiert werden. Eine Ableitungsregel kann dazu auf der rechten Seite das Symbol auf der linken Seite enthalten, etwa:

Lies: Eine Ziffernfolge ist eine Ziffer oder eine Ziffer gefolgt von einer Ziffernfolge.

Eine Ziffernfolge passt also zu den Symbolfolgen 0, 1, 2, 10, 9870, 8970635 usw., jedoch auch zu 00, 000, … Eine positive Zahl darf nicht mit 0 beginnen. Dies leistet die folgende Regel:

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.

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.