Backus-Naur form

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg
Broom icon.svg Der er ingen kildehenvisninger i denne artikel, hvilket muligvis er et problem.
Du kan hjælpe ved at angive kilder til de påstande, der fremføres i artiklen.
Question book-4.svg

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

Begreber, der er kendte, skrives som de er.

Overblik[redigér | redigér wikikode]

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.

Eksempler[redigér | redigér wikikode]

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.

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.

Programmering Stub
Denne artikel om datalogi eller et datalogi-relateret emne er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.