Backus-Naur form

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

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.^[1]

I BNF bruges nogle få simple symboler, som alle kan skrives på en skrivemaskine. Der bruges følgende symboler:^[1]

< > 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.^[2]^[3] BNF har tydelige ligheder med Pāṇinis regler for grammatik, og BNF bliver derfor også nogle gange omtalt som Panini-Backus-formen.^[4]

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.^[5]

Se også

Attributgrammatik - formelt sprog med semantisk databehandling

Referencer

^ ^a ^b ^c Isaac Computer Science: Backus–Naur Form, backup
^ Kræver login: NAUR, Peter (ed.), "Revised Report on the Algorithmic Language ALGOL 60.", Communications of the ACM, Vol. 3 No.5, pp. 299-314, May 1960.
^ Backus, John W., "The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference," Proc. First Int'l. Conf. Information Processing, Butterworth, London, 1960, pp. 125-132. direkte link
^ "Panini-Backus Form" suggested. January 1967 Communications of the ACM 10:137, direkte link, backup
^ ada-auth.org: 1.1.4 Method of Description and Syntax Notation, backup

Eksterne henvisninger

BNF er anvendt her: RFC 733, RFC 822
W3C, World Wide Web Consortium: Notation

Spire

Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.

[isaac-1] Isaac Computer Science: Backus–Naur Form, backup

[2] Kræver login: NAUR, Peter (ed.), "Revised Report on the Algorithmic Language ALGOL 60.", Communications of the ACM, Vol. 3 No.5, pp. 299-314, May 1960.

[3] Backus, John W., "The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference," Proc. First Int'l. Conf. Information Processing, Butterworth, London, 1960, pp. 125-132. direkte link

[4] "Panini-Backus Form" suggested. January 1967 Communications of the ACM 10:137, direkte link, backup

[5] -auth.org: 1.1.4 Method of Description and Syntax Notation, backup

[1]

[2]

[3]

[4]

[5]