Proširena Bakus–Naurova forma

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

U računarstvu Proširena Bakus–Naurova forma (EBNF) je notacija meta jezika koji se koristi za izražavanje kontekstno slobodnih gramatika: to je formalni način da se opišu programski jezici i formalni jezici. To je proširenje osnovne Bakus–Naurove forme u metasintaksičkoj notaciji.

Original je napravljen po ugledu na Niklausa Virta. Najuobičajnije korišćenje EBNF-a je obično definisano standardima, od kojih je najistaknutiji ISO-14977.

Osnove[uredi]

Kod, npr. izvorni kod računarskog programa se sastoji od terminalnih simbola - to su vidljivi karakteri, cifre, interpukcijski znaci, beline itd.

EBNF definiše pravila izvođenja gde su slaganja simbola, jednog u odnosu na drugi, propisana neterminalima:

цифра искључујући нулу ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
цифра                ::= "0" | цифра искључујући нулу;

Ovo pravilo izvođenja definiše da se neterminal cifra nalazi na levoj strani operatora dodele. Uspravna crta | predstavlja izbor i terminalni simboli su obuhvaćeni znacima navoda praćenih tačkom sa zapetom kao završnim karakterom. Dakle cifra je 0 ili cifra isključujući nulu koja može biti 1 ili 2 ili 3 i tako dalje sve do 9.

Pravilo izvođenja može takođe da uključuje i slaganje terminala ili neterminala, međusobno razdvojenih zapetom:

dvanaest ::= "1", "2" ;
dvesta jedan ::= "2", "0", "1" ;
trista dvanaest ::= "3", dvanaest ;
dvanaest hiljada dvesta jedan ::= dvanaest, dvesta jedan ;

Izrazi koji mogu biti izostavljeni ili ponovljeni, mogu se predstaviti u vitičastim zagradama { ... }:

prirodan broj = cifra isključujući nulu, {cifra } ;

U ovom slučaju, niske 1, 2, ..., 10, ..., 12345, ... su regularni izrazi. Da bi predstavili ovo, sve što je obuhvaćeno vitičastim zagradama, može biti često svojevoljno ponovljeno, ne uključujući ništa uopšteno.

Opcija može biti predstavljena u uglastim zagradama [ ...]:

ceo broj = "0" | [ "-"], prirodan broj ;

Stoga, ceo broj je nula (0 ) ili prirodan broj ispred koga može prethoditi opcioni znak minus.

EBNF takođe pruža, između ostalih stvari, sintaksu da bi se opisala ponavljanja naznačenog broja sati, da bi isključili deo izvođenja ili da bi se ubacili komentari u gramatiku BNFa.

Proširenja prema ISO standardu[uredi]

Prema ISO 14977 standardu EBNF je namenjen da bude proširen i spominju se dve olakšice. Prvi je deo o gramatici EBNF, posebnog slaganja, koji je proizvoljni tekst unutar znakova pitanja, čije je tumačenje izvan dometa standarda EBNF-a. Na primer, razmak može biti definisan sledećim pravilom:

razmak ::= ? US-ASCII karakter 32 ?;

Drugi deo je korišćenje činjenice da zagrade ne mogu biti stavljene pored identifikatora u BNFu.

Znači, proširenje BNF-a može da koristi ovu notaciju. Na primer, u gramatici Lisp-a, korišćenje funkcije može biti definisano kao sledeće pravilo:

korišćenje funkcije ::= lista(simbol, [ { izraz }] );


Motivacija za proširenje BNF-a[uredi]

BNF je imao problem da se opcije i ponavljanja nisu mogli direktno izraziti. Umesto toga, bila im je potrebna upotreba međupravila ili alternativa izvođenja, definisan da ili ne bude ništa ili da bude opciono izvođenje za opciju, ili bilo koje ponovljeno izvođenje. Slična konstrukcija još može biti korišćena u EBNF-u.

Opcija:

Означен број ::= [ означен,] број ;

može biti predstavljena u BNF-stilu kao:

означен број ::= означен, број | број ;

ili

означен број ::= опционо означен, број;
опционо означен ::= ε |означен ; (* епсилон је коришћен да би јасније назначио празно извођење *)

Ponavljanje:

број ::= { цифра } ;

može biti predstavljena u BNF-stilu kao:

број ::= цифра | број цифра;

Ostala dodavanja i modifikacije[uredi]

EBNF eliminiše neke mane BNF-a:

  • BNF koristi simbole (<, >, |, ::=) za sebe. Kada se oni pojave u jeziku koji treba da se definiše, BNF ne može biti korišćen bez modifikacija i objašnjenja.
  • BNF sintaksa može jedino predstaviti pravilo u jednom redu.

