Backus-Naurov oblik

Backus-Naurov oblik (još i Backus-Naurov formalizam, Backusov normalni oblik, Panini-Backusov oblik ili Backus-Naurova forma^[1] - obično samo kratko kao BNF, od engl. Backus-Naur form) metasintaksa je korištena za izražavanje kontekstno neovisnih gramatika: to jest, formalnih način opisa formalnih jezika.

BNF je naširoko korištena notacija za gramatike računalnih programskih jezika, instrukcijskih skupova i komunikacijskih protokola, te kao jedna od mogućih notacija za prikaz dijelova gramatike prirodnog jezika (npr. stope u sanskrtskom pjesništvu). Većina udžbenika iz teorije programskih jezika i/ili semantike dokumentiraju programski jezik baš u BNF notaciji.

Postoje mnoga proširenja i varijante BNF.

Povijest

John Backus je stvorio ovu notaciju kako bi izrazio gramatiku ALGOL-a. Na prvoj konferenciji World Computer Congress, koja se dogodila u Parizu 1959., Backus je predstavio svoj rad pod nazivom "The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference", formalni opis jezika IAL koji je kasnije prozvan ALGOL 58. Formalni jezik koji je on predstavio je bio zasnovan na sustavu produkcija Emila Posta. Generativne gramatike su bile aktivno područje matematičkog proučavanja, npr. od strane Noama Chomskyja, koji ih je primijenio na gramatiku prirodnih jezika.^[2]^[3]

Peter Naur je kasnije pojednostavio Backusovu notaciju kako bi minimizirao skup korištenih znakova (karaktera), te se na prijedlog Donalda Knutha njegovo ime dodalo u znak priznanja njegova doprinosa.

Backus-Naurov oblik ili BNF gramatike imaju značajne sličnosti sa Pāṇinijevim gramatičkim pravilima, te se notacija stoga ponekad naziva i Panini-Backusov oblik.

Uvod

BNF specifikacija je skup produkcijskih pravila, koji su zapisani kao

<simbol> ::= <izraz sa simbolima>

gdje je <simbol> nezavršni simbol, a izraz se sastoji od slijedova simbola i/ili slijedova odvojenih uspravnom crtom., '|', označujući mogućnost izbora, pri čemu je svaka jedinka izbora moguća zamjena za krajnje lijevi simbol produkcije. Simboli koji se nikad ne pojavljuju na lijevoj strani produkcije se zovu završni simboli.

Primjer

Kao primjer, razmotrimo BNF za poštanske adrese u SAD-u:

  <poštanska-adresa> ::= <ime-dio> <adresa-ulice-dio> <poštanski-broj-dio>

           <ime-dio> ::= <osobni-dio> <prezime> <opc-jr-dio> <kraj-linije> 
                       | <osobni-dio> <ime-dio>
 
        <osobni-dio> ::= <ime> | <inicijal> "." 

  <adresa-ulice-dio> ::= <opc-stan-broj> <kućni-broj> <ime-ulice> <kraj-linije>

<poštanski-broj-dio> ::= <ime-grada> "," <kodni-broj-države> <poštanski-broj> <kraj-linije>

Što se čita na sljedeći način:

Poštanska se adresa sastoji do dijela za ime, nakon kojeg slijedi ime ulice te poštanski broj.
ime-dio se sastoji od ili osobni-dio nakon kojeg slijedi prezime nakon kojeg slijedi opcionalni "jr-dio" (Jr., Sr., ili broj dinastije) te oznaka kraja linije, ili osobnog dijela nakon kojeg slijedi ime-dio (ovo pravilo slikovito predočava uporabu rekurzije u BNF notaciji, pokrivajući slučaj ljudi koji koriste višestruka početna i srednja imena i/ili inicijale).
osobni-dio se sastoji ili od imena, ili inicijala nakon kojeg slijedi točka.
Adresa ulice se sastoji od opcionalnog specifikatora stana, nakon kojeg slijedi kućni broj, nakon kojeg slijedi ime ulice, nakon kojeg slijedi kraj linije
poštanski-broj-dio se sastoji od imena grada, nakon kojeg slijedi zarez, nakon kojeg slijedi kodni broj savezne države, nakon kojeg slijedi poštanski broj te kraj linije.

