Formalna gramatika

U računarstvu i lingvistici, formalna gramatika, ili ponekad jednostavno gramatika, jest precizan opis formalnog jezika - to jest, skupa nizova znakova (stringova). Dvije glavne kategorije formalnih gramatika su generativne gramatike, koje predstavljaju skup pravila za generiranje nizova znakova jezika, te analitičke gramatike, koje predstavljaju skup pravila za analizu pripadnosti niza znakova jeziku. Ukratko, analitička gramatika opisuje kako prepoznati kad je niz znakova u skupu, dok generativna gramatika opisuje kako pisati samo one nizove znakova u skupu.

Generativne gramatike

Generativna gramatika se sastoji od skupa pravila za transformiranje nizova znakova koje zovemo produkcije. Prilikom generiranja niza znakova u jeziku započinjemo sa nizom znakova koji se sastoji od samo jednog početnog znaka, i potom uzastopno primjenjujemo pravila (bilo koji broj puta, u bilo kojem redoslijedu) u svrhu prepisivanja (engl. rewrite) niza znakova. Jezik se sastoji od svih nizova znakova koji mogu biti generirani na ovaj način. Bilo koji pojedinačni slijed valjanih izbora pravila odabranih za vrijeme procesa prepisivanja daje neki pojedinačni niz znakova jezika, i ukoliko postoji više načina za generiranje jednog niza znakova, tada za gramatiku kažemo da je nejednoznačna.

Na primjer, pretpostavimo da se abeceda sastoji od znakova [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math], da je početni znak [math]\displaystyle{ S }[/math], te da imamo sljedeće produkcije:

1. [math]\displaystyle{ S \rightarrow aSb }[/math]

2. [math]\displaystyle{ S \rightarrow ba }[/math]

tada započinjemo sa početnim nezavršnim znakom [math]\displaystyle{ S }[/math] te odabiremo produkciju koju nad njim primjenjujemo. Ako odaberemo prvu produkciju, zamjenjujemo [math]\displaystyle{ S }[/math] sa [math]\displaystyle{ aSb }[/math] te dobivamo međuniz [math]\displaystyle{ aSb }[/math]. Ako opet odaberemo prvu produkciju, zamjenjujemo [math]\displaystyle{ S }[/math] sa [math]\displaystyle{ aSb }[/math] te na taj način generiramo međuniz [math]\displaystyle{ aaSbb }[/math]. Ovaj proces ponavljamo sve dok međuniz ne bude sadržavao samo znakove iz abecede (tj. [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math]). Ako sad odaberemo drugu produkciju, zamjenjujemo [math]\displaystyle{ S }[/math] sa [math]\displaystyle{ ba }[/math] pri čemu se generira niz znakova [math]\displaystyle{ aababb }[/math] i generiranje je završeno. Ovaj slijed odabira produkcija možemo konciznije zapisati koristeći simbole: [math]\displaystyle{ S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb }[/math]. Jezik ove gramatike je skup svih nizova znakova koji mogu biti generirani koristeći sljedeći proces: [math]\displaystyle{ \left \{ba, abab, aababb, aaababbb, ...\right \} }[/math].

Formalna definicija

Klasičnu formalizaciju generativnih gramatika je prvi predložio Noam Chomsky 1950ih,, gramatiku G čine sljedeće komponente:

• Konačan skup [math]\displaystyle{ N }[/math] nezavršnih znakova
• Konačan skup [math]\displaystyle{ \Sigma }[/math] završnih znakova disjunktan sa skupom [math]\displaystyle{ N }[/math]
• Konačan skup [math]\displaystyle{ P }[/math] pravila produkcija, svako oblika

[math]\displaystyle{ (\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*} }[/math]

gdje je [math]\displaystyle{ {}^{*} }[/math] Kleeneov operator i [math]\displaystyle{ \cup }[/math] označava uniju skupova. To jest, svaka produkcija preslikava jedan niz znakova u drugi, gdje prvi niz znakova sadrži barem jedan nezavršni znak. U slučaju da je drugi niz znakova prazni niz - tj. ne sadrži nijedan znak - simbol iz grčke abecede epsilon ([math]\displaystyle{ \epsilon }[/math]) se obično piše mjesto njega kako bi se izbjegla nejednoznačnost.

• Istaknuti znak [math]\displaystyle{ S \in N }[/math] je početni nezavršni znak.

Obično se takva formalna gramatika [math]\displaystyle{ G }[/math] konciznije zapiše kao uređena četvorka [math]\displaystyle{ (N, \Sigma, P, S) }[/math].

Jezik formalne gramatike [math]\displaystyle{ G = (N, \Sigma, P, S) }[/math], označen sa [math]\displaystyle{ \boldsymbol{L}(G) }[/math], je definiran kao skup svih onih nizova znakova nad [math]\displaystyle{ \Sigma }[/math] koji mogu biti generirani počevši od početnog nezavršnog znaka [math]\displaystyle{ S }[/math] i potom primjenjujući produkcije u [math]\displaystyle{ P }[/math] sve dok nijedan nezavršni znak nije prisutan u međunizu.

Primjer

