Quelltext der Seite Backus-Naur-Form

Die '''Backus-Naur-Form''' oder '''Backus-Normalform''' (kurz '''BNF''') ist eine kompakte formale [[Metasprache]] zur Darstellung [[Kontextfreie Grammatik|kontextfreier Grammatiken]] (Typ-2-Grammatiken in der [[Chomsky-Hierarchie]]). Hierzu zählt die [[Syntax]] gängiger [[Höhere Programmiersprache|höherer Programmiersprachen]]. Sie wird auch für die [[Notation]] von Befehlssätzen und [[Kommunikationsprotokoll]]en verwendet.

Ursprünglich war sie nach [[John W. Backus]] benannt, später wurde sie (auf Anregung von [[Donald E. Knuth]]) auch nach [[Peter Naur]] benannt. Beide waren Pioniere der [[Informatik]], die sich mit der Erstellung der [[Algol 60|Algol-60-Regeln]] und insbesondere mit der Kunst des [[Compilerbau]]s beschäftigten.<ref name="Backus-1959">{{Literatur |Autor=J. W. Backus |Hrsg=International Business Machines Corp. |Titel=The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM conference |Ort=New York |Datum=1959 |Kapitel=Syntax of IAL |Sprache=en}}</ref><ref>{{Literatur |Autor=John Backus |Hrsg=IBM research laboratory, San Jose CA |Titel=Programming in America in the 1950s – Some Personal Impressions |Datum= |Kapitel=9. Emil Post and Syntax Description |Sprache=en}}</ref> 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. Für Syntaxdefinitionen in Internetnormen wird überwiegend die [[angereicherte Backus-Naur-Form]] (ABNF) verwendet.

== Grundlagen ==
Ein Programm besteht zunächst aus –&nbsp;auf Bildschirm oder Papier&nbsp;– sichtbaren Zeichen. Daneben treten ggf. noch Leerzeichen sowie Zeilen- und Spaltentrennzeichen auf. Diese Zeichen zählen zu den ''[[Terminalsymbol]]en'' (englisch ''terminal symbols'' oder kurz ''terminals''), da sie von einer BNF final erzeugt werden.

Die BNF verwendet zur Erzeugung der finalen Folge von Terminalsymbolen sogenannte ''Ableitungsregeln'' ''([[Produktionsregel|Produktionen]]).'' Jede Ableitungsregel definiert ein [[Nichtterminalsymbol]] (englisch ''nonterminal symbol'' oder kurz ''nonterminal'') zusammen mit Folgen von Terminal- und Nichtterminalsymbolen, durch die es bei einer Erzeugung ersetzt wird. Oftmals dient dabei das Zeichen <code>|</code> (vertikaler Strich) als Alternative, die Zeichenfolge <code>::=</code> wird zur Kennzeichnung einer Definition verwendet und die Nichtterminalsymbole (auch syntaktische Variablen genannt) werden mit spitzen Klammern <code><</code>, <code>></code> umschlossen.

Beispiel einer Definition eines Nichtterminalsymbols mit Alternativen an Terminalsymbolen:
<syntaxhighlight lang="bnf">
<Ziffer ausser Null> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
</syntaxhighlight><!-- ASCII: kein ß -->

Eine Ziffer außer Null ist also entweder eine 1 oder eine 2 oder eine 3 usw. Es lassen sich auch Nichtterminalsymbole definieren, die bei einer Erzeugung durch eine Folge von Terminal- und Nichtterminalsymbolen ersetzt werden.

Zum Beispiel:
<syntaxhighlight lang="bnf">
<Ziffer>              ::= 0 | <Ziffer ausser Null>
<Zweistellige Zahl>   ::= <Ziffer ausser Null> <Ziffer>
<Zehn bis Neunzehn>   ::= 1 <Ziffer>
<Zweiundvierzig>      ::= 42
</syntaxhighlight><!-- ASCII: kein ß -->

Eine Ziffer ist also eine 0 oder eine Ziffer außer Null. Eine zweistellige Zahl ist eine Ziffer außer Null gefolgt von einer Ziffer. Zweiundvierzig ist eine 4 gefolgt von einer 2.

Wiederholungen müssen in der BNF über [[Rekursion]]en definiert werden. Eine Ableitungsregel kann dazu insbes. auf der rechten Seite das Symbol auf der linken Seite enthalten, etwa:
<syntaxhighlight lang="bnf">
<Ziffernfolge> ::= <Ziffer> | <Ziffernfolge> <Ziffer>
</syntaxhighlight>

''Bedeutung: Eine Ziffernfolge ist eine Ziffer oder eine Ziffernfolge gefolgt von einer Ziffer.''

