Проширена Бакус–Наурова форма

Из Википедије, слободне енциклопедије

У рачунарству Проширена Бакус–Наурова форма (ЕБНФ) је нотација мета језика који се користи за изражавање контекстно слободних граматика: то је формални начин да се опишу програмски језици и формални језици. То је проширење основне Бакус–Наурове форме у метасинтаксичкој нотацији.

Оригинал је направљен по угледу на Никлауса Вирта. Најуобичајније коришћење ЕБНФ-а је обично дефинисано стандардима, од којих је најистакнутији ISO-14977.

Основе[уреди]

Код, нпр. изворни код рачунарског програма се састоји од терминалних симбола - то су видљиви карактери, цифре, интерпукцијски знаци, белине итд.

ЕБНФ дефинише правила извођења где су слагања симбола, једног у односу на други, прописана нетерминалима:

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

Ово правило извођења дефинише да се нетерминал цифра налази на левој страни оператора доделе. Усправна црта | представља избор и терминални симболи су обухваћени знацима навода праћених тачком са запетом као завршним карактером. Дакле цифра је 0 или цифра искључујући нулу која може бити 1 или 2 или 3 и тако даље све до 9.

Правило извођења може такође да укључује и слагање терминала или нетерминала, међусобно раздвојених запетом:

дванаест ::= "1", "2" ;
двеста један ::= "2", "0", "1" ;
триста дванаест ::= "3", дванаест ;
дванаест хиљада двеста један ::= дванаест, двеста један ;

Изрази који могу бити изостављени или поновљени, могу се представити у витичастим заградама { ... }:

природан број = цифра искључујући нулу, {цифра } ;

У овом случају, ниске 1, 2, ..., 10, ..., 12345, ... су регуларни изрази. Да би представили ово, све што је обухваћено витичастим заградама, може бити често својевољно поновљено, не укључујући ништа уопштено.

Опција може бити представљена у угластим заградама [ ...]:

цео број = "0" | [ "-"], природан број ;

Стога, цео број је нула (0 ) или природан број испред кога може претходити опциони знак минус.

ЕБНФ такође пружа, између осталих ствари, синтаксу да би се описала понављања назначеног броја сати, да би искључили део извођења или да би се убацили коментари у граматику БНФа.

Проширења према ИСО стандарду[уреди]

Према ИСО 14977 стандарду ЕБНФ је намењен да буде проширен и спомињу се две олакшице. Први је део о граматици ЕБНФ, посебног слагања, који је произвољни текст унутар знакова питања, чије је тумачење изван домета стандарда ЕБНФ-а. На пример, размак може бити дефинисан следећим правилом:

размак ::= ? US-ASCII карактер 32 ?;

Други део је коришћење чињенице да заграде не могу бити стављене поред идентификатора у БНФу.

Значи, проширење БНФ-а може да користи ову нотацију. На пример, у граматици Лисп-а, коришћење функције може бити дефинисано као следеће правило:

коришћење функције ::= листа(симбол, [ { израз }] );


Мотивација за проширење БНФ[уреди]

БНФ је имао проблем да се опције и понављања нису могли директно изразити. Уместо тога, била им је потребна употреба међуправила или алтернатива извођења, дефинисан да или не буде ништа или да буде опционо извођење за опцију, или било које поновљено извођење. Слична конструкција још може бити коришћена у ЕБНФ-у.

Опција:

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

може бити представљена у БНФ-стилу као:

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

или

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

Понављање:

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

може бити представљена у БНФ-стилу као:

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

Остала додавања и модификације[уреди]

ЕБНФ елиминише неке мане БНФ-а:

  • БНФ користи симболе (<, >, |, ::=) за себе. Када се они појаве у језику који треба да се дефинише, БНФ не може бити коришћен без модификација и објашњења.
  • БНФ синтакса може једино представити правило у једном реду.

БНФ решава ове проблеме:

  • Терминали су срого обухваћени знацима навода ("..." или '...'). Угласте заграде ("<...>") за нетерминале могу бити изостављене.
  • Завршни карактер, обично тачка са запетом (;) обележава крај правила.

Даље на ту тему, постоје механизми за унапређивање који су предвиђени, дефинишући број понављања, искључујући алтернативе (нпр. сви карактери искључујући знаке навода), коментаре итд. Упркос свим унапређивањима, ЕБНФ није моћнији од БНФа у погледу језика, који може да дефинише. Што се тиче принципа било које граматике дефинисане у ЕБНФ-у, може такође бити представљена у БНФу. Ипак ово често води ка значајно већем представљању.

ЕБНФ је стандардизована од стране ИСОа под шифром ИСО/ИЕЦ 14977:1996(E)

Под неким околностима било која ЕБНФ се односи као БНФ.


Други пример[уреди]

Једноставан програмски језик који једино дозвољава додељивања може бити дефинисан у БНФу као следеће:

(* прост програм у ЕБНФ − Википедија*)

програм ::= '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" ;
белина ::= ? белина карактер ? ;
сви карактери ::= ? сви видљиви карактери ? ;

Онда би синтакстно коректни програм био:

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

Језик би могао лако бити проширен истицањем контроле, аритметичким изразима и улазно/излазним инструкцијама. Тада би мали, применљив програмски језик био развијен.

Следећи карактери су предложени у стандарду и користе се овако представљени:

Метод Нотација
дефинисаност =
конкатенација ,
завршетак  ;
раздвајање |
опција [ ...]
понављање { ... }
груписање (... )
дупли наводници " ... "
једноструки наводници ' ... '
комантар (* ... *)
специјална секвенца  ? ... ?
изузетак -


Конвенције[уреди]

1. Следеће конвенције су употребљене:

  • Сваки мета-идентификатор ЕБНФ-а је написан као једна или више речи спојене цртицом.
  • Мета идентификатор који се завршава са “-симбол” је терминал ЕБНФ-а .

2. Нормални карактер представља сваки оператор ЕБНФ–а и његов имплицирани приоритет је (највиши приоритет на врху):

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

3. Нормални приоритет је представљен следећим паровима у загради

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

Као примери, следећа синтаксичка правила илуструју олакшице за изражавање понављања:

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

Терминал-ниске дефинисане су правилима као следеће:

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 итд.

Види још[уреди]

Спољашње везе[уреди]

Корисни страни линкови[уреди]