Backus-Naur-Form

Die Backus-Naur-Form oder Backus-Normalform, kurz BNF ist eine kompakte formale Metasyntax, die benutzt wird, um kontextfreie Grammatiken (= Typ-2-Grammatiken, vgl. Chomsky-Hierarchie) darzustellen. Hierzu zählt die Syntax gängiger höherer Programmiersprachen. Sie wird auch für die Notation von Befehlssätzen und Kommunikationsprotokollen verwendet.

Ursprünglich war sie nach John Backus benannt, später wurde sie (auf Anregung von Donald Knuth) auch nach Peter Naur benannt. Beide waren Informatikpioniere, die sich mit der Erstellung der Algol 60 Regeln und insbesondere mit der Kunst des Compilerbaus beschäftigten. Durch die Backus-Naur-Form im Algol 60-Report wurde es erstmals möglich, die Syntax einer Programmiersprache formal exakt, also ohne die Ungenauigkeiten natürlicher Sprachen, darzustellen.

Es gibt viele Varianten der Backus-Naur-Form. Die erweiterte Backus-Naur-Form (EBNF) ist eine gebräuchliche Variante, die unter anderem eine kompakte Notation von sich wiederholenden Elementen erlaubt.

Grundlagen

Ein Programm besteht zunächst aus sichtbaren, also auf der Tastatur vorhandenen, Zeichen. Daneben treten noch Leerzeichen und Zeilentrenner auf. Die sichtbaren Zeichen werden zu den Terminalsymbolen (engl. terminals) gerechnet.

BNF verwendet so genannte Ableitungsregeln, in denen Nicht-Terminalsymbole (engl. nonterminals) definiert werden. Dabei dient das Zeichen | (vertikaler Strich) als Alternative, die Zeichenfolge ::= wird zur Definition verwendet, zum Beispiel:

Alternative:

eine Ziffer ausser 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:

Eine Ziffer ist also entweder eine 0 oder eine 1 oder eine 2 usw. Eine zweistellige Zahl ist eine Ziffer ausser Null gefolgt von einer Ziffer. Zweiundvierzig ist eine 4 gefolgt von einer 2.

Eine positive Zahl mit beliebig vielen Stellen kann man über eine Rekursion erzeugen:

Eine positive Zahl ist also eine Ziffer oder eine Ziffer ausser Null gefolgt von einer positiven Zahl. Dazu passen also die Folgen 0, 1, 2,..._,10, 11,..._ 99, 100,..., 100000,..._, 45691283284.

BNF und Programmiersprachen

Um die Syntax von Programmiersprachen wie ALGOL, Pascal, Java in BNF darzustellen, muss man noch die Schlüsselwörter (IF, SWITCH) zu den Terminalsymbolen rechnen. In einem Compiler werden sie von einer Vorphase, der lexikalischen Analyse erkannt und als besondere Zeichen weitergegeben. Auch Kommentare werden von der lexikalischen Analyse erkannt, manchmal auch weitere Elemente wie Fliesskommazahlen, Bezeichner und Zeichenketten.

Damit lässt sich dann die gesamte Syntax eines Programms in BNF darstellen:

Eine Syntaxanalyse besteht aus der Rückführung eines Programmtexts auf das Nichterminalsymbol <Programm>.

Ein Programm muss also mit dem Wort PROGRAM beginnen, auf das ein Bezeichner folgt. Bezeichner beginnen mit einen Buchstaben, gefolgt von beliebig vielen Buchstaben oder Ziffern.

Die Rückführung auf <Programm> gelingt bei

  PROGRAM Ggt BEGIN ... END.

 

  PROGRAM DiesisteinlangerBezeichnertmit123 BEGIN ... END .

 

nicht jedoch bei

  Ggt BEGIN ... END. (beginnt nicht mit PROGRAM)

 

  PROGRAM 123 BEGIN ... END. (123 ist kein Bezeichner)

 

Beispiel

Hier eine BNF für eine deutsche Postanschrift:

(Definition von Straßenname, Hausnummer etc. fehlen)

Die Ausformulierung lautet:

