BNF

Fra Wikipedia, den frie encyklopædi

Du har nye beskeder (forskel fra næstsidste redigering).

Backus-Naur form (BNF-form) er en metasyntax, dvs. en formel måde at beskrive formelle sprog.

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, der ikke er beskrevet til bunds.
| bruges som "eller".
::= læses som "består af".

Begreber, der er kendte, skrives som de er.

[redigér] Overblik

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

[redigér] Eksempler

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. Eksempelt 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 løser disse problemer.

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> | ""  
<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> "'"

Dette understreger virkelig den rekursive natur.