Formalna gramatika
Ovom članku potrebna je jezička standardizacija, preuređivanje ili reorganizacija. |
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
Formalna gramatika je gramatika koja se može zapisati i jednoznačno tumačiti.
Podjela
urediJezik 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
urediPostoje 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
urediU 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 naprimjer 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.