Backus-Naur-form

Från Rilpedia

Texten från svenska Wikipedia

BNF är en förkortning av Backus-Naur Form, 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>;

<instrNedan beskrivs i uktionsdelen> ::= <instruktioner>

<instruktioner> ::= <instruktion>; | <instruktion>; <instruktioner>

Se även

• LBNF