Backus-Naur-Form
Die Backus-Naur-Form oder Backus-Normalform, kurz BNF, ist eine kompakte formale Metasprache zur Darstellung kontextfreier_Grammatiken (Typ-2-Grammatiken in der Chomsky-Hierarchie). 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_E._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 (Produktionen), in denen Nichtterminalsymbole (engl. nonterminals) definiert werden. Dabei dient das Zeichen /'> (vertikaler Strich) als Alternative, die Zeichenfolge ::= wird zur Definition verwendet und die Rekursionen definieren. 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:
BNF und Programmiersprachen
Um die Syntax von Programmiersprachen wie Java in BNF darzustellen, muss man noch die Schlüsselwörter (IF, SWITCH) zu den Terminalsymbolen rechnen. In einem Compiler werden sie in einer Vorphase, der lexikalischen_Analyse, erkannt und als besondere Zeichen weitergegeben. Kommentare werden von der lexikalischen Analyse erkannt (und oft entfernt), manchmal auch weitere Elemente wie Gleitkommazahlen, Bezeichner und Zeichenketten.
Damit lässt sich dann die gesamte Syntax z.B. eines PASCAL-Programms in BNF darstellen:
...
*) gekürzt
Eine Syntaxanalyse besteht aus der Rückführung eines Programmtexts auf das Nichtterminalsymbol
Ein Programm muss also mit dem Wort PROGRAM beginnen, auf das ein Bezeichner folgt. Bezeichner beginnen mit einem Buchstaben, gefolgt von beliebig vielen Buchstaben oder Ziffern.
Die Rückführung auf
PROGRAM Ggt BEGIN ... END.
PROGRAM DiesisteinlangerBezeichnermit123 BEGIN ... END .
nicht jedoch bei
Ggt BEGIN ... END. (beginnt nicht mit PROGRAM)
PROGRAM 123 BEGIN ... END. (123 ist kein Bezeichner, Bezeichner müssen mit einem Buchstaben beginnen)
Beispiel
Hier eine BNF für eine deutsche Postanschrift:
(Definition von Straßenname, Hausnummer etc. fehlen)
Die Ausformulierung lautet:
* Eine Postanschrift besteht aus einem Personenteil, gefolgt von einer Parser-Generatoren verwenden eine eigene Form der BNF als Eingabe und generieren hieraus einen Parser für die zugrundegelegte Programmiersprache.
Das dem Betriebssystem Unix beiligende Programm yacc ist so ein Programm. Es generiert einen tabellengesteuerten Parser aus einer BNF-Definition, wobei nur Produktionen (: statt ::=) und Alternativen (/'>) zulässig sind. Dies ist notwendig, da yacc eine Unterprogramm in der Programmiersprache C. Die zugrundegelegte Grammatik muss dabei die LALR-Eigenschaft erfüllen.
Literatur
* Donald E. Knuth: Backus Normal Form versus Backus Naur Form, Communications of the ACM 7 (December 1964), S. 735f. ? DOI 10.1145/355588.365140
Weblinks
• Revised Report on the Algorithmic Language Algol 60 (englisch)
• Vergleich der BNF-Varianten (englisch)
• Syntaxdiagramme von EBNF
• Erzeugen von Sytaxdiagrammen aus EBNF
Siehe auch
Erweiterte Backus-Naur-Form
Formale Sprache
Formale Grammatik
Syntaxdiagramm
Syntaxbaum
ta:???????-???? ????
