Parsiranje
Из Википедије, слободне енциклопедије
U računarstvu i lingvistici, 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, parser je jedna od komponenti interpretera ili kompajlera, u kojoj se prihvata podrazumevana hijerarhija ulaznog teksta i transformiše u oblik koji je pogodan za dalju obradu (najčešće u neki oblik stabla parsiranja, apstraktnog sintaksnog stabla ili neke druge hijerarhijske strukture), pri tom obično proveravajući i eventualne greške u sintaksi. Parser često koristi poseban leksički analizator za izdvajanje tokena iz sekvence ulaznih karaktera. Parseri mogu biti programirani ručno ili generisani poluautomatski (u nekom programskom jeziku) upotrebom programskih alata (poput Yacc-a) polazeći od gramatike u Bekus-Naurovoj formi.
Pored toga, parseri 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 parser kombinatori) koji omogućavaju konstrukciju parsera 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 X-SAIGA sajtu se može naći više pojedinosti o algoritmima i detaljima implementacije.
Садржај |
[уреди] Prirodni jezici
- Vidi i Parsiranje prirodnih jezika
Kod nekih sistema za mašinsko prevođenje i obradu prirodnih jezika, prirodne jezike parsiraju računarski programi. Programi ne mogu lako da parsiraju 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 parsirali 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 parsiranje koriste leksičke funkcionalne gramatike, ali u opštem slučaju, parsiranje 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 parsing 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 parsiranje 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 parsiranje zavisnih gramatika.
Većina savremenih parsera je bar delom statistička; odnosno, oni se oslanjaju na korpus već zabeleženih (ručno parsiranih) 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 parsiranje 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 kompjuterski parsirati; 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 tablično parsiranje.) 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 parsiranja u kojem parser predlaže velik broj analiza, a složeniji sistem bira najbolju opciju.
[уреди] Programski jezici
Parser se najčešće koristi kao komponenta kompajlera ili interpretera. On parsira 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 parseri. Parseri se pišu ručno ili se generišu upotrebom generatora parsera.
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, sa druge strane, ne mogu da se parsiraju efikasno. Zbog toga je uobičajena strategija pravljenje manje preciznog parsera 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 parsiranja 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. Parser 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 parsiranje ili sintaksna analiza, kojom se proverava da li ekstrahovani 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 parsiranje ili analiza, kojom se obrađuju implikacije upravo potvrđenih izraza i preduzimaju odgovarajuće akcije. U slučaju kalkulatora ili interpretera, akcija je izračunavanje izraza ili programa, dok bi, sa druge strane, kompajler generisao neku vrstu koda. Atributske gramatike mogu biti upotrebljene i za definisanje ovih akcija.
[уреди] Vrste parsera
Osnovni zadatak parsera 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 parseri koji koriste metodu rekurzivnog spusta su primeri parsera koji koriste sintaksnu analizu naniže, koji se ne mogu prilagoditi gramatikama koje sadrže levo-rekurzivna pravila. Iako se verovalo da se jednostavne implementacije 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 parsiranju višeznačnih kontekstno slobodnih gramatika, Frost, Hafiz i Kalahan su kreirali 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 generiše reprezentacije polinomijalne prostorne složenosti potencijalno eksponencijalnog broja stabala sintaksičke analize. Njihov algoritam može da generiše oba, i najlevlje i najdešnje izvođenje neke ulazne niske, korišćenjem pravila zadate KSG.
- Sintaksna analiza naviše - Parser 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 parsera 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 parser opisuje najlevlje ili najdešnje izvođenje zadate niske (pogledati: kontekstno slobodne gramatike). LL-analizatori će generisati najlevlje izvođenje, dok će LR-analizatori generisati najdešnje izvođenje, ali u obrnutom redosledu (od listova ka korenu).
[уреди] Primeri parsera
[уреди] Sintaksna analiza naniže
Neki od parsera koji koriste sintaksnu analizu naniže:
[уреди] Sintaksna analiza naviše
Neki od parsera koji koriste sintaksnu analizu naviše:
