WikiSysop: Bot: Automatski unos stranica

2021-08-20T01:28:03Z

Bot: Automatski unos stranica

Nova stranica

U [[računarstvo|računarstvu]] i [[lingvistika|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 ==

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]].

Na primjer, pretpostavimo da se [[abeceda (računarstvo)|abeceda]] sastoji od znakova <math>a</math> i <math>b</math>, da je početni znak <math>S</math>, te da imamo sljedeće produkcije:

: 1. <math>S \rightarrow aSb</math>
: 2. <math>S \rightarrow ba</math>

tada započinjemo sa početnim nezavršnim znakom <math>S</math> te odabiremo produkciju koju nad njim primjenjujemo. Ako odaberemo prvu produkciju, zamjenjujemo <math>S</math> sa <math>aSb</math> te dobivamo međuniz <math>aSb</math>. Ako opet odaberemo prvu produkciju, zamjenjujemo <math>S</math> sa <math>aSb</math> te na taj način generiramo međuniz <math>aaSbb</math>. Ovaj proces ponavljamo sve dok međuniz ne bude sadržavao samo znakove iz abecede (tj. <math>a</math> i <math>b</math>). Ako sad odaberemo drugu produkciju, zamjenjujemo <math>S</math> sa <math>ba</math> pri čemu se generira niz znakova <math>aababb</math> i generiranje je završeno. Ovaj slijed odabira produkcija možemo konciznije zapisati koristeći simbole: <math>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>\left \{ba, abab, aababb, aaababbb, ...\right \}</math>.

=== Formalna definicija ===
Klasičnu formalizaciju generativnih gramatika je prvi predložio [[Noam Chomsky]] 1950ih,<ref name="Chomsky1956">Chomsky, Noam, "Three Models for the Description of Language," ''IRE Transactions on Information Theory'', Vol. 2 No. 2, pp. 113-123, 1956.</ref><ref name="Chomsky1957">Chomsky, Noam, ''Syntactic Structures'', Mouton, The Hague, 1957.</ref>, gramatiku ''G'' čine sljedeće komponente:
* Konačan skup <math>N</math> ''[[Završni i nezavršni znakovi|nezavršnih znakova]]''
* Konačan skup <math>\Sigma</math> ''[[Završni i nezavršni znakovi|završnih znakova]]'' disjunktan sa skupom <math>N</math>
* Konačan skup <math>P</math> ''pravila produkcija'', svako oblika
:: <math>(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*} </math>
:gdje je <math>{}^{*}</math> [[Kleeneov operator]] i <math>\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>\epsilon</math>) se obično piše mjesto njega kako bi se izbjegla nejednoznačnost.
* Istaknuti znak <math>S \in N</math> je ''početni nezavršni znak''.
Obično se takva formalna gramatika <math>G</math> konciznije zapiše kao uređena četvorka <math>(N, \Sigma, P, S)</math>.

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

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

: 1. <math>S \rightarrow aBSc</math>
: 2. <math>S \rightarrow abc</math>
: 3. <math>Ba \rightarrow aB</math>
: 4. <math>Bb \rightarrow bb </math>

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>
* <math>\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> \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>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>L = \left \{ a^{n}b^{n}c^{n} | n \ge 1 \right \}</math> gdje <math>a^{n}</math> označava niz znakova koji se sastoji od ''n'' uzastopnih znakova <math>a</math>. Dakle, jezik ove gramatike je skup svih nizova znakova koji se sastoje od jednog ili više znakova <math>a</math>, nakon kojih slijedi jednak broj znakova <math>b</math>, nakon kojih slijedi jednak broj znakova <math>c</math>.

=== Chomskyjeva hijerarhija ===
{{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 neovisna gramatika|kontekstno neovisne gramatike]] (tip 2) i [[regularna gramatika|regularne gramatike]] (tip 3). Jezici koji se mogu opisati ovakvim gramatikama se respektivno zovu [[kontekstno neovisni 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 [[parsiranje|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 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:

: 1. <math>S \rightarrow aSb</math>
: 2. <math>S \rightarrow ab</math>

Kontekstno neovisni jezik može biti prepoznat u vremenu <math>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>O(n^3)</math> vremenu pripada li niz jeziku, pri čemu je <math>n</math> duljina niza znakova.<ref name="Earley1970">Earley, Jay, "An Efficient Context-Free Parsing Algorithm," ''Communications of the ACM'', Vol. 13 No. 2, pp. 94-102, February 1970.</ref> Nadalje, neki važni podskupovi kontekstno neovisnih jezika mogu biti prepoznati u linearnom vremenu koristeći neke druge algoritme.

==== Regularne gramatike ====
U [[regularna gramatika|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>\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>\left \{ a^{n}b^{m} | m,n \ge 1 \right \}</math> (barem jedan znak <math>a</math> nakon kojeg slijed barem jedan znak <math>b</math>, iako ne nužno isti broj puta) jest, pošto ga generira gramatika <math>G_3</math> sa <math>N=\left \{S, A,B\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math>, pri čemu je <math>S</math> početni nezavršni znak, a skup produkcija je sljedeći:

: 1. <math>S \rightarrow aA</math>
: 2. <math>A \rightarrow aA</math>
: 3. <math>A \rightarrow bB</math>
: 4. <math>B \rightarrow bB</math>
: 5. <math>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 [[regularni izraz|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 [[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.

== 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'' <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>
* ''Link grammar'': oblik analitičke gramatike dizajniran za [[lingvistika|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>

== Izvori ==

{{izvori}}

== Vanjske poveznice ==

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

{{Formalni jezici i gramatike}}
[[Kategorija:Formalni jezici]]

Formalna gramatika - Povijest promjena

WikiSysop: Bot: Automatski unos stranica