From Wikipedia, the free encyclopedia
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.
Generativna gramatika se sastoji od skupa pravila za transformiranje nizova znakova koje zovemo produkcije. Prilikom generiranja niza znakova u jeziku započinjemo s 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 ako 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 i , da je početni znak , te da imamo sljedeće produkcije:
tada započinjemo s početnim nezavršnim znakom te odabiremo produkciju koju nad njim primjenjujemo. Ako odaberemo prvu produkciju, zamjenjujemo sa te dobivamo međuniz . Ako opet odaberemo prvu produkciju, zamjenjujemo sa te na taj način generiramo međuniz . Ovaj proces ponavljamo sve dok međuniz ne bude sadržavao samo znakove iz abecede (tj. i ). Ako sad odaberemo drugu produkciju, zamjenjujemo sa pri čemu se generira niz znakova i generiranje je završeno. Ovaj slijed odabira produkcija možemo konciznije zapisati koristeći simbole: . Jezik ove gramatike je skup svih nizova znakova koji mogu biti generirani koristeći sljedeći proces: .
Klasičnu formalizaciju generativnih gramatika je prvi predložio Noam Chomsky 1950ih,[1][2] gramatiku G čine sljedeće komponente:
Obično se takva formalna gramatika konciznije zapiše kao uređena četvorka .
Jezik formalne gramatike , označen sa , je definiran kao skup svih onih nizova znakova nad koji mogu biti generirani počevši od početnog nezavršnog znaka i potom primjenjujući produkcije u sve dok nijedan nezavršni znak nije prisutan u međunizu.
Promatrajmo gramatiku gdje je , , je početni nezavršni znak, i se sastoji od sljedećih produkcija:
Neki primjeri generiranih nizova znakova u su:
Ova gramatika definira jezik gdje označava niz znakova koji se sastoji od n uzastopnih znakova . Dakle, jezik ove gramatike je skup svih nizova znakova koji se sastoje od jednog ili više znakova , nakon kojih slijedi jednak broj znakova , nakon kojih slijedi jednak broj znakova .
Kada je Noam Chomsky prvi iznio formalizam generativnih gramatika 1956.,[1] 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.[3] 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 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 (barem jedan znak nakon kojeg slijedi jednak broj znakova ) jest kontekstno neovisan, pošto ga generira gramatika sa , , pri čemu je početni nezavršni znak, a produkcije su sljedeće:
Kontekstno neovisni jezik može biti prepoznat u vremenu 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 vremenu pripada li niz jeziku, pri čemu je duljina niza znakova.[4] Nadalje, neki važni podskupovi kontekstno neovisnih jezika mogu biti prepoznati u linearnom vremenu koristeći neke druge algoritme.
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 -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 (barem jedan znak nakon kojeg slijed barem jedan znak , iako ne nužno isti broj puta) jest, pošto ga generira gramatika sa , , pri čemu je početni nezavršni znak, a skup produkcija je sljedeći:
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.
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:
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:
Seamless Wikipedia browsing. On steroids.