Backus-Naur-form
Backus-Naur-form, förkortat BNF, har sitt namn efter upphovsmännen John Backus och Peter Naur. I och med BNF-notationen introducerades för första gången en formell notation (se Formell grammatik) för att beskriva syntaxen för ett givet språk. Ett språk som går att beskriva med en formell notation definieras som ett formellt språk.
Element
BNF-notationen omfattar tre grundläggande element: Metasymboler, Terminalsymboler och Icke-terminalsymboler.
Metasymboler
Meta-symboler i BNF-notationen är
::= "Definieras som" | "Eller" < > "Kategorinamn"
Terminalsymboler
Terminalsymboler i BNF-notationen är symboler som beskrivs i grammatiken exakt som de ska förekomma i språket som definieras.
Icke-terminalsymboler
Icke-terminalsymboler i BNF-notationen representeras av metasymbolen Kategorinamn, och kan väljas godtyckligt. Ett annat ord för Icke-terminalsymbol är Regel - en grammatik består ju av regler.
Regler kan förekomma fristående (definition) eller inbakade i andra regler (referens). En BNF-regel som beskriver en icke-terminalsymbol kan alltså vara på formen
icke-terminal ::= sekvens av alternativ bestående av strängar av terminalsymboler eller icke-terminalsymboler separerade av |
Utökningar i BNF
Med åren har två utökade metasymboler av BNF-notationen kommit att bli vanliga:
[ ] "Optionell entitet" { } "Repeteras noll eller flera gånger"
BNF skriven i BNF
Med hjälp av dessa regler kan BNF-notationen beskrivas i termer av BNF som följer:
<syntax> ::= { <regel> } <regel> ::= <identifierare> "::=" <uttryck> <uttryck> ::= <term> { "|" <term> } <term> ::= <faktor> { <faktor> } <faktor> ::= <identifierare> | <qsymbol> | "(" <uttryck> ")" | "[" <uttryck> "]" | "{" <uttryck> "}" <identifierare> ::= tecken { tecken | siffra } <qsymbol> ::= """ { godtyckligt tecken } """
Analys av BNF i BNF-notation
Om vi bryter ner notationen ovan ser vi följande:
<syntax> ::= { <regel> }
Betyder "En syntax består av noll eller flera regler"
<regel> ::= <identifierare> "::=" <uttryck>
Betyder "En regel är på formen 'En identifierare tilldelas ett uttryck'"
<uttryck> ::= <term> { "|" <term> }
Betyder "Ett uttryck består av en eller flera termer åtskilda av metasymbolen |"
<term> ::= <faktor> { <faktor> }
Betyder "En term består av en eller flera faktorer"
<faktor> ::= <identifierare> | <qsymbol> | "(" <uttryck> ")" | "[" <uttryck> "]" | "{" <uttryck> "}"
Betyder "En faktor består av en identifierare eller en qsymbol eller ett enstaka uttryck eller ett optionellt uttryck eller en sekvens av noll eller flera uttryck"
<identifierare> ::= tecken { tecken | siffra }
Betyder "En identifierare består av ett (bokstavs-)tecken och noll eller flera tecken eller siffror"
<qsymbol> ::= """ { godtyckligt tecken } """
Betyder "En qsymbol består av noll eller flera godtyckliga tecken omslutna av citationstecken"
BNF för ett Ada-program
<program> ::= <inkluderingsdelen> procedure <programmets namn> is <deklarationsdelen> begin <instruktionsdelen> end <programmets namn>;
<instruktionsdelen> ::= <instruktioner>
<instruktioner> ::= <instruktion>; | <instruktion>; <instruktioner>
Se även
- LBNF
Externa länkar
Wikimedia Commons har media som rör Backus-Naur-form.
Bilder & media