Бакус–Наурова форма

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

Џон Бакус и Питер Наур, су развили контекстно слободну граматику да би дефинисали синтаксу програмских језика, користећи две групе правила: тј, лексичка правила и синтаксичка правила.

БНФ је широм коришћена нотација за граматике програмских језика, листа инструкција и комуникацијских протокола, као и нотација за представљање граматика свакодневног језика. У Бакусовој нотацији синтакса програмског језика описује се помоћу коначног скупа металингвистичких формула (МЛФ).

Постоје многа проширења и варијанте БНФ-а.

Историја

Џон Бакус је створио нотацију да би изразио граматику АЛГОЛ-а. На Првом светском рачунарском конгресу, који је одржан у Паризу 1959. године, Бакус је представио Синтаксу и семантику предложеног интернационалног алгебарског језика на АЦМ-ГАММ конференцији у Цириху, формални опис ИАЛ-а, који је касније назван АЛГОЛ 58. Формални језик који је он представио, заснован је на систему извођења Емила Поста.

Генеративне граматике биле су активни предмет математичке студије, као на пример Ноама Чомског, који их је користио у граматици свакодневног језика.

Питер Наур, (АЛГОЛ 60, 1963) дефинисао је Бакусову нотацију као Бакусову нормалну форму и поједноставио је да би умањио класу коришћених карактера и, на предлог Доналда Кнута, његово име је додато као признање његовог доприноса. Кнут је демантовао његово првобитно замењивање Н за Нормална, говорећи да БНФ није нормална форма у било ком смислу.

Граматике БНФ-а имају значајне сличности са правилима Панинијеве граматике, тако да се нотација често тумачи као Панини-Бакус форма.

Увод

У БНФ-у се користе следеће конвенције за записивање правила граматике:

a. уместо симбола -> користи се симбол ::=;

b. помоћни симболи се наводе међу заградама < и >;

c. вертикална црта (избор) раздваја десне стране правила које одговарају истом симболу са леве стране правила;

d. празна ниска ε се записује као <empty>.

Симболи који се никада не појављују на левој страни правила су терминали.

Пример

Као пример, узмимо у обзир ову БНФ за поштанску адресу у САД:

 <поштанска-адреса> ::= <део-за-име> <улица> <зип-део>

 
      <део-за-име> ::= <лични-део> <презиме> <опц-јр-део> <ЕОЛ> 
                    | <лични-део> <део-за-име>
  
  <лични-део> ::= <име> | <иницијали> "." 
 
 <улица> ::= <опц-бр-стана> <кућни-број> <улица> <ЕОЛ>
 
  <зип-део> ::= <име-града> "," <државни-број> <поштански-број> <ЕОЛ>
 
    <опц-јр-део> ::= „Ср." | „Јр." | <римски-број> | ""

Ово се преводи на енглески као:

Поштанска адреса која се састоји од дела за име, праћеног делом за улицу, праћеног делом за поштански број.
Део за име се састоји или од личног дела праћеног презименом, праћеног опционим “јр. делом” (Јр., Ср. или династијским бројем) и крајем линије, или од личног дела праћеног делом за име (Ово правило приказује употребу рекурзије у БНФ-у покривајући случај када људи користе вишеструка имена и средња имена и/или иницијале).
Личног дела који се састоји или од имена или од иницијала праћеног тачком.
Улица се састоји од опционог описа стана, праћеног кућним бројем, праћеног улицом, праћеног крајем линије.
Зип део се састоји од имена града, праћеног зарезом, праћеног државним бројем, праћеног поштанским бројем, праћеног крајем линије.

Ваља приметити да многе ствари (као што су формат имена, описивање стана, поштанског броја и римских цифара) су овде остављене неодређене.

Ако је потребно, она могу бити описана користећи додатна правила БНФ-а.

Даља објашњења

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

 <синтакса> ::= <правило> | <правило> <синтакса>

 <правило> ::= <опц-белина> "<" <име-правила> ">" < опц-белина > "::=" 
            < опц-белина > <израз> <крај-линије>
 < опц-белина > ::= " " < опц-белина > | ""  <!-- "" је празна ниска,  тј. нема белине -->

 <израз> ::= <листа> | <листа> "|" <израз>

 <крај-линије> ::= < опц-белина > <ЕОЛ> | <крај-линије> <крај-линије>

 <листа> ::= <терм> | <терм> < опц-белина > <листа>

 <терм> ::= <литерал> | "<" <име-правила> ">"

 <литерал> ::= '"' <текст> '"' | "'" <текст> "'" <!—у ствари, оригинални БНФ не користи наводнике -->

Ово симулира да белина није потребна за одговарајуће тумачење. <ЕОЛ> представља одговарајући опис краја линије (у ASCII запису, повратак на почетак реда и/или нови ред, зависно од оперативног система). <име-правила> и <текст> морају да буду замењени декларисаним именом/ознаком правила или дословним текстом.

Варијанте

Постоје многе варијанте и проширења БНФ-а, или због једноставности и сажетости или да је прилагоде одређеном коришћењу. Једно од заједничких обележја многих варијанти је употреба регуларног израза, понављање операција * и +. Проширена БНФ је једна од честих. У ствари, пример изнад није чиста форма, направљена за извештај АЛГОЛ-а 60. Обележавање заграда "[]" уведено је пар година касније у IBM-овој ПЛ/I, дефиницији, али је данас широм препознатљива.

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

Многе БНФ спецификације које су данас доступне путем Интернета намењене су да буду читљиве људима и оне су неформалне. Оне често укључују многа од следећих правила и проширења синтаксе:

Опциони ајтеми обухваћене угластим заградама. Нпр. [<ајтем-x>]
Ајтеми који се понављају нула или више пута су обухваћени витичастим заградама или им је додата звездица. Нпр. <реч> ::= <слово> { <слово> }
Ајтеми који се понављају једном или више пута су праћени симболом +.
Терминали се могу појавити масним словима и нетерминали у светлом тексту пре него да се користе коса слова и веће-мање заграде (‘<’, ‘>’).
Алтернативни избори у извођењу су раздвојени симболом усправна црта ‘|’. Нпр. <избор-A> | <избор-Б>
Тамо где теме треба да се групишу оне су обухваћене обичним заградама.