Die Backus-Naur-Form oder Backus-Normalform, kurz BNF ist eine formale Metasyntax die benutzt wird um kontextfreie Gramatiken darzustellen.
Ursprünglich war sie nach 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. Sie wird oft für die Notation von Programmiersprachen, Befehlssätzen und Kommunikationsprotokollen verwendet.
Beispiel
Hier eine BNF für eine deutsche Postanschrift:
<Post-Anschrift> ::= <Personenteil> <Straße> <Stadt>
<Personenteil> ::= [<Titel>] <Namensteil>
<Vornamenteil> ::= <Vorname> | Initial "."
<Namensteil> ::= <Vornamen-Teil> <Nachname> <EOL> | <Vornamenteil> <Namensteil>
<Straße> ::= <Straßenname> <Hausnummer> <EOL>
<Stadt> ::= <Postleitzahl> <Stadtname> <EOL>
Die deutsche Übersetzung 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 einige Dinge (wie die Postleitzahl oder Hausnummer) nicht weiter spezifiziert sind. Es wird angenommen das diese lexikalischen Details vom Kontext abhängen oder anderweitig spezifiziert sind.
Es gibt viele Varianten von BNF, möglicherweise enthalten sie einige oder alle regexp Platzhalter, wie "*" oder "+". Die Erweiterte Backus-Naur Form (eng. Extended Backus-Naur Form) (EBNF) ist eine gebräuchliche. Tatsache ist, dass das Beispiel oben keine reine Form aus dem "ALGOL 60 report" ist. Die eckigen Klammern "[ ]" wurden einige Jahre später in der Definition von IBMs PL/I eingeführt, aber sie sind allgemein anerkannt. ABNF ist eine andere Erweiterung.