Valja uočiti da su mnogi elementi (kao što je format imena, specifikatora stana ili poštanskog broja) ovdje ostali nespecificirani. Ako to bude potrebno, mogu biti opisani dodatnim BNF pravilima.

Dodatni primjeri

BNF sintaksa može biti prikazana samom BNF notacijom na sljedeći način:

   <sintaksa> ::= <pravilo> | <pravilo> <sintaksa>
    <pravilo> ::= <opc-bjelina> "<" <ime-pravila> ">" <opc-bjelina> "::=" 
                  <opc-bjelina <izraz> <kraj-linije>
<opc-bjelina> ::= " " <opc-bjelina> | ""  
      <izraz> ::= <lista> | <lista> "|" <izraz>
   <line-end> ::= <opc-bjelina> <EOL> | <kraj-linije> <kraj-linije>
      <lista> ::= <term> | <term> <opc-bjelina> <lista>
       <term> ::= <literal> | "<" <ime-pravila> ">"
    <literal> ::= '"' <tekst> '"' | "'" <text> "'"

Ova sintaksa pretpostavlja da nije potrebna bjelina za pravilnu interpretaciju produkcijskih pravila. <EOL> je znak kraja linije (u ASCII-u: carriage return i/ili line feed, ovisno o operacijskom sustavu). <ime-pravila> i <tekst> valja zamijeniti s imenom/labelom deklariranog pravila ili literalnim tekstom, respektivno.

Varijante

Postoje mnoge varijante i proširenja BNF notacije, općenito ili u svrhu pojednostavljenja i sažimanja, ili u svrhu prilagodbe specifičnoj primjeni. Jedna zajednička osobina mnogih izraza jest korištenje regex operatora ponavljanja kao što su * i +. Prošireni Backus-Naurov oblik (EBNF) je uobičajena takva varijanta. Ustvari, gornji primjer nije čisti oblik koji je izmišljen za ALGOL 60 izvještaj. Notacija preko uglatih zagrada "[ ]" je uvedena nekoliko godina kasnije u IBM-ovoj definiciji jezika PL/I, iako je danas općeprihvaćena. ABNF je druga ekstenzija obično korištena za opis IETF protokola.

Gramatike koje parsiraju izraze su izgrađene nad BNF i notacijom regularnih izraza kako bi oblikovale alternativnu klasu formalnih gramatika, koja je po prirodi esencijalno analitička mjesto generativna.

Mnoge BNF notacije koje se danas mogu naći na Webu su više namijenjene da čitanju od strane ljudi, te stoga nisu formalnog karaktera. Ovakvi primjeri često uključuju mnoge od sljedećih sintaksnih pravila i proširenja:

Opcionalne elemente zagrađene u uglate zagrade. Na primjer, [<element-x>]
Elementi koji se ponavljaju 0 ili više puta su zagrađeni u vitičaste zagrade. Na primjer, <riječ> ::= <slovo> { <slovo> }
Nakon elemenata koji se ponavljaju 1 ili više puta slijedi znak '+'.
Završni simboli se mogu pojavljivati otisnuti masno a nezavršni simboli u običnom tekstu mjesto korištenja kurziva i uglatih zagrada.
Opetovanje elemenata se označuje zvjezdicom koje sa stavlja iza elementa ‘*’
Alternativni izbori produkcije su odvojeni simbolom uspravne crte ‘|’. Na primjer, <alternativa-A> | <alternativa-B>
Grupiranje elemenata se označuje zatvaranjem u jednostavne zagrade.

Izvori

↑ Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 93
↑ Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.
↑ Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.

Vanjske poveznice

Algol-60 BNF, izvorni BNF.
Jednostavne gramatike iz BNF Web kluba.
[1] sadrži poruku na newsgrupi comp.compilers koja objašanjava povijest dvaju imena (Backus-Naurov oblik vs. Backusov normalni oblik).
Članak BNF and EBNF: What are they and how do they work? autora Larsa Mariusa Garshola.
RFC 4234 Augmented BNF for Syntax Specifications: ABNF
Usporedba različitih varijanti BNF notacije
Sintaksni dijagram za EBNF
Generiranje dijagrama iz EBNF

[InfoRjecnik-1] Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 93

[Chomsky1956-2] Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.

[Chomsky1957-3] Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.

[1]

[2]

[3]