Formalna gramatika

U formalnoj teoriji jezika, u računarstvu i u lingvistici, formalna gramatika (češće samo gramatika) je precizna definicija nekog jezika, tj. skup niski nad nekom azbukom. Drugim rečima, gramatika opisuje koje od mogućih sekvenci simbola u jeziku u stvari formiraju validne reči i rečenice u tom jeziku, ali ne definiše njihovo značenje.

Za gramatiku se obično misli da generiše validne niske jezika; takođe se može koristiti kao osnova prepoznavaoca koji određuje da li neka niska pripada jeziku. Da bi se opisao takav prepoznavalac, formalna teorija jezika koristi određene formalizme, znane kao automati.

Gramatika se takođe može koristiti za analiziranje niski jezika - npr. da opiše njihovu internu strukturu. U računarstvu, ovaj proces je poznat kao parsiranje. Većina jezika ima vrlo kompozitnu semantiku, npr. značenje njihovih izvođenja je strukturirano prema njihovoj sintaksi; zbog toga, prvi korak u opisivanju značenja nekog izvođenja u jeziku jeste da se ono analizira i da se pogleda njegova analizirana forma (u računarstvu je to drvo izvođenja).

Formalna gramatika[uredi | uredi izvor]

Gramatika se sastoji od skupa pravila za dobijanje niza znakova. Prilikom generisanja niza znakova u jeziku, započinje se sa simbolom koji se naziva početni (ili startni) simbol i potom se primenjuju pravila (u bilo kojem broju, u bilo kojem redosledu). Jezik se sastoji od svih niski koje se mogu dobiti na ovaj način. Formalna gramatika je gramatika koja se može jednoznačno tumačiti. Gramatika je jednoznačna ako svako rečenična forma u toj gramatici ima tačno jedno drvo izvođenja. U suprotnom slučaju, gramatika je višeznačna (ili ambigvitetna). Višeznačnost je svojstvo gramatike, a ne jezika. Za jedan isti jezik mogu postojati i jednozanačne i višeznačne gramatike. Ukoloko su za neki jezik sve gramatike višeznačne, onda se kaže da je to inherentno višeznačan jezik, za njega nije moguće naći ekvivalentnu jednoznačnu gramatiku.

Na primer, ako imamo: azbuku (koju čine simboli a i b), S početni simbol i ako imamo pravila:

1.

S\rightarrow aSb

2.

S\rightarrow ba

tada se započinje sa početnim simbolom S i odabira se pravilo koje će dati željenu nisku. Ako se odabere prvo pravilo, zamenjuje se S sa aSb i dobija se niska aSb na koju može da se dalje primeni neko od datih pravila. Ako se opet primeni prvo pravilo, dobija se aaSbb. Ovo se ponavlja sve dok u nisci ne budu samo terminalni simboli, odnosno a i b. Ukoliko se odabere drugo pravilo - da se S zameni sa ba, tada će da se dobije niska aababb i u njoj neće biti neterminalnih simbola, pa je time završeno jedno izvođenje. Ovo izvođenje se zapisuje $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ . Na osnovu tog prethodnog procesa izvođenja zaključujemo da je jezik ove gramatike skup svih niski koje su oblika: $\left\{ba,abab,aababb,aaababbb,...\right\}$ .

Formalna definicija[uredi | uredi izvor]

Klasičnu formalizaciju formalnih gramatika prvi je predložio Naom Čomski 1950. godine. Gramatiku G čine:

Konačan skup N nezavršnih simbola
Konačan skup Σ završnih simbola (još važi da su Σ i N disjunktni skupovi)
Konačan skup Р pravila, i za svako pravilo važi: $(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}$

gde je

{}^{*}

Klinijeva zvezdica a

{}^{\cup }

skupovna unija. Dakle, svako izvođenje preslikava jedan niz znakova u drugi, pri čemu prvi niz znakova sadrži barem jedan nezavršni simbol. U slučaju da je drugi niz prazan niz, tj. ne sadrži nijedan simbol, onda se piše grčko slovo epsilon ε.

početni neterminalni simbol S.

Gramtika se formalno definiše kao uređena četvorka (N, Σ, P, S). Jezik formalne gramatike G = (N, Σ, P, S) označen sa L(G) je definisan kao skup svih onih niski završnih simbola koje mogu biti generisane od startnog nezavršnog simbola S primenom pravila P gramatike G.

Terminalni simboli, tzv. „terminali“ ili „tokeni“, su zapravo ono što obično nazivamo reč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 izvođenja gramatike.

Izvođenja su usmerene relacije između stringova sačinjenih od terminalnih i neterminalnih simbola. Razlikuje im se desna strana od leve. Leva strana može da se predstavi desnom, tj. neki slučaj može da se sažme u ono na levoj 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 primenom produkcija gramatike, onda se kaže da gramatika prihvata ovu rečenicu, da je napisana pravilno po datoj gramatici, ili da pripada jeziku kojeg generiše gramatika.

