Predgovor

Prošlo je četvrt stoljeća otkad sam prvi put saznao da je sve što nas okružuje jezik! Da, upravo tako. Naime, prema definiciji formalnog jezika, to je bilo koji skup, pa i prazan skup, a sve čime smo okruženi jest dio nekog skupa, a koliko tek ima praznih skupova! (Ima li?)

Teorija formalnih jezika rodena je u drugoj polovici pedesetih godina dvadesetoga stoljeća u ranim radovima Noama Chomskog. Temeljila se na odgovarajućem modelu prirodnih jezika, kao što je npr. engleski.

Uskoro potom veliki poticaj daljnjem razvoju teorije formalnih jezika dala je uporaba beskontekstnih gramatika i onoga što se danas naziva "Backus-Naurova forma" (BNF). Prvi je put bila upotrijebljena u defininiciji jezika ALGOL 60, 1963. godine.

Na početku se teorija formalnih jezika više bavila specificiranjem skupova i odredenim formalizmima, kao što su regularni izrazi i gramatike, beskontekstne gramatike itd.

Daljnji razvoj teorije formalnih jezika išao je u nekoliko pravaca. Osim dijela teorije koji je bio bliži matematici, sve više se razvijala teorija koja je nalazila primjene u računarskim znanostima:

Danas je značenje teorije formalnih jezika višestruko. Fundamentalni koncepti teorije formalnih jezika nalaze svoju primjenu u nekoliko područja; osim u računarskim znanostima još i u umjetnoj inteligenciji (razumijevanju prirodnih jezika), prepoznavanju oblika, kemiji, biologiji itd.

Poslije četvrt stoljeća bavljenja teorijom formalnih jezika i njezinom praktičnom primjenom u definiciji i izradbi prevodilaca jezika za programiranje, poslije jednako toliko predavanja na dodiplomskim studijima, te poslije velikog broja realiziranih algoritama teorije formalnih jezika i prevodilaca, posebno predprocesora, te nekoliko desetaka diplomskih radova iz područja formalnih jezika, pred vama je jedna od knjiga koja sve to objedinjuje.

Teorija formalnih jezika ima više aspekata. Sigurno da će se pristup u njezinom izučavanju razlikovati na prirodoslovno-matematičkom fakultetu i filozofskom fakultetu. Mi smo, može se tako reći, više koristili teorijske rezultate koji su nastali izučavanjem formalnih jezika i pokušali ukazati na moguće praktične primjene. Ako smo ponegdje uveli teorem, nije nas interesirao njegov dokaz, već više njegove posljedice.

Pred vama je prva od dvije knjige koje se odnose na teoriju formalnih jezika, s podnaslovom Sintaksna analiza . Druga je knjiga, s podnaslovom Prevodenje , u pripremi i bit će objavljena početkom 2004. godine.

U uvodnom poglavlju, Osnove , dan je kratki repetitorij onih dijelova matematike koji su neophodni za potpuno razumijevanje ostalih poglavlja, a to su: skupovi, relacije, funkcije, matematička logika i grafovi.

Prvo poglavlje, Uvod u teoriju formalnih jezika , sadrži osnove teorije formalnih jezika, pojam znaka, i niza znakova, definiciju formalnog jezika, te regularne skupove i izraze kao formalizme za specificiranje regularnih jezika.

U drugom poglavlju, Gramatike , definiraju se gramatike kao jedan od sustava za specificiranje i generiranje jezika. Dana je klasifikacija gramatika i načini prikaza gramatika. Veći dio poglavlja odnosi se na beskontekstne gramatike i jezike, kao uvod u preostala poglavlja gdje ćemo se takoder pretežno baviti beskontekstnim jezicima.

Treće se poglavlje, Izvodenje i transformiranje gramatika , takoder bavi gramatikama, posebno opisom kako izvesti inicijalnu gramatiku danog jezika, a potom je transformirati u podesniji oblik ili zadanu formu.

Cetvrto je poglavlje, Uvod u teoriju automata , posvećeno drugom načinu prikaza, generiranja i prepoznavanja jezika - automatima, s posebnim osvrtom na konačne i stogovne automate. Takoder je prikazano kako se konačni automati mogu korisno upotrijebiti u izvodenju regularnih gramatika.