Eine so definierte Ziffernfolge passt also zu den Terminalsymbolfolgen 0, 1, 2, 10, 9870, 8970635 usw., jedoch auch zu 00, 000,&nbsp;…

Soll eine positive Zahl nicht mit 0 beginnen, leistet dies etwa die folgende Regel:
<syntaxhighlight lang="bnf">
<Positive Zahl> ::= <Ziffer ausser Null> | <Positive Zahl> <Ziffer>
</syntaxhighlight><!-- ASCII: kein ß -->

''Bedeutung: Eine positive Zahl ist eine Ziffer außer Null oder eine positive Zahl gefolgt von einer Ziffer.''

== BNF und kontextfreie Sprachen ==
Die Produktionsregeln der BNF (nach Backus) sind genau die in kontextfreien Grammatiken (nach [[Noam Chomsky|Chomsky]]) erlaubten Regeln, es ist also klar, dass beide Formalismen dieselben Sprachen erzeugen. Sie entstanden auch zu derselben Zeit, nämlich am Ende der 1950er Jahre. Es gibt aber erst seit 1961 einen Hinweis auf den Zusammenhang, nämlich in einem Überblicksartikel über Metasprachen von Saul Gorn,<ref>Saul Gorn: ''Specification languages for mechanical languages and their processors – a baker’s dozen''. In: ''Communications of the ACM'' 4, 1961, S. 336–371.</ref> dort noch als Zusammenhang von BNF mit allgemeinen [[Phrasenstrukturgrammatik]]en dargestellt und erst später –&nbsp;genauer&nbsp;– auf kontextfreie Grammatiken beschränkt. Im Folgejahr gab es einen Briefwechsel zwischen Gorn und [[Donald E. Knuth|Knuth]] über dieses Thema in den Leserbriefen ''(letters to the editor)'' von ''[[Communications of the ACM|Comm.&nbsp;ACM]]''. Es ist plausibel anzunehmen, dass Chomsky und Backus ihre Formalismen unabhängig voneinander entwickelten und Gorn der erste war, der beide Ansätze kannte und so die Verbindung herstellen konnte.<ref>Anton Nijholt: ''Computers and Languages''. North-Holland, Amsterdam 1988, ISBN 0-444-70463-9, S.&nbsp;207–210.</ref>

== BNF und Programmiersprachen ==
Um die Syntax von Programmiersprachen wie [[ALGOL]], [[Pascal (Programmiersprache)|Pascal]], [[C (Programmiersprache)|C]] oder [[Java (Programmiersprache)|Java]] in der BNF darzustellen, können deren [[Schlüsselwort (Programmierung)|Schlüsselwörter]] (z.&nbsp;B. ''IF'', ''SWITCH'') zu den Terminalsymbolen gezählt werden.<ref>{{Literatur |Autor=J. W. Backus, F. L. Bauer, J. Green, C. Katz, J. McCarthy, P. Naur, A. J. Perlis, H. Rutishauser, K. Samelson, B. Vauquois, J. H. Wegstein, A. van Wijngaarden, M. Woodger |Hrsg=International Federation of Information Processing 1962 |Titel=Revised Report on the Algorithmic Language Algol 60 |Datum= |Kapitel=2.1 Letters |Sprache=en}}</ref> Dies lässt es später zu, die finale Bezeichnung der Schlüsselwörter bei einer Implementierung eines Compilers willkürlich festzulegen. Alternativ können die Schlüsselwörter über Nichtterminalsymbole als Folgen von Terminalsymbolen (z.&nbsp;B. Buchstabenfolgen) festgelegt werden.<ref name="Backus-1959" /> In einem Compiler werden die Schlüsselwörter in einer Vorphase, der [[Lexikalischer Scanner|lexikalischen Analyse]], erkannt und als besondere Zeichenfolgen weitergegeben. Kommentare werden von der lexikalischen Analyse erkannt (und oft entfernt), zudem ggf. auch weitere Elemente wie Gleitkommazahlen, Bezeichner und initiale Zeichenketten.

Damit lässt sich die gesamte Syntax z.&nbsp;B. eines PASCAL-Programms in BNF darstellen (teilweise gekürzt):<!-- <Restbezeichner> ::= [nichts] | <Buchstabe oder Ziffer> <Restbezeichner> [rekursiv] -->
<syntaxhighlight lang="bnf" line>
 <Programm>               ::= 'PROGRAM' <Bezeichner> 'BEGIN' <Satzfolge> 'END' .
 <Bezeichner>             ::= <Buchstabe> <Restbezeichner>
 <Restbezeichner>         ::= | <Buchstabe oder Ziffer> <Restbezeichner>
 <Buchstabe oder Ziffer>  ::= <Buchstabe> | <Ziffer>
 <Buchstabe>              ::= A | B | C | D | … | Z | a | b | … | z
 <Ziffer>                 ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
 <Satzfolge>              ::= …
 …
