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.
Table of contents |
2 BNF und Programmiersprachen 3 Beispiel 4 Modifikationen der BNF 5 Selbstdefinition einer (modifzierten) BNF 6 BNF und Parser-Generatoren |
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:
Sequenz:
Eine positive Zahl mit beliebig vielen Stellen kann man über eine Rekursion erzeugen:
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
Die Rückführung auf
PROGRAM DiesisteinlangerBezeichnertmit123 BEGIN ... END .
PROGRAM 123 BEGIN ... END. (123 ist kein Bezeichner)
Die Ausformulierung lautet:
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
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:
Eine modifizierte BNF kann sich selbst definieren:
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).
Siehe auch: Formales System (Informatik), Syntaxdiagramm
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.
eine Ziffer ist also entweder eine 0 oder eine 1 oder eine 2 usw. Es lassen sich auch Terminalfolgen definieren, also eine Sequenz. Als Elemente dürfen Terminalsymbole und Nichtterminalsymbole auftreten:
Eine zweistellige Zahl ist eine Ziffer gefolgt von einer Ziffer. Zweiundvierzig ist eine 4 gefolgt von einer 2.
Eine positive Zahl ist also eine Ziffer oder eine Ziffer gefolgt von einer positiven Zahl. Dazu passen also die Folgen 0, 1, 2, ...,10, 11, ... 99, 100,..., 100000, ..., 45691283284.BNF und Programmiersprachen
*) gekürzt PROGRAM Ggt BEGIN ... END.
nicht jedoch bei
Ggt BEGIN ... END. (beginnt nicht mit PROGRAM)
Beispiel
Hier eine BNF für eine deutsche Postanschrift:
(Definition von Straßenname, Hausnummer etc. fehlen)
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.
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
ziffer = "0" | "1" | "2" | "3" | ... | "9" .
positivezahl = ziffer | ziffer positivezahl .
zahl = [ "-" ] positivezahl .
programm = PROGRAM bezeichner
BEGIN satzfolge END "." .
Die Option wird manchmal nicht mit eckigen Klammern, sondern durch einen angefügtes Fragezeichen dargestellt. Die Wiederholung durch Rekursion ist oft umständlich: positivezahl = ziffer+ .
zahl = ( "-" )? positivezahl .
bezeichner = buchstabe ( buchstabe | ziffer )* .
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
modifiziertebnf = | satz modifiziertebnf .
satz = nichtterminal "=" elementliste "." .
elementliste = | element elementliste .
element = terminal | nichtterminal .
nichtterminal = kleinbuchstabe | kleinbuchstabe nichtterminal .
terminal = schluesselwort | anf sichtbareszeichen anf .
schluesselwort = grossbuchstabe | grossbuchstabe schluesselwort .
anf = """ .
grossbuchstabe = "A" | "B" | ... | "Z" .
kleinbuchstabe = "a" | "b" | ... | "z" .
sichtbareszeichen = "!" | "$" | "%" | ... (alle sichtbaren Zeichen) .
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.