Wikipedija

Formalna gramatika – razlika između verzija

Interaktivna pretraga historije
← Starija izmjenaNovija izmjena →
Uklonjeni sadržaj Dodani sadržaj
VizualnoWikitekst
m Bot: formatiranje referenci
m Bot: popravljanje preusmjeravanja
Red 1:
U [[računarstvo|računarstvu]] i [[lingvistikajezikoslovlje|lingvistici]], '''formalna gramatika''', ili ponekad jednostavno '''gramatika''', jest precizan opis [[formalni jezik|formalnog jezika]] - to jest, [[skup]]a 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 ==
Red 44:
{{glavni|Chomskyjeva hijerarhija}}
 
Kada je [[Noam Chomsky]] prvi iznio formalizam generativnih gramatika 1956.<ref name="Chomsky1956"/>, klasificirao ih je u tipove danas poznate kao dio [[Chomskyjeva hijerarhija|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 neovisnanezavisna gramatika|kontekstno neovisne gramatike]] (tip 2) i [[regularna gramatika|regularne gramatike]] (tip 3). Jezici koji se mogu opisati ovakvim gramatikama se respektivno zovu [[kontekstno neovisninezavisni jezik|kontekstno neovisni jezici]] i [[regularni jezik|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 [[parsiranjeraščlanjivanje|parser]] za njih može učinkovito implementirati.<ref name="Grune&Jacobs1990">Grune, Dick & Jacobs, Ceriel H., ''Parsing Techniques—A Practical Guide'', Ellis Horwood, England, 1990.</ref> 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 parser]]a i [[LR parser]]a koji prepoznaju odgovarajuće jezike koje gramatike generiraju.
 
==== Kontekstno neovisne gramatike ====
''[[Kontekstno nezavisna gramatika|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>\left \{ a^{n}b^{n} | n \ge 1 \right \}</math> (barem jedan znak <math>a</math> nakon kojeg slijedi jednak broj znakova <math>b</math>) jest kontekstno neovisan, pošto ga generira gramatika <math>G_2</math> sa <math>N=\left \{S\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math>, pri čemu je <math>S</math> početni nezavršni znak, a produkcije su sljedeće:
Red 70:
 
=== 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 [[parsiranjeraščlanjivanje|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.
Red 80:
* ''The Language Machine'' <ref name="TheLanguageMachine">[http://languagemachine.sourceforge.net the language machine<!-- Bot generated title -->]</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>
* ''Link grammar'': oblik analitičke gramatike dizajniran za [[lingvistikajezikoslovlje|lingvistiku]] koji izvodi sintaksnu strukturu proučavanjem pozicijskih odnosa parova riječi.<ref name="Sleater&Temperly1991">Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.</ref><ref name="Sleater&Temperly1993">Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," ''Third International Workshop on Parsing Technologies'', 1993. (Revizija prethodnog papira.)</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>
 
Izvor: https://sh.wikipedia.org/wiki/Formalna_gramatika