</syntaxhighlight>
Die Spezifikation in Zeile 3 beginnt mit <code>|</code> und bedeutet, dass dieser selbst-rekursive ''Restbezeichner'' auch „nichts“ sein darf, was am Ende der Rekursion zwingend erforderlich ist, weil sonst immer wieder ein neues Zeichen erforderlich wäre.

Eine Syntaxanalyse besteht aus der Rückführung eines Programmtexts auf das Nichtterminalsymbol <span style="font-family:monospace;"><Programm></span>. Ein Programm muss also mit dem Wort <span style="font-family:monospace;">PROGRAM</span> beginnen, auf das ein Bezeichner folgt. Bezeichner beginnen mit einem Buchstaben, gefolgt von beliebig vielen Buchstaben oder Ziffern.

Die Rückführung auf <Programm> gelingt bei
<syntaxhighlight lang="bnf">
  PROGRAM Ggt BEGIN … END .

  PROGRAM DiesisteinlangerBezeichnermit123 BEGIN … END .
</syntaxhighlight>
nicht jedoch bei
<syntaxhighlight lang="bnf">
  Ggt BEGIN … END .         (beginnt nicht mit PROGRAM)

  PROGRAM 123 BEGIN … END . (123 ist kein Bezeichner, Bezeichner müssen mit einem Buchstaben beginnen)
</syntaxhighlight>

== Beispiel ==
Hier eine BNF für eine deutsche [[Postanschrift]]:
<syntaxhighlight lang="bnf">
  <Post-Anschrift>  ::= <Personenteil> <Strasse> <Stadt>
  <Personenteil>    ::= <Titelteil> <Namensteil> <EOL>
  <Titelteil>       ::= <Titel> |
  <Namensteil>      ::= <Vornamensteil> <Nachname> | <Vornamensteil> <Namensteil>
  <Vornamensteil>   ::= <Vorname> | <Initial> .
  <Strasse>         ::= <Strassenname> <Hausnummer> <EOL>
  <Stadt>           ::= <Postleitzahl> <Stadtname> <EOL>
</syntaxhighlight>

Die Ausformulierung lautet:
* Eine Postanschrift besteht aus einem Personenteil, gefolgt von einer Straße, gefolgt von der Stadt.
* Der Personenteil besteht aus einem Titelteil und einem Namensteil, gefolgt von einem Zeilenende – gekennzeichnet durch <EOL>.
* Der Titelteil besteht aus einem Titel oder ist leer.
* Der Namensteil besteht aus einem Vornamensteil und einem Nachnamen oder aus einem Vornamensteil und wiederum einem Namensteil. (Diese Regel zeigt die Benutzung von [[Rekursion]] in BNFs und stellt den Fall dar, dass eine Person mehrere Vornamen und/oder [[Initiale]]n besitzt.)
* Der Vornamensteil besteht aus einem Vornamen oder einem Initial, auf den ein Punkt folgt.
* Eine Straße besteht aus einem Straßennamen, gefolgt von einer Hausnummer, gefolgt von einem Zeilenende.
* Eine Stadt besteht aus einer Postleitzahl, gefolgt von einem Stadtnamen, 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 Zusammenhang abhängen oder anderweitig spezifiziert sind.

Oft wird der Titel in eckige Klammern gestellt, der Titelteil entfällt. Dies bedeutet, dass der Titel leer sein darf:

Option:
<syntaxhighlight lang="bnf">
 <Personenteil>    ::= [ <Titel> ] <Namensteil> <EOL>
</syntaxhighlight>

Dieses Beispiel ist keine reine Form aus dem ''Algol 60 Report''. Die eckigen Klammern <span style="font-family:monospace;">[…]</span> stellen eine Option dar. Sie wurden einige Jahre später in der Definition von [[IBM]]s [[PL/I]] eingeführt, sind aber allgemein nur in [[EBNF]] anerkannt.

Option:
<syntaxhighlight lang="bnf">
 <Zahl> ::= [ - ] <Positive Zahl>
</syntaxhighlight>

Das Minuszeichen ist optional. Die Definition ist äquivalent zu
<syntaxhighlight lang="bnf">
 <Zahl> ::=  <Positive Zahl> | - <Positive Zahl>
</syntaxhighlight>

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

== Modifikationen der BNF ==
[[Datei:Modebnf.png|mini|400px|[[Syntaxdiagramm]]e der modifizierten 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 können auch Zeichen wie Punkt oder Minus nur schwer erkannt werden.

Die BNF wird daher in der Regel etwas modifiziert und ergänzt:
* Keine spitzen Klammern <span style="font-family:monospace;">&lt;…&gt;</span> für Nichtterminale.
* Zeichen als 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.
<syntaxhighlight lang="abnf" pre style="overflow:auto; white-space:nowrap;">
  ziffer            = "0" | "1" | "2" | "3" | … | "9" .
  zifferaussernull  = "1" | "2" | "3" | … | "9" .
  ziffernfolge      = ziffer | ziffer ziffernfolge .
  zahl              = [ "-" ] zifferaussernull [ ziffernfolge ] | "0" .
  programm          = PROGRAM bezeichner
                      BEGIN satzfolge END "." .
</syntaxhighlight>

Die Option wird manchmal nicht mit eckigen Klammern, sondern durch ein 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, ein- oder mehrfach) werden durch einen angefügten Stern dargestellt.
* Klammern dienen zur Gruppierung
<syntaxhighlight lang="abnf" pre style="overflow:auto; white-space:nowrap;">
  ziffernfolge ::= ziffer+ .
  zahl         ::= ( "-" )? zifferaussernull ( ziffernfolge )? | "0" .
  bezeichner   ::= buchstabe ( buchstabe | ziffer )* .
</syntaxhighlight>

Die [[erweiterte Backus-Naur-Form]] geht andere Wege. Sie verwendet eckige Klammern <span style="font-family:monospace;">[…]</span> für die Option, jedoch geschweifte Klammern <span style="font-family:monospace;">{…}</span> für die optionale Wiederholung. Terminale und Nichtterminale werden nicht streng unterschieden. Hier würde das obenstehende Beispiel so dargestellt:
<syntaxhighlight lang="ebnf" pre style="overflow:auto; white-space:nowrap;">
  Ziffernfolge = Ziffer { Ziffer } ;
  Zahl         = [ "-" ] ZifferAusserNull [ Ziffernfolge ] | "0" ;
  Bezeichner   = Buchstabe { Buchstabe | Ziffer } ;
</syntaxhighlight>

== Selbstdefinition einer (modifizierten) BNF ==
Eine modifizierte BNF kann sich selbst definieren:
<syntaxhighlight lang="abnf">
  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
  Grossbuchstabe    ::= "A" | "B" | … | "Z" .
  Kleinbuchstabe    ::= "a" | "b" | … | "z" .
  Sichtbareszeichen ::= "!" | "$" | "%" | … (''alle sichtbaren Zeichen'') .
  Anf               ::= '"' .
</syntaxhighlight>

Bei dieser Version werden Schlüsselwörter als Großbuchstaben dargestellt, Nichtterminale als Kleinbuchstaben. Wiederholungen müssen über Rekursionen definiert werden. Davon wird in der eigenen Definition auch Gebrauch gemacht (<span style="font-family:monospace;">modifiziertebnf</span>, <span style="font-family:monospace;">elementliste</span>, <span style="font-family:monospace;">nichtterminal</span>, <span style="font-family:monospace;">schlüsselwort</span>).

== BNF und Parser-Generatoren ==
Manche [[Parsergenerator]]en verwenden eine eigene Form der BNF als Eingabe und generieren hieraus einen [[Parser]] für die zugrundeliegende Programmiersprache.

Das dem Betriebssystem [[Unix]] beigegebene ''[[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 [[Attributgrammatik|S-Attribution]] ermöglicht, einem optionalen Teil jedoch kein sinnvoller semantischer Typ des Attributs zugeordnet werden kann. Als Ausgabe erhält man ein [[Unterprogramm]] in der Programmiersprache&nbsp;C. Die zugrundeliegende Grammatik muss dabei die [[LALR-Parser|LALR-Eigenschaft]] erfüllen.

== Siehe auch ==
* [[Formale Sprache]]
* [[Syntaxbaum]]

== Literatur ==
* {{Literatur
 | Autor = [[Donald E. Knuth]]
 | Titel = Backus Normal Form vs. Backus Naur Form
 | Sammelwerk = Communications of the ACM
 | Band = 7
 | Nummer = 12
 | Datum = 1964
 | Seiten = 735–737
 | DOI = 10.1145/355588.365140
}}

== Weblinks ==
{{Commonscat|Backus–Naur Form|Backus-Naur-Form}}
* [https://www.masswerk.at/algol60/report.htm ''Revised Report on the Algorithmic Language Algol 60''.] (englisch)
<!-- * [http://www-cgi.uni-regensburg.de/~brf09510/grammartypes.html Vergleich der BNF-Varianten] (englisch) nicht mehr online.-->
* {{RFC-Internet |RFC=5234 |Titel=Augmented BNF for Syntax Specifications: ABNF |Datum=2008-01}}

== Einzelnachweise ==
<references />

{{Lesenswert|3. März 2006|14146789}}

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Compilerbau]]
[[Kategorie:Normalform]]