Pređi na sadržaj

Bakus–Naurova forma

S Vikipedije, slobodne enciklopedije

U računarstvu, Bakus–Naurova forma (Bakusova notacija ili BNF) je meta jezik koji se koristi za izražavanje kontekstno slobodnih gramatika: to je formalni način da se opišu formalni jezici.

Džon Bakus i Piter Naur, su razvili kontekstno slobodnu gramatiku da bi definisali sintaksu programskih jezika, koristeći dve grupe pravila: tj, leksička pravila i sintaksička pravila.

BNF je širom korišćena notacija za gramatike programskih jezika, lista instrukcija i komunikacijskih protokola, kao i notacija za predstavljanje gramatika svakodnevnog jezika. U Bakusovoj notaciji sintaksa programskog jezika opisuje se pomoću konačnog skupa metalingvističkih formula (MLF).

Postoje mnoga proširenja i varijante BNF-a.

Istorija

[uredi | uredi izvor]

Džon Bakus je stvorio notaciju da bi izrazio gramatiku ALGOL-a. Na Prvom svetskom računarskom kongresu, koji je održan u Parizu 1959. godine, Bakus je predstavio Sintaksu i semantiku predloženog internacionalnog algebarskog jezika na ACM-GAMM konferenciji u Cirihu, formalni opis IAL-a, koji je kasnije nazvan ALGOL 58. Formalni jezik koji je on predstavio, zasnovan je na sistemu izvođenja Emila Posta.

Generativne gramatike bile su aktivni predmet matematičke studije, kao na primer Noama Čomskog, koji ih je koristio u gramatici svakodnevnog jezika.

Piter Naur, (ALGOL 60, 1963) definisao je Bakusovu notaciju kao Bakusovu normalnu formu i pojednostavio je da bi umanjio klasu korišćenih karaktera i, na predlog Donalda Knuta, njegovo ime je dodato kao priznanje njegovog doprinosa. Knut je demantovao njegovo prvobitno zamenjivanje N za Normalna, govoreći da BNF nije normalna forma u bilo kom smislu.

Gramatike BNF-a imaju značajne sličnosti sa pravilima Paninijeve gramatike, tako da se notacija često tumači kao Panini-Bakus forma.

Uvod

[uredi | uredi izvor]

U BNF-u se koriste sledeće konvencije za zapisivanje pravila gramatike:

a. umesto simbola -> koristi se simbol ::=;
b. pomoćni simboli se navode među zagradama < i >;
c. vertikalna crta (izbor) razdvaja desne strane pravila koje odgovaraju istom simbolu sa leve strane pravila;
d. prazna niska ε se zapisuje kao <empty>.

Simboli koji se nikada ne pojavljuju na levoj strani pravila su terminali.

Primer

[uredi | uredi izvor]

Kao primer, uzmimo u obzir ovu BNF za poštansku adresu u SAD: 

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

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

Ovo se prevodi na engleski kao:

  • Poštanska adresa koja se sastoji od dela za ime, praćenog delom za ulicu, praćenog delom za poštanski broj.
  • Deo za ime se sastoji ili od ličnog dela praćenog prezimenom, praćenog opcionim “jr. delom” (Jr., Sr. ili dinastijskim brojem) i krajem linije, ili od ličnog dela praćenog delom za ime (Ovo pravilo prikazuje upotrebu rekurzije u BNF-u pokrivajući slučaj kada ljudi koriste višestruka imena i srednja imena i/ili inicijale).
  • Ličnog dela koji se sastoji ili od imena ili od inicijala praćenog tačkom.
  • Ulica se sastoji od opcionog opisa stana, praćenog kućnim brojem, praćenog ulicom, praćenog krajem linije.
  • Zip deo se sastoji od imena grada, praćenog zarezom, praćenog državnim brojem, praćenog poštanskim brojem, praćenog krajem linije.

Valja primetiti da mnoge stvari (kao što su format imena, opisivanje stana, poštanskog broja i rimskih cifara) su ovde ostavljene neodređene.

Ako je potrebno, ona mogu biti opisana koristeći dodatna pravila BNF-a.

Dalja objašnjenja

[uredi | uredi izvor]

Sama sintaksa BNF-a može biti predstavljena BNF-om kao sledeće: 

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

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

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

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

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

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

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

Ovo simulira da belina nije potrebna za odgovarajuće tumačenje. <EOL> predstavlja odgovarajući opis kraja linije (u ASCII zapisu, povratak na početak reda i/ili novi red, zavisno od operativnog sistema). <ime-pravila> i <tekst> moraju da budu zamenjeni deklarisanim imenom/oznakom pravila ili doslovnim tekstom.

Varijante

[uredi | uredi izvor]

Postoje mnoge varijante i proširenja BNF-a, ili zbog jednostavnosti i sažetosti ili da je prilagode određenom korišćenju. Jedno od zajedničkih obeležja mnogih varijanti je upotreba regularnog izraza, ponavljanje operacija * i +. Proširena BNF je jedna od čestih. U stvari, primer iznad nije čista forma, napravljena za izveštaj ALGOL-a 60. Obeležavanje zagrada "[]" uvedeno je par godina kasnije u IBM-ovoj PL/I, definiciji, ali je danas širom prepoznatljiva.

Tumačenje izraza gramatika nadograđuje se na BNF i na notacije regularnog izraza da bi se formirala alternativna klasa formalnih gramatika, koja je suštinski analitička pre nego generativna po karakteru.

Mnoge BNF specifikacije koje su danas dostupne putem Interneta namenjene su da budu čitljive ljudima i one su neformalne. One često uključuju mnoga od sledećih pravila i proširenja sintakse:

  • Opcioni ajtemi obuhvaćene uglastim zagradama. Npr. [<ajtem-x>]
  • Ajtemi koji se ponavljaju nula ili više puta su obuhvaćeni vitičastim zagradama ili im je dodata zvezdica. Npr. <reč> ::= <slovo> { <slovo> }
  • Ajtemi koji se ponavljaju jednom ili više puta su praćeni simbolom +.
  • Terminali se mogu pojaviti masnim slovima i neterminali u svetlom tekstu pre nego da se koriste kosa slova i veće-manje zagrade (‘<’, ‘>’).
  • Alternativni izbori u izvođenju su razdvojeni simbolom uspravna crta ‘|’. Npr. <izbor-A> | <izbor-B>
  • Tamo gde teme treba da se grupišu one su obuhvaćene običnim zagradama.

Vidi još

[uredi | uredi izvor]

Spoljašnje veze

[uredi | uredi izvor]

Korisni strani linkovi

[uredi | uredi izvor]
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Бакус–Наурова_форма&oldid=26817591”