Promatrajmo gramatiku [math]\displaystyle{ G }[/math] gdje je [math]\displaystyle{ N = \left \{S, B\right \} }[/math], [math]\displaystyle{ \Sigma = \left \{a, b, c\right \} }[/math], [math]\displaystyle{ S }[/math] je početni nezavršni znak, i [math]\displaystyle{ P }[/math] se sastoji od sljedećih produkcija:

1. [math]\displaystyle{ S \rightarrow aBSc }[/math]

2. [math]\displaystyle{ S \rightarrow abc }[/math]

3. [math]\displaystyle{ Ba \rightarrow aB }[/math]

4. [math]\displaystyle{ Bb \rightarrow bb }[/math]

Neki primjeri generiranih nizova znakova u [math]\displaystyle{ \boldsymbol{L}(G) }[/math] su:

• [math]\displaystyle{ \boldsymbol{S} \Rightarrow_2 \boldsymbol{abc} }[/math]
• [math]\displaystyle{ \boldsymbol{S} \Rightarrow_1 aB\boldsymbol{S}c \Rightarrow_2 a\boldsymbol{Ba}bcc \Rightarrow_3 aa\boldsymbol{Bb}cc \Rightarrow_4 aa\boldsymbol{b}bcc }[/math]
• [math]\displaystyle{ \boldsymbol{S} \Rightarrow_1 aB\boldsymbol{S}c \Rightarrow_1 aBaB\boldsymbol{S}cc \Rightarrow_2 a\boldsymbol{Ba}Babccc \Rightarrow_3 aaB\boldsymbol{Ba}bccc\Rightarrow_3 aa\boldsymbol{Ba}Bbccc }[/math][math]\displaystyle{ \Rightarrow_3 aaaB\boldsymbol{Bb}ccc \Rightarrow_4 aaa\boldsymbol{Bb}bccc \Rightarrow_4 aaa\boldsymbol{b}bbccc }[/math]

(Bilješka o korištenoj notaciji: [math]\displaystyle{ L \Rightarrow_i R }[/math] čitaj kao "L generira R korištenjem produkcije i" i generirani dio međuniza je svaki put masno otisnut (podebljan).)

Ova gramatika definira jezik [math]\displaystyle{ L = \left \{ a^{n}b^{n}c^{n} | n \ge 1 \right \} }[/math] gdje [math]\displaystyle{ a^{n} }[/math] označava niz znakova koji se sastoji od n uzastopnih znakova [math]\displaystyle{ a }[/math]. Dakle, jezik ove gramatike je skup svih nizova znakova koji se sastoje od jednog ili više znakova [math]\displaystyle{ a }[/math], nakon kojih slijedi jednak broj znakova [math]\displaystyle{ b }[/math], nakon kojih slijedi jednak broj znakova [math]\displaystyle{ c }[/math].

Chomskyjeva hijerarhija

Podrobniji članak o temi: Chomskyjeva hijerarhija

Kada je Noam Chomsky prvi iznio formalizam generativnih gramatika 1956., klasificirao ih je u tipove danas poznate kao dio Chomskyjeve hijerarhije. Razlika između ovih tipova jest što imaju povećavajuće stroga produkcijska pravila i stoga mogu izraziti sve manje formalnih jezika. Dva važna tipa su kontekstno neovisne gramatike (tip 2) i regularne gramatike (tip 3). Jezici koji se mogu opisati ovakvim gramatikama se respektivno zovu kontekstno neovisni jezici i regularni jezici. Premda nešto manje moćne od gramatike neograničenih produkcija (tip 0), koje mogu izraziti bilo koji jezik koji prihvaća Turingov stroj, ova dva ograničena tipa gramatika su najčešće korištena jer se parser za njih može učinkovito implementirati. Na primjer, sve regularne jezike može prepoznati konačni automat, a za korisne podskupove kontekstno neovisnih gramatika postoje dobro poznati algoritmi za generiranje učinkovitih LL parsera i LR parsera koji prepoznaju odgovarajuće jezike koje gramatike generiraju.

Kontekstno neovisne gramatike

Kontekstno neovisna gramatika je gramatika u kojoj se lijeva strana produkcije sastoji samo od jednog nezavršnog znaka. Ovo ograničenje je netrivijalno; kontekstno neovisna gramatika ne može generirati sve jezike. One koje može zovemo kontekstno neovisni jezici.

Jezik definiran u gornjem primjeru nije kontekstno neovisan i ovo se može strogo dokazati koristeći svojstvo napuhavanja za kontekstno neovisne jezike, no npr. jezik [math]\displaystyle{ \left \{ a^{n}b^{n} | n \ge 1 \right \} }[/math] (barem jedan znak [math]\displaystyle{ a }[/math] nakon kojeg slijedi jednak broj znakova [math]\displaystyle{ b }[/math]) jest kontekstno neovisan, pošto ga generira gramatika [math]\displaystyle{ G_2 }[/math] sa [math]\displaystyle{ N=\left \{S\right \} }[/math], [math]\displaystyle{ \Sigma=\left \{a,b\right \} }[/math], pri čemu je [math]\displaystyle{ S }[/math] početni nezavršni znak, a produkcije su sljedeće:

1. [math]\displaystyle{ S \rightarrow aSb }[/math]

2. [math]\displaystyle{ S \rightarrow ab }[/math]

Kontekstno neovisni jezik može biti prepoznat u vremenu [math]\displaystyle{ O(n^3) }[/math] koristeći algoritme kao što je Earleyev algoritam. Drugim riječima, za svaki kontekstno neovisni jezik se može izgraditi stroj koji na ulazu prima neki niz znakova i određuje u [math]\displaystyle{ O(n^3) }[/math] vremenu pripada li niz jeziku, pri čemu je [math]\displaystyle{ n }[/math] duljina niza znakova. Nadalje, neki važni podskupovi kontekstno neovisnih jezika mogu biti prepoznati u linearnom vremenu koristeći neke druge algoritme.

Regularne gramatike

U regularnim gramatikama, lijeva strana produkcije je također isključivo jedan nezavršni znak, ali sad se postavlja ograničenje i na desnu stranu produkcije, na kojoj ne mora biti nijedan znak (u slučaju [math]\displaystyle{ \epsilon }[/math]-produkcije), može biti jedan završni znak, ili jedan završni znak nakon kojeg slijedi jedan nezavršni znak, i nijedan drugi niz znakova. (Ponekad se koristi nešto šira definicija po kojoj su dozvoljeni dulji nizovi završnih znakova ili samo jedan nezavršni znak i ništa drugo, i na taj se način pojednostavi označavanje iste klase jezika.)

Jezik prethodno definiran nije regularan, ali jezik [math]\displaystyle{ \left \{ a^{n}b^{m} | m,n \ge 1 \right \} }[/math] (barem jedan znak [math]\displaystyle{ a }[/math] nakon kojeg slijed barem jedan znak [math]\displaystyle{ b }[/math], iako ne nužno isti broj puta) jest, pošto ga generira gramatika [math]\displaystyle{ G_3 }[/math] sa [math]\displaystyle{ N=\left \{S, A,B\right \} }[/math], [math]\displaystyle{ \Sigma=\left \{a,b\right \} }[/math], pri čemu je [math]\displaystyle{ S }[/math] početni nezavršni znak, a skup produkcija je sljedeći:

1. [math]\displaystyle{ S \rightarrow aA }[/math]

2. [math]\displaystyle{ A \rightarrow aA }[/math]

3. [math]\displaystyle{ A \rightarrow bB }[/math]

4. [math]\displaystyle{ B \rightarrow bB }[/math]

5. [math]\displaystyle{ B \rightarrow \epsilon }[/math]

Sve jezike koje generira regularna gramatika može u linearnom vremenu prepoznati konačni automat. Iako su u praksi regularne gramatike obično opisane regularnim izrazima, neki oblici regularnih izraza korištenih u praksi ne generiraju strogo regularne jezike i zbog tih otklona ne mogu biti prepoznati u linearnom vremenu.

Drugi oblici generativnih gramatika

U posljednje su vrijeme razvijena mnoga proširenja i varijacije na izvornu Chomskyjevu hijerarhiju formalnih gramatika, kako od strane lingvista tako i od strane računalnih znanstvenika, obično u svrhu povećanja ekspresivne moći ili u svrhu lakše analize ili parsiranja. Neki oblici tako razvijenih gramatika uključuju:

• Tree-adjoining gramatike povećavaju ekspresivnost konvencionalnih generativnih gramatika dozvoljavanjem pravilima prepisivanja da operiraju na stablima parsiranja mjesto na običnim nizovima znakova.
• Afiksne gramatike i atributne gramatike dozvoljavaju pravilima prepisivanja da budu obogaćena semantičkim atributima i operacijama, što se pak pokazalo korisno za povećanje ekspresivnosti gramatike, kao i za izgradnju praktičnih alata za prevođenje (translaciju) jezika.

Analitičke gramatike

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

Alternativni pristup jest formalizacija jezika u obliku analitičke gramatike, koja pak puno izravnije korespondira strukturi i semantici parsera za jezik. Primjeri formalizama analitičkih gramatika uključuju:

• The Language Machine izravno implementira neograničene analitičke gramatike (analitičke gramatike neograničenih produkcija). Supstitucijska pravila se koriste za transformiranje ulaza i generiranje izlaza i ponašanja. Sustav također može generirati lm-dijagram koji pokazuje što se događa prilikom primjene pravila analitičke gramatike neograničenih produkcija.
• Top-down parsing language (TDPL): minimalistički formalizam analitičkih gramatika razvijen u ranim 1970im u svrhu proučavanja parsera od vrha prema dnu.
• Link grammar: oblik analitičke gramatike dizajniran za lingvistiku koji izvodi sintaksnu strukturu proučavanjem pozicijskih odnosa parova riječi.
• Parsing expression grammar (PEG): poopćenje TDPL-a dizajnirano da zadovolji praktične potrebe ekspresivnosti programskih jezika i pisaca jezičnih procesora.

Vanjske poveznice

• Godišnja konferencija o formalnim gramatikama