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 redigér
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 redigér
Heltal redigér
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 redigér
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 redigér
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 redigér
Programmeringssproget Ada er blevet beskrevet i en variant af BNF.[5]
Se også redigér
- Attributgrammatik - formelt sprog med semantisk databehandling
Referencer redigér
- ^ 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 redigér
- 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. |