Backus-Naur-Form

Begriff und Grundprinzip

Die Backus-Naur-Form oder Backus-Normalform (BNF) ist eine kompakte formale Metasprache zur Darstellung kontextfreier Grammatiken, also von Typ-2-Grammatiken der Chomsky-Hierarchie. Mit ihr lässt sich insbesondere die Syntax von Programmiersprachen exakt beschreiben. Sie wird außerdem zur Notation von Befehlssätzen und Kommunikationsprotokollen eingesetzt. Die erweiterte Backus-Naur-Form (EBNF) erleichtert unter anderem die Darstellung von Wiederholungen; in Internetnormen wird überwiegend die angereicherte Backus-Naur-Form (ABNF) verwendet.

Eine BNF unterscheidet Terminalsymbole und Nichtterminalsymbole. Terminalsymbole sind die sichtbaren Zeichen oder Zeichenfolgen, die am Ende tatsächlich entstehen. Nichtterminalsymbole, auch syntaktische Variablen genannt, bezeichnen dagegen Kategorien, die durch Ableitungsregeln oder Produktionen ersetzt werden. Nichtterminale stehen häufig in spitzen Klammern. Die Zeichenfolge ::= kennzeichnet eine Definition, der senkrechte Strich | trennt Alternativen.

Beispiel: <Ziffer ausser Null> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9. Damit ist eine Ziffer außer Null als eine der Ziffern 1 bis 9 definiert. Weitere Regeln können bereits definierte Nichtterminale verwenden: <Ziffer> ::= 0 | <Ziffer ausser Null> und <Zweistellige Zahl> ::= <Ziffer ausser Null> <Ziffer>. Eine zweistellige Zahl beginnt somit nicht mit 0.

Rekursion und kontextfreie Sprachen

Wiederholungen werden in der reinen BNF durch Rekursion beschrieben. Dabei verweist eine Regel auf das Nichtterminal, das sie selbst definiert. Die Regel <Ziffernfolge> ::= <Ziffer> | <Ziffernfolge> <Ziffer> erzeugt eine oder mehrere Ziffern. Sie passt beispielsweise zu 0, 10, 9870 und 8970635, aber auch zu 00 oder 000. Soll eine positive Zahl nicht mit 0 beginnen, kann man schreiben: <Positive Zahl> ::= <Ziffer ausser Null> | <Positive Zahl> <Ziffer>.

Die Produktionsregeln der BNF sind genau die Regeln, die in kontextfreien Grammatiken erlaubt sind. Beide Formalismen erzeugen deshalb dieselben Sprachen. BNF und Chomskys Grammatikformalismus entstanden Ende der 1950er Jahre vermutlich unabhängig voneinander. Saul Gorn wies 1961 auf ihren Zusammenhang hin; zunächst bezog er die BNF auf allgemeine Phrasenstrukturgrammatiken, später wurde die Beziehung genauer auf kontextfreie Grammatiken beschränkt.

Beschreibung von Programmiersprachen

Bei der Beschreibung von Programmiersprachen wie ALGOL, Pascal, C oder Java können Schlüsselwörter wie IF oder SWITCH unmittelbar als Terminalsymbole gelten. Alternativ lassen sie sich als Folgen einzelner Zeichen definieren. In einem Compiler erkennt die lexikalische Analyse solche Schlüsselwörter vor der eigentlichen Syntaxanalyse. Sie behandelt häufig auch Kommentare, Gleitkommazahlen, Bezeichner und Zeichenketten.

Ein vereinfachter Ausschnitt einer Pascal-Grammatik lautet: <Programm> ::= 'PROGRAM' <Bezeichner> 'BEGIN' <Satzfolge> 'END' . Ein Bezeichner wird durch <Bezeichner> ::= <Buchstabe> <Restbezeichner> beschrieben. Der Rest darf leer sein oder aus einem Buchstaben beziehungsweise einer Ziffer und einem weiteren Rest bestehen. Die leere Alternative ist notwendig, damit die Rekursion enden kann.