BNF rešava ove probleme:

  • Terminali su srogo obuhvaćeni znacima navoda ("..." ili '...'). Uglaste zagrade ("<...>") za neterminale mogu biti izostavljene.
  • Završni karakter, obično tačka sa zapetom (;) obeležava kraj pravila.

Dalje na tu temu, postoje mehanizmi za unapređivanje koji su predviđeni, definišući broj ponavljanja, isključujući alternative (npr. svi karakteri isključujući znake navoda), komentare itd. Uprkos svim unapređivanjima, EBNF nije moćniji od BNFa u pogledu jezika, koji može da definiše. Što se tiče principa bilo koje gramatike definisane u EBNF-u, može takođe biti predstavljena u BNFu. Ipak ovo često vodi ka značajno većem predstavljanju.

EBNF je standardizovana od strane ISO-a pod šifrom ISO/IEC 14977:1996(E).

Pod nekim okolnostima bilo koja EBNF se odnosi kao BNF.


Drugi primer[uredi]

Jednostavan programski jezik koji jedino dozvoljava dodeljivanja može biti definisan u BNFu kao sledeće:

(* prost program u EBNF − Vikipedija*)

програм ::= 'PROGRAM', белина, идентификатор, белина ,
           'BEGIN', белина ,
           { додела, ";", белина} ,
           'END.' ;
идентификатор = слово, { слово| цифра } ;
број ::= [ "-"], цифра, { цифра} ;
ниска ::= '"', { сви карактери − '"' }, '"' ;
додела ::= идентификатор, ":=", (број | идентификатор | ниска ) ;
слово ::= "A" | "B" | "C" | "D" | "E" | "F" | "G"
                     | "H" | "I" | "J" | "K" | "L" | "M" | "N"
                     | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
                     | "V" | "W" | "X" | "Y" | "Z" ;
цифра ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
белина ::= ? белина карактер ? ;
сви карактери ::= ? сви видљиви карактери ? ;

Onda bi sintakstno korektni program bio:

PROGRAM DEMO1 
BEGIN
  A0:=3;
  B:=45;
  H:=-100023;
  C:=A;
  D123:=B34A;
  BABOON:=GIRAFFE;
  TEXT:=Cao svete!";
END.

Jezik bi mogao lako biti proširen isticanjem kontrole, aritmetičkim izrazima i ulazno/izlaznim instrukcijama. Tada bi mali, primenljiv programski jezik bio razvijen.

Sledeći karakteri su predloženi u standardu i koriste se ovako predstavljeni:

Metod Notacija
definisanost =
konkatenacija ,
završetak ;
razdvajanje |
opcija [ ...]
ponavljanje { ... }
grupisanje (... )
dupli navodnici " ... "
jednostruki navodnici ' ... '
komantar (* ... *)
specijalna sekvenca ? ... ?
izuzetak -


Konvencije[uredi]

1. Sledeće konvencije su upotrebljene:

  • Svaki meta-identifikator EBNF-a je napisan kao jedna ili više reči spojene crticom.
  • Meta identifikator koji se završava sa “-simbol” je terminal EBNF-a .

2. Normalni karakter predstavlja svaki operator EBNF–a i njegov implicirani prioritet je (najviši prioritet na vrhu):

* понављање-симбол
- изузетак-симбол
, конкатенација-симбол
| дефиниција-раздвајање-симбол
= дефинисаност-симбол
; завршетак-симбол  

3. Normalni prioritet je predstavljen sledećim parovima u zagradi

´  први-квота-симбол            први-квота- симбол  ´
"  други- квота-симбол         други- квота-симбол "
(* почетни-коментар-симбол     крајњи-коментар-симбол *)
(почетни-групни-симбол            крајњи-групни-симбол  )
[  почетни-опциони-симбол           крајњи-опциони-симбол ]
{  почетни-поновљени-симбол     крајњи-поновљени-симбол }
?  специјална-секвенца-симбол   специјална-секвенца-симбол ?

Kao primeri, sledeća sintaksička pravila ilustruju olakšice za izražavanje ponavljanja:

aa = "A";
бб = 3 * aa, "B";
цц = 3 * [aa], "C";
дд = {aa}, "D";
ee = aa, {aa}, "E";
фф = 3 * aa, 3 * [aa], "F";
гг= {3 * aa}, "D";

Terminal-niske definisane su pravilima kao sledeće:

aa: A
бб: AAAB
цц: C AC AAC AAAC
дд: D AD AAD AAAD AAAAD итд.
ee: AE AAE AAAE AAAAE AAAAAE итд.
фф: AAAF AAAAF AAAAAF AAAAAAF
гг: D AAAD AAAAAAD итд.

Vidi još[uredi]

Korisni strani linkovi[uredi]

Spoljašnje veze[uredi]