• Ein Postanschrift besteht aus einem Personenteil, gefolgt von einer Straße, gefolgt von der Stadt.
• Der Personenteil besteht aus einem optionalen Titel und einem Namensteil, gefolgt von einem Zeilenende.
• Der Vornamenteil besteht aus einem Vornamen oder einem Initial, auf den dann ein Punkt folgt.
• Der Namensteil besteht aus einem Vorname-Teil, einem Nachname oder aus einem Vornamenteil und wiederum aus einem Namensteil. (Diese Regel zeigt die Benutzung von Rekursion in BNFs und stellt den Fall dar, dass eine Person mehrere Vornamen und/oder Initialen besitzt.)
• Eine Straße besteht aus einem Straßenname, gefolgt von einer Hausnummer, gefolgt von einem Zeilenende.
• Eine Stadt besteht aus einer Postleitzahl, gefolgt von einem Stadtname, gefolgt von einem Zeilenende.

Man beachte, dass einiges (wie die Postleitzahl oder Hausnummer) nicht weiter spezifiziert ist. Es wird angenommen, dass diese lexikalischen Details vom Kontext abhängen oder anderweitig spezifiziert sind.

Dieses Beispiel ist keine reine Form aus dem "ALGOL 60 report". Die eckigen Klammern "[ ]" stellen eine Option dar. Sie wurden einige Jahre später in der Definition von IBMs PL/1 eingeführt, sind aber allgemein anerkannt.

Option

Das Minuszeichen ist optional. Die Definition ist äquivalent zu

Eine Zahl ist eine positive Zahl, oder ein Minuszeichen, gefolgt von einer positiven Zahl.

Modifikationen der BNF

Die Alternative und die Sequenz sind zur Darstellung der BNF grundsätzlich geeignet. Allerdings lassen sich die Zeichen |, [, ] nicht von den BNF-Zeichen unterscheiden. Oft erkennt man auch Zeichen wie Punkt oder Minus nur schwer.

Die BNF wird daher in der Regel etwas modifiziert und ergänzt:

• Keine spitzen Klammern "< >" für Nichtterminale.
• Einbuchstabige Terminalsymbole werden in Anführungszeichen gesetzt ("0" | "1"..._)
• Nichtterminalsymbole in Kleinbuchstaben.
• Schlüsselwörter in Großbuchstaben.
• Nur = statt ::=.
• Ein Punkt am Ende einer Regel. Mehrzeilige Regeln sind möglich.

Die Option wird manchmal nicht mit eckigen Klammern, sondern durch einen angefügtes Fragezeichen dargestellt. Die Wiederholung durch Rekursion ist oft umständlich:

• Optionen werden durch ein angefügtes Fragezeichen dargestellt.
• Wiederholungen (ein- oder mehrfach) werden durch ein angefügtes Pluszeichen dargestellt.
• Optionale Wiederholungen (keinmal oder mehrfach) werden durch einen angefügten Stern dargestellt.
• Klammern dienen zur Gruppierung

Die erweiterte Backus-Naur-Form geht andere Wege. Sie verwendet eckige Klammern "[ ]" für die Option, jedoch geschweifte Klammenr "{ }" für die optionale Wiederholung.

Selbstdefinition einer (modifzierten) BNF

Eine modifizierte BNF kann sich selbst definieren:

Man erkennt, dass bei dieser Version Schlüsselwörter als Großbuchstaben dargestellt werden, Nichtterminale als Kleinbuchstaben. Wiederholungen müssen über Rekursionen definiert werden. Davon wird in der eigenen Definition auch Gebrauch gemacht (modifiziertebnf, elementliste, nichtterminal, schlüsselwort).

BNF und Parser-Generatoren

Manche Parser-Generatoren verwenden eine eigene Form der BNF als Eingabe und generieren hieraus einen Parser für die zugrundegelegte Programmiersprache.

Das in dem Betriebssystem Unix enthaltene Programm yacc (Yet Another Compiler Compiler) ist so ein Programm. Es generiert einen tabellengesteuerten Parser aus einer BNF-Definition. Als Ausgabe erhält man ein Unterprogramm in der Programmiersprache C. Die zugrundegelegte Sprache muss dabei bestimmten Einschränkungen genügen, da der Parser als endlicher Automat realisiert ist (sogenannte LR(1)-Grammatik).