Backus-Naur form

Backus-Naur form (BNF) er en metasyntaks, dvs. en formel måde at beskrive formelle sprogs syntaks.

BNF er en meget udbredt notation til at beskrive grammatikken af programmeringsprog. De fleste lærebøger om teorien bag programmering beskriver programmeringssprog i BNF.

I BNF bruges nogle få simple symboler, som alle kan skrives på en skrivemaskine. Der bruges følgende symboler:
 < > markerer et begreb (variabel), der skal defineres.
 | læses som "eller".
 ::= læses som "består af".

Begreber, der er defineret (konstanter, terminale begreber), skrives som de er.

Historisk 

BNF er opkaldt efter John Backus og danskeren Peter Naur. De var pionerer i datalogi med speciale i design af compilere. BNF blev oprindeligt lavet for at kunne beskrive reglerne i ALGOL 60. BNF har tydelige ligheder med Pāṇinis regler for grammatik, og BNF bliver derfor også nogle gange omtalt som Panini-Backus-formen.

Eksempler

Heltal 
Beskrivelse af heltal.

 <heltal>           ::= <positivt heltal> | <nul> | <negativt heltal>
 <positivt heltal>  ::= <positivt ciffer> | <positivt heltal> <ciffer>
 <nul>              ::= 0
 <negativt heltal>  ::= – <positivt heltal>
 <ciffer>           ::= <positivt ciffer> | <nul>
 <positivt ciffer>  ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Som det fremgår af eksemplet beskrives gentagelser rekursivt. I eksemplet er et positivt heltal beskrevet som et positivt ciffer eller et positivt heltal efterfulgt af et ciffer. Eksemplet viser også nogle af begrænsningerne i BNF. Opremsning af beslægtede værdier er omstændelig, og valgfrie elementer er ikke markerede som sådanne. (EBNF (eng. Extended Backus-Naur form dansk udvidet Backus-Naur form) løser disse problemer.)

Folkeregisteradresse 
Dette er en BNF for en dansk postadresse:
  <postadresse>     ::= <persondel> <vej> <by>
  <persondel>       ::= <titeldel> <navnedel> <linjeskift>
  <titeldel>        ::= <titel> | ""
  <navnedel>        ::= <fornavnedel> <efternavn> | <fornavnedel> <navnedel>
  <fornavnedel>     ::= <fornavn> | <stort bogstav> "."
  <vej>             ::= <vejnavn> <husnummer> <linjeskift>
  <husnummer>       ::= <positivt heltal> | <positivt heltal> <bogstav> | <positivt heltal> <etageangivelse> |  
                        <positivt heltal> <bogstav> <etageangivelse> 
  <etageangivelse>  ::= <etage> "." | <etage> "." " " <lejlighedsdel>
  <etage>           ::= st | <positivt heltal>  
  <lejlighedsdel>   ::= "tv" | "mf" | "th"
  <by>              ::= <postnummer> <bynavn> <linjeskift>
  <postnummer>      ::= <ciffer> <ciffer> <ciffer> <ciffer>
  <ciffer>          ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

BNF 
Også definitionen af BNF kan opskrives med BNF:

 <syntax>           ::= <rule> | <rule> <syntax>
 <rule>             ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" 
                        <opt-whitespace> <expression> <line-end>
 <opt-whitespace>   ::= " " <opt-whitespace> | ""  <!-- "" is empty string, i.e. no whitespace -->
 <expression>       ::= <list> | <list> "|" <expression>
 <line-end>         ::= <opt-whitespace> <EOL> | <line-end> <line-end>
 <list>             ::= <term> | <term> <opt-whitespace> <list>
 <term>             ::= <literal> | "<" <rule-name> ">"
 <literal>          ::= '"' <text> '"' | "'" <text> "'" <!-- actually, the original BNF didn't use quotes -->

Dette er et godt eksempel på brugen af rekursion.

Programmeringssproget Ada 
Programmeringssproget Ada er blevet beskrevet i en variant af BNF.

Se også 
 Attributgrammatik - formelt sprog med semantisk databehandling

Referencer

Eksterne henvisninger 
 BNF er anvendt her: , 
 W3C, World Wide Web Consortium: Notation

Implementation af programmeringssprog