Primer[uredi | uredi izvor]

Posmatrajmo gramatiku $G$ gde $N=\left\{S,B\right\}$ , $\Sigma =\left\{a,b,c\right\}$ , $S$ je početni simbol, i $P$ je skup sledećih pravila:

1.

S\rightarrow aBSc

2.

S\rightarrow abc

3.

Ba\rightarrow aB

4.

Bb\rightarrow bb

Neki primeri generisanih niski u ${\boldsymbol {L}}(G)$ su:

${\boldsymbol {S}}\Rightarrow _{2}{\boldsymbol {abc}}$
${\boldsymbol {S}}\Rightarrow _{1}{\boldsymbol {aBSc}}\Rightarrow _{2}aB{\boldsymbol {abc}}c\Rightarrow _{3}a{\boldsymbol {aB}}bcc\Rightarrow _{4}aa{\boldsymbol {bb}}cc$
${\boldsymbol {S}}\Rightarrow _{1}{\boldsymbol {aBSc}}\Rightarrow _{1}aB{\boldsymbol {aBSc}}c\Rightarrow _{2}aBaB{\boldsymbol {abc}}cc\Rightarrow _{3}a{\boldsymbol {aB}}Babccc\Rightarrow _{3}aaB{\boldsymbol {aB}}bccc$ $\Rightarrow _{3}aa{\boldsymbol {aB}}Bbccc\Rightarrow _{4}aaaB{\boldsymbol {bb}}ccc\Rightarrow _{4}aaa{\boldsymbol {bb}}bccc$

(napomena:

L\Rightarrow _{i}R

čitamo: "L generiše R korišćenjem pravila pod rednim brojem i" i generisani deo u međunisci je svaki put podebljan.)

Ova gramatika definiše jezik $L=\left\{a^{n}b^{n}c^{n}|n\geq 1\right\}$ gde $a^{n}$ podrazumeva nisku koja ima n uzastopnih pojavljivanja simbola $a$ -ova. Dakle, jezik ove gramatike je skup svih nizova simbola koji se sastoje od jednog ili više simbola $a$ , nakon kojih sledi isto toliko pojavljivanja simbola $b$ , za kojim sledi toliko pojavljivanja simbola $c$ .

Hijerarhija Čomskog[uredi | uredi izvor]

Kada je Noam Čomski izneo formalizam fomalnih gramatika 1956. godine, klasifikovao ih je u tipove danas znano kao hijerarhija Čomskog. Postoje sledeća podela:

Desno linearna (regularna) gramatika (jezik opisan ovom gramatikom je desno linearan ili regularan jezik)
Konteksno slobodna gramatika (jezik opisan ovom gramatikom je konteksno slobodan jezik)
Konteksno osetljiva gramatika (jezik opisan ovom gramatikom je konteksno osetljiv jezik)
Gramatika bez ograničenja, opšta (jezik opisan ovom gramatikom je jezik bez ograničenja)

Razlika između ovih tipova jeste u tome što neki tipovi gramatika imaju stroža pravila pa mogu izraziti i manje formalne jezike. Dva važna tipa su konteksno slobodne gramatike (tip 2) i regularne gramatike (tip 3). Jezici koji se mogu opisati ovakvim gramatikama se zovu konteksno slobodni jezici i regularni jezici. Iako nešto manje moćne od gramatika bez ograničenja (tip 0), koje mogu izraziti bilo koji jezik koji prihvata Tjuringova mašina, ova dva ograničena tipa gramatika su najčešće korištena jer se parser za njih može vrlo uspešno implementirati. Na primer, sve regularne jezike može prepoznati konačni automat, a za korisne podskupove konteksno slobodnih gramatika postoje dobro poznati algoritmi za generisanje efikasnih LL analizatora i LR analizatora koji prepoznavaju odgovarajuće jezike koje gramatika generiše.

Kontekstno slobodna gramatika[uredi | uredi izvor]

Kontekstno slobodna gramatika je gramatika u kojoj se leva strana pravila sastoji samo od jednog neterminalnog simbola. Ovo ograničenje nije netrivijalno; konteksno slobodna gramatika ne može generisati sve jezike. One koje može zovemo konteksno slobodnim jezicima. Jezik definisan u prethodnom primeru nije konteksno slobodan, i to se može strogo dokazati korištenjem leme o razrastanju za konteksno slobodne jezike, ali, na primer jezik $\left\{a^{n}b^{n}|n\geq 1\right\}$ (tj. bar jedan znak $a$ nakon koga sledi isto toliko znakova $b$ ) jeste konteksno slobodan, pošto ga generiše gramatika $G_{2}$ sa $N=\left\{S\right\}$ , $\Sigma =\left\{a,b\right\}$ , pri čemu je $S$ početni nezavršni simbol, a pravila su:

1.

S\rightarrow aSb

2.

S\rightarrow ab

