From Wikipedia, the free encyclopedia
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 a) 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. ) 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 može se naći više pojedinosti o algoritmima i detaljima ugrađivanja.
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. 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 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 (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 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. 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.
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.
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.
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:
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).
Neki od raščlanjivača koji koriste sintaksnu analizu naniže:
Neki od raščlanjivača koji koriste sintaksnu analizu naviše:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.