Raščlanjivanje

U računarstvu i lingvistici, raščlanjivanje (parsiranje, formalnije: sintaksna analiza) je postupak analiziranja niza tokena radi utvrđivanja gramatičke strukture u odnosu na datu (više ili manje) formalnu gramatiku. Dakle, raščlanjivač je jedan od delova interpretatora ili kompilatora, u kojoj se prihvata podrazumevana hijerarhija ulaznog teksta i pretvara u oblik koji je pogodan za dalju obradu (najčešće u neki oblik stabla raščlanjivanja, apstraktnog sintaksnog stabla ili neke druge hijerarhijske strukture), pritom obično proveravajući i eventualne greške u sintaksi. Raščlanjivač često koristi poseban leksički analizator za izdvajanje tokena iz niza ulaznih znakova. Raščlanjivači mogu biti programirani ručno ili stvoreni poluautomatski (u nekom programskom jeziku) upotrebom programskih alata (poput Yacca) polazeći od gramatike u Bekus-Naurovoj formi.

Pored toga, raščlanjivači mogu biti konstruisani i kao izvršne specifikacije gramatika u funkcionalnim programskim jezicima. Frost, Hafiz i Kalahan (eng. Callaghan) su na osnovu radova drugih napravili skup funkcija višeg reda (nazvani raščlanjivački kombinatori) koji omogućavaju konstrukciju raščlanjivača za analizu naniže, polinomijalne vremenske i prostorne složenosti, kao izvršne specifikacije za višeznačne gramatike koje sadrže levo-rekurzivna pravila. Na sajtu X-SAIGA može se naći više pojedinosti o algoritmima i detaljima ugrađivanja.

Prirodni jezici

Pogledajte i raščlanjivanje prirodnih jezika

Kod nekih sistema za mašinsko prevođenje i obradu prirodnih jezika, prirodne jezike raščlanjuju računarski programi. Programi ne mogu lako da raščlanjuju rečenice koje formiraju ljudi, s obzirom na to da je višeznačnost jedna od osnovnih odlika u strukturi jezika koje koriste ljudi. Da bi raščlanjivali podatke prirodnog jezika istraživači prvo moraju da se dogovore koja će se gramatika koristiti. Na izbor sintakse utiču kako lingvistička tako i pitanja računarske obrade; na primer, neki sistemi za raščlanjivanje koriste leksičke funkcionalne gramatike, ali u opštem slučaju, raščlanjivanje gramatika ove vrste pripada problemima klase složenosti NP. Head-driven phrase structure grammar je još jedan lingvistički formalizam koji je bio popularan u raščlanjivačkoj zajednici, ali drugi istraživački napori su se fokusirali na manje složene formalizme kao što su oni koji su korišćeni u Penn banci drveta. Plitko raščlanjivanje ima za cilj samo određivanje granica glavnih sastavnih delova kao što su imeničke fraze. Još jedna popularna strategija za izbegavanje lingvističkih kontroverzi je raščlanjivanje zavisnih gramatika.

Većina savremenih raščlanjivača je bar delom statistička; odnosno, oni se oslanjaju na korpus već zabeleženih (ručno raščlanjenih) podataka. Ovaj pristup dozvoljava sistemu da prikuplja informacije o učestalosti pojavljivanja raznih konstrukcija u određenom kontekstu. (Videti mašinsko učenje) Pristupi koji su korišćeni obuhvataju pravolinijske SCFG (stohastičke kontekstno slobodne gramatike), maksimalnu entropiju, i neuronske mreže. Većina uspešnijih sistema koristi leksičku statistiku (to jest, razmatra identitet upotrebljenih reči, kao i njihov govorni deo).

Algoritmi za raščlanjivanje prirodnih jezika ne mogu da se oslone na to da će gramatika imati „fine“ osobine kao ručno pravljene gramatike za programske jezike. Kako je već ranije pomenuto, neke gramatičke formalizme je veoma teško raščlaniti uz pomoć računara; u principu, čak i u slučaju kada željena struktura nije kontekstno slobodna, koristi se neka vrsta kontekstno slobodne aproksimacije u odnosu na gramatiku koja se koristi da bi se izvršio prvi prolazak. Algoritmi koji koriste kontekstno slobodne gramatike često se oslanjaju na neku varijantu CYK algoritma, obično sa nekom heuristikom za odbacivanje nepotrebnih analiza da bi se uštedelo na vremenu. (Videti tabelarno raščlanjivanje.) Ipak, neki sistemi su žrtvovali brzinu u cilju tačnosti korišćenjem npr. linearnih algoritama sa prebacivanje-svođenje (eng. shift-reduce) konfliktima. Nešto skoriji razvoj je prerangiranje raščlanjivanja u kojem raščlanjivač predlaže veliki broj analiza, a složeniji sistem bira najbolju opciju.

Programski jezici

Raščlanjivač se najčešće koristi kao deo kompilatora ili interpretatora. On raščlanjuje izvorni kod programskog jezika da bi stvorio neki oblik interne reprezentacije. Obično se programski jezici opisuju kontekstno slobodnim gramatikama jer se za njih mogu napisati brzi i efikasni raščlanjivači. Raščlanjivači se pišu ručno ili se stvaraju upotrebom generatora raščlanjivača.

Kontekstno slobodne gramatike su ograničene u meri u kojoj mogu da izraze sve jezičke zahteve. Neformalno, razlog je da je ograničeno pamćenje tog jezika. Gramatika ne može da zapamti prisustvo neke konstrukcije u odnosu na proizvoljno dug ulaz; ovo je neophodno za jezik u kojem, na primer, ime mora biti deklarisano pre njegovog pozivanja. Moćnije gramatike koje mogu da izraze ova ograničenja, s druge strane, ne mogu da se raščlanjuju efikasno. Zbog toga je uobičajena strategija pravljenje manje preciznog raščlanjivača za kontekstno slobodnu gramatiku koji prihvata nadskup željenih jezičkih konstrukcija (to jest, prihvata i neke konstrukcije koje nisu korektne), a neželjene konstrukcije kasnije mogu biti izbačene.

Pregled postupka

Sledeći primer pokazuje uobičajeni slučaj raščlanjivanja računarskog jezika sa dva nivoa gramatike: leksičkim i sintaksnim.

Prvu fazu predstavlja ekstrahovanje tokena, ili leksička analiza, kojom se ulazna struja karaktera deli u osnovne simbole čije je značenje definisano gramatikom regularnih izraza. Na primer, program za izračunavanje će tražiti ulaz kao što je 12*(3+4)^2 i podeliti ga na tokene 12, *, (, 3, +, 4, ), ^ i 2, od koji svakih predstavlja simbol koji ima značenje u kontekstu aritmetičkog izraza. Raščlanjivač treba da sadrži pravila koja će mu reći da slova *, +, ^, ( i ) označavaju početak novog tokena, tako da besmisleni tokeni kao što su 12* ili (3 neće biti ekstrahovani.

Sledeća faza je raščlanjivanje ili sintaksna analiza, kojom se proverava da li otpakovani tokeni formiraju izraz koji je dozvoljen. Ovo se obično čini korišćenjem kontekstno slobodne gramatike koja rekurzivno definiše komponente koje mogu činiti izraz i redosled kojim one moraju da se pojavljuju. Ipak, ne mogu sva pravila koja definišu programske jezike da se izraze samo preko kontekstno slobodnih gramatika, na primer, ispravnost tipova i odgovarajuće deklaracije identifikatora. Ova pravila mogu formalno da se izraze pomoću atributskih gramatika.

Poslednja faza je semantičko raščlanjivanje ili analiza, kojom se obrađuju implikacije upravo potvrđenih izraza i preduzimaju odgovarajuće radnje. U slučaju kalkulatora ili interpretatora, radnja je izračunavanje izraza ili programa, dok bi, s druge strane, kompilator stvorio neku vrstu koda. Atributske gramatike mogu biti upotrebljene i za definisanje ovih radnji.

Vrste raščlanjivača

Osnovni zadatak raščlanjivača je da odredi da li i kako se dati ulaz može dobiti iz početnog simbola gramatike. Postoje dva osnovna načina da se to uradi:

Sintaksna analiza naniže - Sintaksna analiza naniže se može posmatrati kao pokušaj nalaženja najlevljeg izvođenja neke struje ulaznih karaktera konstruisanjem drveta sintaksičke analize koje započinje od korena i napreduje ka listovima na osnovu pravila zadate formalne gramatike. Čitanje ulaznih karaktera vrši se sleva nadesno. Uključivanje izbora se koristi za prilagođavanje višeznačnosti proširivanjem svih mogućih desnih strana gramatičkih pravila. LL-analizatori i raščlanjivači koji koriste metodu rekurzivnog spusta su primeri raščlanjivača koji koriste sintaksnu analizu naniže, koji se ne mogu prilagoditi gramatikama koje sadrže levo-rekurzivna pravila. Iako se verovalo da se jednostavna ugrađivanja sintaksne analize naniže ne mogu prilagoditi gramatikama sa direktnom i indirektnom levom rekurzijom i da mogu da zahtevaju eksponencijalnu vremensku i prostornu složenost pri raščlanjivanju višeznačnih kontekstno slobodnih gramatika, Frost, Hafiz i Kalahan su napravili nešto složeniji algoritam za sintaksnu analizu naniže koji se može primeniti i na višeznačne i levo-rekurzivne gramatike, polinomijalne vremenske složenosti, koji stvara reprezentacije polinomijalne prostorne složenosti potencijalno eksponencijalnog broja stabala sintaksičke analize. Njihov algoritam može da stvara oba, i najlevlje i najdešnje izvođenje neke ulazne niske, korišćenjem pravila zadate KSG.
Sintaksna analiza naviše - Raščlanjivač pokušava da ulaznu nisku tokena svede na početni simbol, konstruišući drvo sintaksičke analize polazeći od njegovih listova, postupnim svođenjem ka korenu. Postupak svođenja se sastoji u tome da se u pojedinim koracima analize, prepoznata desna strana nekog pravila gramatike zameni odgovarajućom levom stranom tog pravila. LR-analizatori su primeri raščlanjivača koji koriste sintaksnu analizu naviše.

Još jedna značajna razlika između ova dva navedena načina sintaksne analize je u tome da li odgovarajući raščlanjivač opisuje najlevlje ili najdešnje izvođenje zadate niske (pogledati: kontekstno slobodne gramatike). LL-analizatori će stvoriti najlevlje izvođenje, dok će LR-analizatori stvoriti najdešnje izvođenje, ali u obrnutom redosledu (od listova ka korenu).

Primeri raščlanjivača

Sintaksna analiza naniže

Neki od raščlanjivača koji koriste sintaksnu analizu naniže:

LL raščlanjivač

Sintaksna analiza naviše

Neki od raščlanjivača koji koriste sintaksnu analizu naviše:

Vidi još