Formalna gramatika

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Preferences-system.svg Ovom članku je potrebna jezička standardizacija, preuređivanje ili reorganizacija.
Pogledajte kako poboljšati članak, kliknite na link uredi i doradite članak vodeći računa o standardima Wikipedije.
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

Formalna gramatika je gramatika koja se može zapisati i jednoznačno tumačiti.

Podjela[uredi | uredi izvor]

Jezik je skup svih rečenica koje tvori određena gramatika. Gramatiku čine:

  • konačan skup terminalnih simbola
  • konačan skup neterminalnih simbola
  • produkcije za svaki neterminalni simbol
  • startni neterminalni simbol

Terminalni simboli, kraće terminali ili tokeni su zapravo ono što obično nazivamo riječima. Zovu se terminali, jer se analiza na njima završava, tj. ne rastavljaju se za potrebe analize.

Neterminalni simboli, tzv. neterminali, su apstraktne oznake za gramatičke konstrukcije. Oni se mogu razdvojiti analizom u zavisnosti od produkcija gramatike.

Produkcije su usmjerene relacije između stringova sačinjenih od terminalnih i neterminalnih simbola. Razlikuje im se desna strana od lijeve. Lijeva strana može da se predstavi desnom, tj. neki slučaj može da se sažme u ono na lijevoj strani.

Startni simbol je neterminal koji predstavlja čitav jezik generisan gramatikom. Od njega polazi analiza. Ako neka rečenica može da se redukuje u ovaj neterminal primjenom produkcija gramatike, onda se kaže da gramatika prihvata ovu rečenicu, da je napisana pravilno po datoj gramatici, ili da pripada jeziku koji tvori gramatika.

Vrste formalne gramatike[uredi | uredi izvor]

Postoje tri vrste formalnih gramatika, a među njima vlada relacija poretka:

  • Kontekstno zavisni jezici su nadskup kontekstno nezavisnih jezika. Pojam "kontekstno zavisno" se upotrebljava da opiše slučajeve kada neka riječ u rečenici ima drugačija značenja u zavisnosti od kombinacije ostalih riječi i njene pozicije u rečenici. Ovo je slučaj sa jezicima koji koriste ljudi za komunikaciju.
  • Kontekstno nezavisni jezici su generisani kontekstno slobodnim gramatikama. U rečenicama ove gramatike značenje neke riječi ne zavisi od konteksta u kom su upotrebljene.
  • Regularni jezici tvoreni su regularnim gramatikama. Oni su podskup kontekstno nezavisnih jezika.

Praktična primjena[uredi | uredi izvor]

U kompjuterskim jezicima obično figuriše kontekstno slobodna gramatika (engl. Context free grammar - CFG) koja kreira odgovarajuće kontekstno nezavisne jezike. Programski jezik C, neterminal koji predstavlja čitav jezik generisan gramatikom, je na primjer kontekstno zavistan, ali se predstavlja kao kontekstno nezavistan s tim da se kontekstna zavisnost rješava u pristupu izradi skenera. Skener je dio prevodioca koji program napisan u programskom jeziku razbije na tokene, i sastavni je dio Front-end prevodioca. Skener emituje tokene parseru kao tok (engl. stream) vezujući za svaki semantičku vrijednost.

Semantička vrijednost je pridružena tokenu i služi da prenese dodatne informacije bitne za rad programa. Na primjer 2435 je broj i token za njega bio bi recimo NUMBER. Međutim kada bi smo utvrdili da je recimo

a = 2435;

ispravno tj. pripada nekom jeziku, bilo bi nam potrebno da baratamo sa konkretnom (semantičkom) vrijednošću koja je predstavljena tokenom. Prenos semantičke vrijednosti se rješava različito a poznat način da se definiše tip za ovu vrijednost u obliku unije (union za jezik C) i jedna globalna promenljiva ovog tipa. Onda skener upisuje u nju semantičku vrijednost, a parser čita i stavlja privremeno na jedan red dok ne prihvati traženi neterminal. Prilikom prihvatanja datog neterminala izvršava se akcija koja treba konačno da odradi posao vezan za prepoznavanje određenog neterminala, i eventualna trajnija skladištenja određenih semantičkih vrijednosti (npr. liste). I naravno na samom kraju generiše se semantička vrijednost za dati neterminal koja će biti vraćena na mjesto sa koga je rekurzivno pozvana tekuća produkcija.


Regularne gramatike se međutim najčešće koriste. Kada se koristiti neki šel (shell), npr. u DOS-u standardni COMMAND.COM i ako je potrebno da se vide svi fajlovi koje je moguće izvršiti, onda se koristi:

DIR *.EXE

Zadati parametar *.EXE je zapravo prihvaćen kao regularni izraz (engl. Regular Expression - RE). Znakovi zvjezda mijenjaju bilo koju kombinaciju sastavljenu iz karaktera dozvoljenih za kreiranje imena.

Također pogledajte[uredi | uredi izvor]