Peto je poglavlje, Općeniti postupci sintaksne analize , kao što slijedi iz naslova, posvećeno problemu sintaksne analize. Obradena su dva najpoznatija općenita postupka nedeterminističke sintaksne analize, silazna i uzlazna analiza, te dva tablična postupka: Cocke-Younger-Kasamijev (CYK) i Earlevjev postupak sintaksne analize.

Šesto je poglavlje, Jednoprolazna sintaksna analiza , nastavak opisa postupaka sintaksne analize. Tu je dano nekoliko postupaka determinističke sintaksne analize: silazni, uzlazni i tablični.

Završno, sedmo poglavlje, Jezici sa svojstvima , predstavlja sintezu moga dugogodišnjeg rada na razvoju posebnog opisa jezika i učinkovitoga determinističkog postupka sintaksne analize. Definicija jezika sa svojstvima obuhvaća sve tipove jezika (od tipa 3 do tipa 0) i jezike za programiranje.

U dodatku su dani programi napisani u Turbo Pascalu koji pokazuju ustroj pojedinih postupaka opisanih u knjizi: Sintaksna analiza jezika BNF, višeprolazne sintaksne analize (silazna, uzlazna i Cocke-Younger-Kasamijev algoritam) i predikatna sintaksna analiza kao primjer jedne jednoprolazne sintaksne analize. Osim toga što programi prikazuju kako se pojedini algoritmi mogu ustrojiti u Turbo Pascalu i predstavljaju simulaciju nekih postupaka sintaksne analize, istodobno mogu poslužiti u njihovom izučavanju.

U svim je poglavljima dano puno primjera koji upotpunjuju teorijska razmatranja, posebno pojedine definicije i algoritme. Na kraju poglavlja su pitanja i zadaci.

Knjiga je namijenjena, u prvom redu, studentima smjera opće informatologije (i smjera lingvistike) na Filozofskom fakultetu Sveučilišta u Zagrebu kao temeljna literatura u izučavanju predmeta Formalni jezici i prevodioci . Sadržaj knjige, odabir pojedinih tema, primjeri i programi rezultat su mojih najnovijih istraživanja u promicanju i modernizaciji nastavnih sadržaja predmeta Formalni jezici i prevodioci u okviru projekta Tempus .

Siguran sam da će knjiga s ovakvim sadržajem zainteresirati studente sličnih usmjerenja, inženjere informatike i računarskih znanosti, napredne srednjoškolce i mnoge druge samouke informatičare. Vjerujem da će programi dani u prilozima biti dovoljna motivacija znatiželjnijim čitateljima da ih u prvom koraku usavrše, a potom pristupe realizaciji nekih drugih algoritama danih u knjizi.

Na kraju zahvaljujem svima onima koji su na bilo koji način utjecali na sadržaj ove knjige, a posebno gospodinu Miroslavu Zečeviću koji me je prvi, davne 1977. godine, "zarazio" teorijom formalnih jezika, ukazao na literaturu i dao temeljne smjernice u toj disciplini.

Neizmjerna je moja zahvala i Georgesu Moustakiju koji je svojom prekrasnom poezijom i šansonama uvijek bio i ostao u pozadini svih mojih radova! Mislim da ćete u prijevodima nekoliko njegovih šansona, danih na početku svakog poglavlja, prepoznati nešto posebno (i možda otkriti tajnu vezu šansone sa sadržajem poglavlja u kojem je dana, jer od mnogih Moustakijevih šansona nisam nimalo slučajno izabrao baš te!).

Na kraju, bit ću vam zahvalan ako pažljivo pročitate ovu knjigu, prihvatite barem jedan njezin djelić i primijenite u svojoj praksi. Ako vam se, ipak, sve ovo učini prilično zamršenim, nerazumljivim ili neupotrebljivim, nemojte očajavati, ima i ljepših stvari u životu. Svi vi, a posebno oni kojima se svide (samo) šansone, možete mi se slobodno javiti na e-mail adresu:

zdovedan@hotmail.com .

Bit će mi posebno zadovoljstvo pokloniti vam CD sa svojim interpreta-cijama tih šansona (dakako, na francuskom!).

U Zagrebu, prosinca 2002. godine

Autor

Sadržaj