Konteksno slobodan jezik može biti prepoznat u vremenu $O(n^{3})$ koristeći algoritme kao što je Ojlerov algoritam. Drugim rečima, za svaki konteksno slobodan jezik se može izgraditi mašina koja na ulazu prima neki niz znakova i određuje u $O(n^{3})$ vremenu da li niska pripada jeziku, pri čemu je $n$ dužina niza simbola za tu nisku. Nadalje, neki važni podskupovi kontekstno slobodnih jezika mogu biti prepoznati u linearnom vremenu koristeći druge algoritme.

Drugi oblici generativnih gramatika[uredi | uredi izvor]

U poslednje vreme su razvijena mnoga proširenja i varijacije na izvornu hijerarhiju Noama Čomskog za formalne gramatike, kako od strane lingvista tako i od strane poznavaoca računara, obično u svrhu povećanja ekspresivne moći ili u svrhu lakše analize ili parsiranja. Neki oblici tako razvijenih gramatika uključuju:

Gramatike sa pridruženim drvetom su gramatike koje povećavaju ekspresivnost konvencionalnih generativnih gramatika dozvoljavanjem pravilima prepisivanja da operišu na stablima parsiranja umesto na običnim nizovima znakova.
afiksne gramatike dozvoljavaju pravilima prepisivanja da budu obogaćena semantičkim atributima i operacijama, što se pokazalo korisno za povećanje ekspresivnosti gramatike, kao i za izgradnju praktičnih alata za prevođenje jezika.

Analitička gramatika[uredi | uredi izvor]

Iako su algoritmi parsiranja jako dugo proučavani i njihova svojstva dobro shvaćena i dokumentovana u ogromnom pisanom opusu, većina njih podrazumeva da je jezik koji se parsira inicijalno opisan preko generativne formalne gramatike, te da je cilj generatora parsera transformisati tu generativnu gramatiku u parser. Strogo govoreći, generativna gramatika ni na koji način ne odgovara algoritmu korištenom za parsiranje jezika, i različiti algoritmi postavljaju različita ograničenja na oblik pravila koje shvataju kao dobro oblikovane.

Alternativni pristup je formalizacija jezika u obliku analitičke gramatike, koja pak znatno više odgovara strukturi i semantici parsera za jezik. Primeri formalizma analitičkih gramatika uključuju:

Mašina za jezik - direktno implementira neograničene analitičke gramatike (analitičke gramatike neograničenih pravila). Pravila supstitucije se koriste za transformisanje ulaza i generisanje izlaza i ponašanja. Sistem takođe može generisati Im - dijagram koji pokazuje šta se dešava prilikom primene pravila analitičke gramatike neograničenih pravila.
Sintaksičku analizu naniže (engl. Top-down parsing language, TDPL): minimalistički formalizam analitičkih gramatika razvijen u ranim 1970im u svrhu proučavanja parsera od vrha prema dnu.
Gramatika veze: oblik analitičke gramatike dizajniran za lingvistiku koji izvodi sintaksnu strukturu proučavanjem pozicijskih odnosa parova reči.
Sintaksno izraženu gramatiku (eng. Parsing expression grammar, PEG): uopštenje TDPL-a dizajnirano da zadovolji praktične potrebe ekspresivnosti programskih jezika i pisaca kompilatora.

Praktična primena[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. Na primer, programski jezik C, neterminal koji predstavlja čitav jezik generisan gramatikom, je kontekstno zavisan ali se predstavlja kao kontekstno nezavisan s tim da se kontekstna zavisnost rešava u pristupu izradi skenera. Skener je deo prevodioca koji program napisan u programskom jeziku razbija na terminalne simbole, i sastavni je deo front-end prevodioca. Skener emituje terminalne simbole parseru kao tok (engl. stream) vezujući za svaki semantičku vrednost.

Semantička vrednost je pridružena terminalnom simbolu i služi da prenese dodatne informacije bitne za rad programa. Na primer 2435 je broj i token za njega bi npr. bio BROJ. Međutim kada bismo utvrdili da je npr.

a = 2435;

ispravno, tj. da pripada nekom jeziku, bilo bi nam potrebno da baratamo sa konkretnom (semantičkom) vrednošću koja je predstavljena tokenom. Prenos semantičke vrednosti se rešava različito a postoji način da se definiše tip za ovu vrednost u obliku unije i jedna globalna promenljiva ovog tipa. Onda skener upisuje u nju semantičku vrednost, 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 vrednosti (npr. liste). I naravno na samom kraju generiše se semantička vrednost za dati neterminal koja će biti vraćena na mesto sa koga je rekurzivno pozvana tekuća produkcija.

Regularne gramatike se najčešće koriste. Npr. kada se koristi neki ljuska (npr. ljuska Beš u Juniksu ili COMMAND.COM u Dosu) 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. Znak zvezda zamenjuje bilo koju kombinaciju sastavljenu iz karaktera dozvoljenih za kreiranje imena.