Formalna gramatika – razlika između verzija

 

== 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 gramatika|nejednoznačna]].

 

Neki primjeri generiranih nizova znakova u <math>\boldsymbol{L}(G)</math> su:

* <math>\boldsymbol{S} \Rightarrow_2 \boldsymbol{abc}</math>

* <math>\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>

=== 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 [[parsiranje|parsiranja]]. Neki oblici tako razvijenih gramatika uključuju:

* ''Tree-adjoining'' gramatike povećavaju ekspresivnost konvencionalnih generativnih gramatika dozvoljavanjem pravilima prepisivanja da operiraju na [[stablo parsiranja|stablima parsiranja]] mjesto na običnim nizovima znakova. <ref name="JoshiEtAl1975">Joshi, Aravind K., ''et al.'', "Tree Adjunct Grammars," ''Journal of Computer Systems Science'', Vol. 10 No. 1, pp. 136-163, 1975.</ref>

* Afiksne gramatike<ref name="Koster1971">Koster , Cornelis H. A., "Affix Grammars," in ''ALGOL 68 Implementation'', North Holland Publishing Company, Amsterdam, p. 95-109, 1971.</ref> i atributne gramatike<ref name="Knuth1968">Knuth, Donald E., "Semantics of Context-Free Languages," ''Mathematical Systems Theory'', Vol. 2 No. 2, pp. 127-145, 1968.</ref><ref name="Knuth1971">Knuth, Donald E., "Semantics of Context-Free Languages (correction)," ''Mathematical Systems Theory'', Vol. 5 No. 1, pp 95-96, 1971.</ref> 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.

 

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'' <ref name="TheLanguageMachine">http://languagemachine.sourceforge.net</ref> 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 [http://languagemachine.sourceforge.net/picturebook.html 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.<ref name="Birman1970">Birman, Alexander, ''The TMG Recognition Schema'', Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.</ref>

* ''Parsing expression grammar'' (PEG): poopćenje TDPL-a dizajnirano da zadovolji praktične potrebe ekspresivnosti [[programski jezik|programskih jezika]] i pisaca [[jezični procesor|jezičnih procesora]].<ref>Ford, Bryan, ''Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking'', Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.</ref>

 

{{reflist}}

 

* [http://www.formalgrammar.tk/ Godišnja konferencija o formalnim gramatikama]