Backus eta Naurren formatu

Backus eta Naurren formatua, Backus-Naurren formatua edo BNF programazio-lengoaien arau sintaktikoak deskribatzeko erabiltzen den notazioa da.

John W. Backusek eta Peter Naurrek asmatu zuten Algol 60 programazio-lengoaia sortu zutenean.

Hasieran Backus eta Naurren formatu normala izenarekin ezagutzen zen, gero Backus-Naurren formatua bihurtu zen Donald Knuthek horrela iradoki eta gero.

Sintaxia 

BNFn hiru osagai mota hauek bereizten dira: meta-ikurrak, bukaerakoak eta ez-bukaerakoak

 Meta-ikurrak BNF lengoaiaren ikurrak dira
 Bukaerako ikurrak deskribatzen den lengoaiaren ikurrak dira
 Ez-bukaerako ikurrak lengoaia deskribatzeko produkzio zuzenetan kategoriak dira.

Adibideak 
"if" agindu bat C programazio-lengoaian :
  <if_egitura>   :: = if "(" <baldintza> ")" "{" <aginduak> "}"

Aldaerak 
BNFren aldaera eta hedapen ugari daude, seguru asko adierazpen erregularretako "*" edo "+" komodin guztiekin edo batzuk bakarrik. Backus-Naur forma hedatua (EBNF) aldaera arrunta da. Izan ere, aurreko adibidea ez da ALGOL 60 txostenerako asmatutako forma hutsa. Parentesi notazioa "[ ]" urte batzuk geroago sartu zen IBMko PL/I lengoaiaren definizioan, baina orain unibertsalki onartzen da. ABNF IETF (Interneteko estandarrak definitzen dituen erakundea) protokoloak deskribatzeko erabiltzen den beste hedapen bat da.

Programazio-lengoaia bateko sintaxia definitzeko meta-lengoaia estandar bakarra Backus–Naur Formatua edo BNF da. Baina duen arazoa malgutasun-falta da. Izan ere, BNF-z idatzitako gramatikak oso errepikakorrak dira, errepikapenak definitzeko ezin direlako adierazpen erregularretan erabili ohi diren Kleene izarra ("*") bezalako eragiketak erabili. Horregatik, beste meta-lengoaia batzuekin konparatuta, erregela gehiago idatzi behar ohi dira. Hala ere, BNF asko zabaldu zen geroago, eta honetan oinarritutako beste meta-lengoaia asko sortu ziren. Gaur egun gehien ezagutzen direnak EBNF eta ABNF dira. Alde batetik, ABNF (Augmented BNF) IETF-k definitzen dituen lengoaiak deskribatzeko erabiltzen da. Lengoaia horretan, literalak kakotxen artean gehitu daitezke, horrela BNF-k zuen murriztapena konpontzen duela. Gainera, errepikapenak aurrizki bidez laburtu daitezke (‘4DIGITU’ katea ‘DIGITU DIGITU DIGITU DIGITU’ katearen baliokidea da), eta Kleene izarraren pareko eragiketak ere onartzen ditu. Beste aldetik, EBNF (Extended BNF) meta-lengoaia familia bat dela esan daiteke. Familia horren barnean, BNFn oinarritutako eta hortik hedatutako meta-lengoaia asko sartzen dira. Horien artean, batek ISO 14977 estandarra jarraitzen du. Baina estandar horretan definitutako EBNF lengoaia ez da oso erabilia. Izan ere, artikuluan aipatzen den bezala, bi EBNF mota nagusi daude: errepikapenak sinplifikatzeko adierazpen erregularretan oinarritzen diren EBNF-ak, eta Niklaus Wirth-ek sortutako WSN meta-lengoaian oinarritutakoak.

Analizatzaile sintaktikoen adierazpen gramatikalak BNF-n eta maila lexikala adierazpen erregularretan definitu ohi dira. Gaur egun, adierazpen erregularrak oso erabiliak dira. Lengoaia ezagunenek beren liburutegi estandarretan dute horiek tratatzeko tresnak. Horregatik, hauetan oinarritutako EBNF lengoaiak dira gehien erabiltzen direnak, eta erabiltzen hasteko errazenak.

Erreferentziak

Ikus, gainera 

 Konpiladore
 Programazio-lengoaia

Kanpoko estekak 

 Knuth, Donald (1964-12-01) «backus normal form vs. Backus Naur form» Communications of the ACM (12): 735–736 doi:10.1145/355588.365140 ISSN 0001-0782

Informatika teorikoa
Programazio lengoaiak
Programazio hizkuntzen gaiak