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.

Statt notiert man .

Sie wird oft für die Notation von Programmiersprachen, 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.

Es gibt viele Varianten der Backus-Naur-Form.

Die erweiterte Backus-Naur-Form (EBNF) ist eine gebräuchliche Variante. Eine andere Variante ist ABNF.

Beispiel

Hier eine BNF für eine deutsche Postanschrift:

{| border="0" | |::= | |- | |::= |[] |- | |::= | | Initial "." |- | |::= | | |- | |::= | |- | |::= | |- |}

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.
Der Vornamenteil besteht aus einem Vornamen oder einem Initial, auf den dann ein Punkt folgt.
Der Namensteil besteht aus einem Vornamen-Teil, einem Nachname und einem Zeilenende oder der Personenteil besteht aus einem Vornamen-Teil und wiederum aus einem Namensteil. (Diese Regel zeigt die Benutzung von Rekursion in BNFs und stellt den Fall dar das 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 "[ ]" wurden einige Jahre später in der Definition von IBMs PL/1 eingeführt, sind aber allgemein anerkannt.