Bei der Syntaxanalyse wird geprüft, ob sich der Programmtext auf das Startsymbol <Programm> zurückführen lässt. PROGRAM Ggt BEGIN … END . und PROGRAM DiesisteinlangerBezeichnermit123 BEGIN … END . erfüllen die angegebenen Regeln. Ggt BEGIN … END . ist ungültig, weil PROGRAM fehlt. PROGRAM 123 BEGIN … END . ist ebenfalls ungültig, weil ein Bezeichner mit einem Buchstaben beginnen muss.

Beispiel einer Postanschrift

Eine BNF für eine deutsche Postanschrift kann mit <Post-Anschrift> ::= <Personenteil> <Strasse> <Stadt> beginnen. Der Personenteil enthält einen Titelteil und einen Namensteil sowie ein Zeilenende <EOL>. Der Titelteil besteht entweder aus einem Titel oder ist leer. Der Namensteil enthält einen Vornamensteil und einen Nachnamen oder rekursiv einen Vornamensteil und einen weiteren Namensteil. Dadurch sind mehrere Vornamen oder Initialen möglich. Ein Vornamensteil ist ein Vorname oder ein Initial mit anschließendem Punkt. Straße und Stadt werden jeweils mit ihren Bestandteilen und einem Zeilenende beschrieben.

Einzelheiten wie Postleitzahl und Hausnummer bleiben in diesem Beispiel undefiniert. Es wird angenommen, dass solche lexikalischen Details vom Zusammenhang abhängen oder an anderer Stelle festgelegt sind.

In erweiterten Schreibweisen können eckige Klammern eine Option kennzeichnen: <Personenteil> ::= [ <Titel> ] <Namensteil> <EOL>. Der Titel darf dann fehlen. Ebenso bedeutet <Zahl> ::= [ - ] <Positive Zahl>, dass das Minuszeichen optional ist. Dies ist gleichbedeutend mit <Zahl> ::= <Positive Zahl> | - <Positive Zahl>. Eckige Klammern gehören jedoch nicht zur reinen Form aus dem Algol 60 Report, sondern sind allgemein in der EBNF anerkannt.

Modifikationen, Selbstbeschreibung und Parser

In praktischen Varianten wird die BNF oft verändert, damit Metazeichen und Zeichen der beschriebenen Sprache eindeutig unterscheidbar sind. Häufig entfallen die spitzen Klammern; Terminalsymbole stehen in Anführungszeichen, Nichtterminale in Kleinbuchstaben und Schlüsselwörter in Großbuchstaben. Statt ::= wird = verwendet, und ein Punkt beendet jede Regel. So kann etwa ziffer = "0" | "1" | … | "9" . geschrieben werden.

Andere Varianten kennzeichnen eine Option mit ?, eine ein- oder mehrmalige Wiederholung mit + und eine null- oder mehrmalige Wiederholung mit . Klammern gruppieren Ausdrücke. Beispiele sind ziffernfolge ::= ziffer+ . und bezeichner ::= buchstabe ( buchstabe | ziffer ) . Die EBNF verwendet dagegen […] für Optionen und {…} für optionale Wiederholungen. Beispielsweise bedeutet Bezeichner = Buchstabe { Buchstabe | Ziffer } ;, dass nach dem ersten Buchstaben beliebig viele Buchstaben oder Ziffern folgen dürfen.

Eine modifizierte BNF kann auch ihre eigene Syntax definieren. Dabei lassen sich etwa Sätze als Nichtterminal, gefolgt von ::=, einer Elementliste und einem Punkt beschreiben. Großgeschriebene Folgen stehen in der dargestellten Variante für Schlüsselwörter, kleingeschriebene Folgen für Nichtterminale. Rekursion wird unter anderem für die gesamte Grammatik, Elementlisten, Nichtterminale und Schlüsselwörter verwendet.

Parsergeneratoren können eine BNF-ähnliche Grammatik einlesen und daraus automatisch einen Parser erzeugen. Das Unix-Programm yacc erstellt einen tabellengesteuerten Parser und gibt ein Unterprogramm in C aus. Seine Grammatiknotation erlaubt nur Produktionen mit : statt ::= sowie Alternativen mit |. Das hängt damit zusammen, dass yacc eine S-Attribution ermöglicht, während einem optionalen Teil kein sinnvoller semantischer Attributtyp zugeordnet werden kann. Die verwendete Grammatik muss die LALR-Eigenschaft erfüllen.