| sa svojom njuškom mješanca židovskog lutalice i grckog pastira i sa svojim kosama sa svih strana svijeta s ocima potpuno orošenim koje mi daju izgled sanjalice meni koji više ne sanjam cesto s rukama kradljivca muzicara i skitnice koje su opljackale tolike vrtove s ustima koja su pila ljubila i grizla a da nikad nisu zasitila svoju glad |
sa svojom njuškom mješanca židovskog lutalice i grckog pastira razbojnika i vagabunda s grudima koje su grlile pod suncem Ijeta sve ono što je suknju nosilo sa srcem koje je znalo patiti onoliko koliko je patilo a da od toga ne pravi drame s dušom koja nema ni najmanje šanse da se spasi i izbjegne cistilište |
sa svojom njuškom mješanca židovskog lutalice i grckog pastira doci cu moja nježna zarobljenice sestro moje duše izvoru mog života doci cu da upijem tvojih dvadeset godina bit cu princ krvi sanjalica ili maloljetnik vec kako ti izabereš i stvorit cemo od svakog dana cijelu jednu vjecnost ljubavi da bismo živjeli od nje umiruci |
|
mješanac meteque (georges moustaki / nepoznati student) |
||
U prethodnom smo poglavlju pokazali kako se automati mogu primijeniti u specificiranju jezika i prihvacanju ulaznih nizova. To je bila sintaksna analiza recenica, premda je nismo posebno spomenuli.
Vidjeli smo kako gramatika G= (N, T, P, S) generira jezik L(G). To je skup recenica w dobivenih svim mogucim izvodenjima iz S, tj.
L(G)={ w Î T*: S * Þ w }
U praksi se cesto susrecemo s problemom da je poznata gramatika nekog jezika i zadan niz znakova, a postavlja se pitanje je li to recenica jezika generiranog danom gramatikom. U tom slucaju problem se svodi na nalaženje niza izvodenja, pocevši od S, koji bi rezultirao tim nizom (recenicom). Takav postupak naziva se sintaksna analiza (ili sintakticka analiza ). Gramatika u tom slucaju ima ulogu prepoznavatelja jezika. Ustrojbu postupka sintaksne analize na racunalu (program u izabranom jeziku za programiranje) nazivat cemo parser .
Pri ucenju nekog jezika gramatika je najcesce u ulozi prepoznavatelja. To je njezin pravi smisao. Bilo bi besmisleno znajuci gramatiku nekog jezika prijeci odmah na izvodenje recenica. Takav proces bi možda trajao nekoliko godina! I u teoriji formalnih jezika gramatika je cešce u ulozi prepoznavatelja nego generatora jezika.
Algoritmi opcenite sintaksne analize primjenjivi su nad širokom klasom beskontekstnih jezika. Postoji nekoliko takvih algoritama. Ovdje su opisana dva koja pripadaju klasi povratnih ("backtrack") algoritama: silazna (top-down) sintaksna analiza i uzlazna (bottom-up) sintaksna analiza, te dva opcenita postupka koja pripadaju klasi tablicnih metoda, Cocke-Younger-Kasamijeva i Earlyjeva metoda.
Naziv "silazna sintaksna analiza." ili "sintaksna analiza s vrha" dolazi od ideje da se pokuša izvesti stablo sintaksne analize ulaznog niza zapoceto od korijena (vrha) gradeci ga prema dolje, prema listovima.
Neformalno je postupak silazne sintaksne analize jezika generiranog nekom gramatikom G sljedeci:
1) Najprije se alternativama produkcija gramatike G pridruže, proizvoljno, indeksi. Na primjer, ako su a 1 , a 2 , ..., a n sve alternative produkcije za A, onda je a 1 prva, a 2 druga alternativa, itd.
2) Neka je w =a 1 a 2 . . . a n ulazni niz za koji treba utvrditi je li u jeziku generiranom sa G . Bit ce upotrijebljena kazaljka koja ce pokazivati na tekuci znak ulaznog niza (na pocetku je to znak a 1 ).
3) Pocetni simbol S korijen je stabla sintaksne analize i istovremeno aktivni cvor.
Sljedeca dva koraka izvode se rekurzivno:
4) Ako je aktivni cvor neterminalni simbol X, bira se njegova prva alternativa i generira k njegovih izravnih slijednika. Neka su oznaceni s X 1 , ..., X k . X i je novi aktivni cvor. Ako je k=0, aktivni cvor postaje simbol koji slijedi X.
5) Ako je aktivni cvor terminalni simbol, treba ga usporediti s tekucim simbolom ulaznog niza (simbolom na koji pokazuje kazaljka). Ako su jednaki, kazaljka se pomice za jedan simbol udesno. Aktivni cvor postaje simbol desno od terminalnog simbola.
Ako terminalni simbol nije jednak tekucem simbolu ulaznog niza, vraca se na cvor gdje je bila upotrijebljena prethodna produkcija i izvodi sljedeca alternativa. Ako nijedna alternativa nije moguca, vraca se na prethodni cvor itd. Ako su upotrijebljene sve alternative i nije se uspjelo s izjednacivanjem ulaznog niza w, ulazni niz nije u jeziku generiranom gramatikom G . Na primjer, neka je dana gramatika G s produkcijama:
S ® aSbS | aS | c
Treba provjeriti je li ulazni niz w =aacbc u jeziku kojeg G generira, tj. postoji li, pocevši sa S, niz izvodenja
S * Þ aacbc
Najprije se može usvojiti da je
aSbS prva,
aS druga i
c treca alternativa za S.
Postupak silazne sintaksne analize bio bi:
a) aacbc s je korijen i inicijalni aktivni cvor. Kazaljka pokazuje na simbol a.
b) aacbc Generirana su cetiri izravna slijednika od S (prva alternativa). Terminal a je aktivni cvor i jednak je tekucem simbolu. Kazaljka se pomice za jedno mjesto.
c) aacbc Aktivni cvor je neterminal S, pa se ponovo generiraju cetiri izravna slijednika (prva alternativa). Aktivni cvor je terminal a, jednak je simbolu ulaznog niza, pa se kazaljka pomice za jedno mjesto.
d) aacbc Neterminal S ponovno je aktivni cvor. Generiraju se slijednici od S prema prvoj alternativi.
e) aacbc Terminal a je aktivni cvor i nije jednak tekucem simbolu. Pokušava se s drugom alternativom.
f) aacbc Terminal a je aktivni cvor i nije jednak tekucem simbolu. Pokušava se s trecom alternativom. Prvo je terminal c aktivni cvor i jednak je tekucem simbolu. Kazaljka se pomice za jedno mjesto. Sada je terminal b aktivni cvor i jednak je tekucem simbolu. Kazaljka se pomice za jedno mjesto.
g) aacbc Neterminal S je aktivni cvor. Generiraju se slijednici prema prvoj alternativi. Poslije toga je terminal a aktivni cvor i nije jednak tekucem znaku. Pokušava se s drugom alternativom. Opet je terminal a aktivni cvor i nije jednak tekucem znaku. Pokušava se s trecom alternativom. Tada je terminal c aktivni cvor i jednak je tekucem znaku. Kazaljka se pomice za jedno mjesto.
h) aacbc Kazaljka je iza posljednjeg znaka ulaznog niza, a u stablu su ostala još dva znaka, b i s. Vracamo se do mjesta gdje je posljednji put ekspandirano stablo. Ne postoji više alternativa, pa se vracamo na prethodno mjesto ekspanzije stabla. Ni tu nije moguca nova ekspanzija, pa se dalje vracamo, do koraka (b).
i) aacbc Pokušava se s drugom alternativom. Aktivni cvor je terminal a i jednak je tekucem znaku. Kazaljka se pomice za jedno mjesto.
k) aacbc Aktivni cvor je S. Generira se podstablo iz prve alternative. Novi aktivni cvor je terminal a i nije jednak tekucem znaku. Pokušava se s drugom alternativom. Opet je aktivni cvor terminal a. Pokušava se s trecom alternativom. Aktivni cvor je terminal c i jednak je tekucem znaku. Kazaljka se pomice za jedno mjesto i pokazuje iza posljednjeg znaka ulaznog niza. Više nema aktivnih cvorova. Ulazni niz je u jeziku.
Iz prethodnog primjera mogu se uociti osnovni nedostaci postupka silazne (povratne) sintaksne analize.
Prvo, postoji veoma opasna klopka u toj proceduri. Ako je gramatika rekurzivna slijeva proces se ne bi nikada završio! Naime, u tom slucaju bi se smjenom nekog neterminala (aktivnog cvora) dobio isti aktivni cvor, pa njegovom smjenom opet isti itd.
Drugi je nedostatak povratne silazne sintaksne analize što uvodi odredene semanticke aspekte. Na primjer, treba znati koji ce dio tablice simbola biti izbrisan u slucaju neuspješnog izjednacivanja; koja je alternativa na redu da se ekspandira stablo sintaksne analize i na koji simbol ulaznog niza treba vratiti kazaljku.
Treci je nedostatak indeksiranje (uredenje) alternativa produkcija. Stavljanje neke alternative na prvo mjesto u nekoj produkciji može ili povecati ili smanjiti ukupno vrijeme potrebno za izvršavanje sintaksne analize. To znaci da bi trebalo znati vjerojatnosti pojavljivanja svake od alternativa u nizovima izvodenja recenica jezika i potom ih urediti stavljajuci na prva mjesta one alternative koje imaju vecu vjerojatnost pojavljivanja.
Intuitivno se može zakljuciti da bi se sintaksna analiza s vrha mogla ubrzati ako sve alternative pocinju terminalnim simbolima. Ako bi, pored toga, terminalni simboli bili razliciti, moglo bi se jednoznacno, na osnovu tekuceg simbola ulaznog niza, odrediti koja ce alternativa biti upotrijebljena. Ovakva razmišljanja, kao što ce se vidjeti u sljedecem poglavlju, vode k pojmu LL (k) gramatika i jednoprolaznih sintaksnih analiza.
Da zakljucimo: silazna sintaksna analiza može se primijeniti samo za gramatike koje nemaju rekurzija slijeva. Medutim, znamo da prema teoremu 3.1 svaka beskontekstna gramatika koja je rekurzivna slijeva ima ekvivalentnu gramatiku koja nije rekurzivna slijeva, pa je taj postupak primjenljiv za sve beskontekstne jezike.
Gramatika iz uvodnog primjera silazne sintaksne analize nije rekurzivna slijeva (no jest zdesna), pa je moguce u konacno mnogo prolazaka iscrpsti sva izvodenja.
Poslije neformalnog opisa postupka silazne sintaksne analize i analize primjenljivosti takvog postupka, evo i njegova algoritma.
Algoritam koristi dva stoga (dvije "potisne" liste), L 1 i L 2 , i kazaljku koja pokazuje na tekuci simbol ulaznog niza. U opisu algoritma bit ce korištena notacija slicna onoj koja je bila upotrijebljena u opisu konfiguracije potisnog prepoznavaca.
Algoritam 5.1
Silazna sintaksna analiza.
Ulaz
Gramatika G ={ N , T , P , S ) koja nije rekurzivna slijeva i ulazni niz w =a 1 a 2 ... a n , n ³ 1. Pretpostavka je da su produkcije u P numerirane od 1 do p.
Izlaz
Stablo sintaksne analize za w , ako je w u jeziku L ( G ); inace "pogreška".
Postupak
(l) Urediti alternative za svaki neterminal A iz N . Na primjer, ako su A ® a 1 | a 2 |... |a k sve A-produkcije u P i alternative su uredene kao što je pokazano, tada je A 1 indeks za a 1 , A 2 indeks za a 2 , itd.
(2) Cetvorka (s, i, L 1 , L 2 ) oznacivat ce konfiguraciju algoritma, gdje su
(3) Pocetna konfiguracija algoritma je (q, 1, e , S$).
(4) Postoji šest vrsta koraka. Bit ce opisani konfiguracijom algoritma. Notacija (s, i, a , b ) |— (s ' , i' , a ', b '), jer se ovdje radi o vrsti automata, ima znacenje prelaska iz konfiguracije (s, i, a , b ) u konfiguraciju (s ' , i' , a ', b '). Moguca su sljedeca premještanja:
(a) Ekspanzija stabla
(q, i, a , A b ) |— (q, i, a A 1 , a 1 b )
gdje je A ® a 1 produkcija u P , a 1 je prva alternativa za A. Ovaj korak odgovara ekspanziji parcijalno izvedenog stabla koristeci prvu alternativu za prvi neterminal s lijeva u stablu.
(b) Uspješno izjednacenje ulaznog i izvedenog simbola
(q, i, a , a b ) |— (q, i+1, a a, b )
pod uvjetom da je a i =a, i £ n. Terminalni se simbol premješta s vrha liste L 2 na vrh liste L 1 . Kazaljka se pomice za jedno mjesto.
(c) Neuspješno izjednacenje ulaznog i izvedenog simbola
(q, i, a , a b ) |— (b, i, a , a b )
ako je a i ¹ a. Lijeva recenicna forma koja je bila upravo izvedena nije konzistentna s ulazom. Prelazi se u "povratni" mod.
(d) Uspješno okoncanje
(q, n+l, a , $) |— (t, n+1, a , e )
Dosegnut je kraj ulaznog niza i nadena lijeva recenicna forma koja odgovara ulazu.
(e) Povrat kazaljke
(b, i, a a, b ) |— (b, i-1, a , a b )
za sve a iz T . Svaki se put ulazni simbol premješta iz L 1 u L 2 .
(f) Pokušaj sljedece alternative
(b, i, a A j , a j b ) |—
(1) (q, i, a A j+1 , a j+1 b ), ako je a j+1 (j+1) -alternativa za A.
(2) Ne postoji sljedeca konfiguracija, ako je i=l, A=S i postoji samo j alternativa za S. Taj uvjet pokazuje da su iscrpljene sve moguce lijeve recenicne forme konzistentne s ulazom w, a da se za njega nije uspjelo izvesti stablo sintaksne analize. Ulazni niz w nije u jeziku pa se prekida daljnje izvršavanje postupka.
(3) (b, i, a , A b ), inace. Sve su alternative za A iscrpljene. Vraca se i izbacuju se sve alternative A j iz L 1 i zamjenjuje a j s A u L 2 .
Izvršavanje algoritma je kao što slijedi:
(1) Krenuvši s pocetnom kon figuracijom, izracunaju se slijedece uzasto pne konfiguracije:
C 0 |— C 1 |— . . . |— C i |— . . .
sve dok je definirana naredna konfiguracija.
(2) Ako je posljednje izracunata konfiguracija
(t, n+l, a , e )
prekida se daljnje izvršavanje. Ulazni je niz u jeziku generiranom gramatikom G . Inace, dojavljuje se greška.
Algoritam silazne sintaksne analize - parser realiziran je u Pascalu i dan u prilogu. Program može raditi korak po korak, prikazujuci svaku promjenu konfiguracije i pomicanje kazaljke, pa istovremeno predstavlja lekciju za ucenje postupka silazne sintaksne analize.
Primjer 5.1
Primijenimo algoritam u sintaksnoj analizi jezika jednostavnih aritmetickih izraza generiranog gramatikom:
E ® T+E (1) E ® T (2)
T ® F*T (3) T ® F (4)
F ® a (5)
gdje brojevi u zagradi oznacuju uredenje produkcija. Neka je El, jednako T+E, prva alternativa za E, a E2, jednako T, druga alternativa za E. Tl jednako F*T i T2 jednako F su prva i druga alternativa za T, a Fl jednako a je prva alternativa za F. Ako je ulazni niz w jednak a+a, algoritam ce izracunati slijedece konfiguracije:
Lista L1 sadrži stablo sintaksne analize (lijeve recenicne forme):
E Þ T+E Þ F+E Þ a+E Þ a+T Þ a+F Þ a+a
Postoji opcenita metoda sintaksne analize koja je po smislu suprotna od silazne sintaksne analize. To je uzlazna (bottom-up) sintaksna analiza.
U silaznoj se sintaksnoj analizi stablo sintaksne analize gradi od korijena prema dolje, do listova. Nasuprot tome, u uzlaznoj sintaksnoj analizi, pocinje se od listova i pokušava izgraditi stablo prema gore, do korijena. Ovdje ce biti izložen algoritam uzlazne sintaksne analize koji se naziva sintaksna analiza "s reduciranjem premještanja". Analiza se odvija koristeci najvažnije svojstvo sintaksne analize zdesna, prolazeci kroz sva moguca krajnja izvodenja zdesna koja su konzistentna s ulazom.
Premještanje se sastoji od ispitivanja niza na vrhu potisne liste i utvrdivanja postoji li desna strana produkcije koja može biti izjednacena s vrhom liste. Ako postoji, vrh potisne liste treba zamijeniti njome. Ako postoji više desnih strana produkcija koje se mogu upotrijebiti za reduciranje vrha postisne liste, uz pretpostavku prethodnog proizvoljnog uredenja produkcija, bit ce upotrebljena prva. Ako nije moguca nijedna redukcija, sljedeci se ulazni simbol premješta u listu i ponovi postupak. Uvijek ce se pokušati s reduciranjem prije premještanja. Ako se dosegne kraj ulaznog niza i nije moguca nijedna redukcija, vraca se na posljednje premještanje gdje je bila ucinjena redukcija i pokuša se s nekom drugom redukcijom.
Ulazni niz je u jeziku generiranom zadanom gramatikom ako lista sadrži pocetni simbol i dosegnut je kraj ulaznog niza. Ako se pokušalo sa svim redukcijama i nije se postiglo takvo stanje, postupak se prekida uz zakljucak da ulazni niz nije recenica jezika. Razmotrimo to na sljedecem primjeru. Neka je dana gramatika s produkcijama:
S ® AB A ® ab B ® aba
i neka je ulazni niz w=ababa. Pogledajmo kako ce se odvijati uzlazna sintaksna analiza:
a) Najprije se prvi znak ulaznog niza, a, premješta u listu. Nije moguca nijedna redukcija, pa se i b prebacuje u listu.
b) ab se može reducirati u A. Premješta se sljedeci znak u listu. Sada je u listi Aa i nije moguca redukcija. Premješta se sljedeci znak. Sadržaj je liste Aab.
c) ab se može reducirati u A. Posljednji se znak premješta u listu. Sadržaj liste je AAa.
d) Nije moguca nijedna redukcija. Vraca se na prethodni korak kad je u listi bilo Aab (b je na vrhu).
e) Nije moguca nijedna redukcija. Premješta se posljednji znak u listu. Sadržaj je liste: Aaba.
f) Sada se aba može reducirati u B. Sadržaj je liste: AB.
g) Konacno se AB može zamijeniti sa S. Time je stablo sintaksne analize izgradeno. Niz je u jeziku koji dana gramatika generira i može se dobiti izvodenjem:
S Þ AB Þ Aaba Þ ababa
Izložena metoda može se razmatrati kao niz svih mogucih premještanja u nedeterministickoj sintaksnoj analizi dane gramatike zdesna. Medutim, kao što je bilo u slucaju analize s vrha, i ovdje postoje izvjesna ogranicenja u primjeni.
Prvo, postoje situacije u kojima bi broj mogucih premještanja bio beskonacan. Takva klopka može se pojaviti ako gramatika ima petlje, tj. postoji izvodenje A + Þ A za neki neterminal A. Tada bi broj podstabala bio beskonacan.
Drugu poteškocu stvaraju e -produkcije u gramatici. Tada se može naciniti proizvoljan broj redukcija u kojima bi prazan niz bio "reduciran" u neki neterminal. Postupak sintaksne analize moze se proširiti da prihvaca i gramatike sa e -produkcijama, ali je to izostavljeno u ovoj knjizi. Osim toga, u trecem je poglavlju dan algoritam za izbacivanje e -produkcija, iz cega slijedi da je ovaj postupak primjenljiv za sve beskontekstne jezike.
Poslije neformalnog opisa postupka uzlazne sintaksne analize evo i algoritma koji dajemo u notaciji slicnoj onoj koja je upotrijebljena u algoritmu silazne sintaksne analize.
Algoritam 5.2
Uzlazna sintaksna analiza.
Ulaz
Gramatika G =( N , T , P , S ) bez petlji i e -produkcija (svojstvena gramatika) i ulazni niz w=a 1 a 2 ...a n , n ³ l. Uredene produkcije od 1 do p.
Izlaz
Stablo sintaksne analize za w, ako je w u L ( G ). Inace, "pogreška".
Postupak
(l) Urediti alternative neterminala iz N pocevši od startnog simbola i njegovih alternativa koje ce imati indeks 1, 2, itd. sve do posljednjeg neterminala i njegovih alternativa koje ce imati indekse ... p-1, p.
(2) Cetvorka (s, i, L 1 , L 2 ) oznacivat ce konfiguraciju algoritma, gdje su:
(3) Pocetna je konfiguracija algoritma (q, 1, $, e ).
(4) Izvršavanje pocinje prvim korakom:
1. korak : premještanje
(q, i, a , g ) |— (q, i+l, a a i , s g )
pod uvjetom da je i ¹ n+l. Potom se ide na drugi korak. Ako je i=n+l, prelazi se na treci korak. Ako je prvi korak bio moguc, upisuje se i-ti simbol na vrh liste L 1 , pomice se ulazna kazaljka i upisuje s na vrh liste L 2 , što je znak da je bilo ucinjeno premještanje.
2. korak : pokušaj reduciranja
(q, i, a b , g ) |— (q, i, a A, j g )
pod uvjetom da je A ® ß j-ta produkcija u P . ß je prva desna strana u linearnom uredenju (1), tj. sufiks niza a ß. Broj produkcije upisan je u listu L 2 . Ako je ovaj korak bio moguc, ponovo se vraca na njega.
3. korak : prihvacanje
(q, n+1, $ S , g ) |— (t, n+1, $ S , g )
Ako ovaj korak nije prihvatljiv, ide se na cetvrti korak.
4. korak : pocetak povratka
(q, n+1, a , g ) |— (b, n+1, a , g )
pod uvjetom da je a ¹ $ S . Ide se na peti korak.
5. korak : povratak
a) (q, i, a A, j g ) |— (b, i, a 'B, k g )
ako je A ® ß j-ta produkcija u P , a B ® ß' je sljedeca produkcija, oznacena s k prema uredenju (1), u kojoj je desna strana sufiks od a ß (vrijedi a ß = a 'ß'). Ide se na drugi korak.
b) (b, n+1, a A, j g ) |— (b, n+1, a b , g )
ako je A ® ß j-ta produkcija u P i nije preostala nijedna alternativa za reduciranje a ß. Ide se ponovo na peti korak.
c) (b, i, a A, j g ) |— (q, i+1, a b a, s g )
ako je i ¹ n+l, j-ta produkcija u P je A ® ß, i nije preostala nijedna alternativa za reduciranje a ß. Ovdje je a=a i premješteno uL 1 , a s u L 2 . Ide se na drugi korak.
d) (b, i, a a, s g ) |— (b, i-1, a , g )
ako je na vrhu liste L 2 simbol koji oznacuje premještanje (simbol s)
Primjer 5.2
Primijenimo algoritam u sintaksnoj analizi jezika jednostavnih aritmetickih izraza generiranog gramatikom G :
E ® E + T (1)
E ® T (2)
T ® T * F (3)
T ® F (4)
F ® a (5)
F ® (E) (6)
Primijetimo da je G rekurzivna slijeva, što u slucaju primjene algoritma uzlazne sintaksne analize ne predstavlja nikakve probleme.
Prema danom uredenju produkcija pojavom E+T na vrhu liste L 1 najprije ce se pokušati reduciranje koristeci E ® E+T, potom E ® T. Takoder ce se uvijek prije pokušati reducirati s T ® T*F nego s T ® F. Razmotrimo promjenu konfiguracije algoritma u sintaksnoj analizi niza a*a:
(q, 1, $, e )
Niz a*a je u jeziku L ( G ). Može se dobiti nizom izvodenja (desnih recenicnih formi):
E Þ T Þ T*F Þ T*a Þ F*a Þ a*a
Opisat cemo još dva postupka sintaksne analize koji pripadaju klasi tzv. tablicnih postupaka sintaksne analize. To su Cocke-Younger-Kasamijev i Earlyjev postupak. Oba postupka zahtijevaju oko n 3 vremena za analizu ulaznog niza duljine n.
Vidjeli smo da silazni i uzlazni povratni postupak sintaksne analize imaju vrijeme trajanja analize koje raste eksponencijalno s povecanjem duljine ulaznog niza. Cocke-Younger-Kasamijev (CYK) algoritam, medutim, treba n 3 vremena i n 2 memorijskog prostora. Neformalno, postupak je sljedeci: Neka je G =( N , T , P , S ) gramatika u Chomskyjevoj normalnoj formi, bez e -produkcija. Neka je w=a 1 ...a n ulazni niz kojeg treba analizirati. Pretpostavimo da je svaki a i u T, l £ i £ n. Bit CYK postupka jest da se izgradi tablica sintaksne analize T ciji ce elementi biti oznaceni s t ij , l £ i £ n i l £ j £ n-i+l. Svaki t ij ima vrijednost koja je podskup od N. Neterminal A ce biti u t ij ako i samo ako je A + Þ a i ...a i+j-1 , tj. ako A izvodi j ulaznih simbola koji pocinju od pozicije i. U posebnom slucaju, w je u L ( G ) ako i samo ako je S u t 1n .
Dakle, da bi se utvrdilo da je niz w u jeziku mora se izgraditi tablica T za w i provjeriti je li S na mjestu t 1n . Potom, ako želimo niz izvodenja koji završava s w, moramo upotrijebiti tu tablicu. Ovdje ce prvo biti dan algoritam 5.3 koji ce izgraditi tablicu, a algoritam 5.4 "cita" niz izvodenja.
Algoritam 5.3
Cocke-Younger-Kasamiev postupak sintaksne analize (CYK).
Ulaz
Gramatika G =( N , T , P , S ) u Chomskyjevoj normalnoj formi, bez e -produkcija i ulazni niz w=a 1 ...a n , w Î T + .
Izlaz
Tablica sintaksne analize T za w tako da t ij sadrži A ako i samo ako je
A + Þ a i ...a i+j-1
Postupak
(l)Staviti t i1 ={A: A ® a i u P } za svaki i. Poslije ovog koraka, ako t i1 sadrži A, sigurno postoji niz izvodenja A + Þ a i .
(2) Pretpostavimo da je t ij , bilo izracunato za sve i, l £ i £ n, i sve j ', l £ j' £ j. Staviti:
t ij ={A: za neki k, l £ k<j, A ® BC je u P, B je u t ik , C je u t i+k, j-k }
Buduci da je l £ k<j, i k i j-k su manji od j. Dakle, i t ik i t i+k, j-k bili su izracunati prije nego je t ij bilo izracunato. Poslije ovoga koraka ako t ij sadrži A, tada je:
A Þ BC + Þ a i ...a i+k-i C + Þ a i ...a i+k-1 a i+k ...a i+j-1
(3) Ponavljati korak (2) sve dok t ij ne postane poznato za sve l £ i £ n i l £ j £ n-i+l.
Primjer 5.3
Razmotrimo gramatiku G s produkcijama:
S ® AA | AS | b
A ® SA | AS | a
Ulazni je niz abaab. Primjenjujuci algoritam 5.3, tablica sintaksne analize je:
| 5 | A,S | ||||
| 4 | A,S > | A, S | |||
| 3 | A, S | S | A,S | ||
| 2 | A,S | A | S | A, S | |
| j 1 | A | S | A | A | S |
| i ® | 1 | 2 | 3 | 4 | 5 |
Iz koraka (1) je t 11 ={A} buduci je A ® a u P i a 1 =a. U koraku (2) se dodaje S u t 32 , buduci je S ® AA u P i A je i u t 31 i t 41 . Primijetiti, opcenito, da ako su t ij prikazani kao što je pokazano, možemo izracunati t ij , i>l, ispitujuci neterminale u sljedecim parovima ulaza:
(t il , t i + i, j-i ) , (t i2 , t i+2, j-2 ) , . . . , (t i, j-i , t i+j-i, 1 )
Tada, ako je B u t ik i C u t i+k, j-k za neki k tako da je l £ k<j i A ® BC je u P , treba dodati A u t ij . Buduci je S u t 15 , abaab je u jeziku L (G).
U sljedecem je algoritmu opisano kako se iz tablice sintaksne analize može dobiti sintaksna analiza slijeva.
Algoritam 5.4
Sintaksna analiza slijeva iz CYK tablice sintaksne analize.
Ulaz
Gramatika G =( N , T , P , S ) u Chomskyjevoj normalnoj formi, u kojoj su produkcije numerirane od 1 do p, ulazni niz w=a 1 ...a n i tablica sintaksne analize T izgradena algoritmom 5.3.
Izlaz
Sintaksna analiza slijeva (niz lijevih recenicnih formi) ili "pogreška".
Postupak
Najprije opišimo rekurzivnu proceduru gen (i, j, A) koja ce generirati sintaksnu analizu slijeva sukladnu izvodenju A + Þ a i a i+1 ...a i+j-1 , takoder slijeva. Procedura gen (i, j, A) definirana je kako slijedi:
(1) Ako je i=l i m-ta produkcija u P jest A ® a i , ispisati broj produkcije m.
(2) Ako je j>l, k je najmanji cijeli broj, l £ k<j, tako da je za neki B u t ik i C u t i+k, j-k , A ® BC
produkcija u P , recimo numerirana s m (može biti više izbora za A ® BC, ali cemo uzeti prvu). Ispisati broj m i izvršiti gen (i, k, B), potom gen (i + k, j-k, C).
Postupak pocinje s gen (l, n, S ), ispitujuci je li S u t 1n . Ako nije, dojavljuje se pogreška, ako jest, nastavlja se na opisani nacin.
Primjer 5.4
Razmotrimo gramatiku G iz primjera 5.3. Numerirajmo produkcije:
(1) S ® AA
(2) S ® AS
(3) S ® b
(4) A ® SA
(5) A ® AS
(6) A ® a
Ulazni je niz abaab, kao u primjeru 5.3, pa je tablica sintaksne analize takoder kao u primjeru 5.3. Buduci da je S u t 15 , ulazni je niz u jeziku L ( G ). Da bismo našli sintaksnu analizu slijeva, poziva se procedura gen (l, 5, S) . Pronadeno je A u t 11 i u t 24 , te produkcija S ® AA u skupu produkcija. Dakle, ispisuje se 1 (broj produkcije S ® AA).
Dalje se poziva gen (1, 1, A) i gen (2, 4, A). gen (1, 1, A) daje produkciju broj 6. Buduci da je S u t 21 i A je u t 33 i A ® SA je cetvrta produkcija, gen (2, 4, A) ispisuje 4 i poziva gen (2, l, S), pa gen (3, 3, A). Nastavljajuci, na kraju bismo dobili 164356263. Dakle, recenica abaab dobiva se u nizu izvodenja:
S Þ AA Þ aA Þ aSA Þ abA Þ abAS Þ abaS Þ abaAS Þ abaaS Þ abaab
Buduci da je gramatika Q dvoznacna, moguce je dobiti više sintaksnih analiza slijeva, što je ovdje izostavljeno.
Završavamo ovo poglavlje s još jednom tablicnom metodom sintaksne analize poznatom kao "Earlyjev postupak sintaksne analize".
Neformalno, postupak je sljedeci. Neka je G =( N , T , P , S ) beskontekstna gramatika i w=a 1 ...a n ulazni niz, w Î T *. Objekt oblika
[A ® X 1 X 2 ...X k • X k+1 .. .X m , i]
naziva se stavka za w ako je A ® X 1 X 2 . . .X m produkcija u P i 0 £ i £ n. Tocka izmedu X k i X k+1 je metasimbol i nije u N È T . Cijeli broj k može biti bilo koji broj od 0 (tada je • prvi simbol) do m (tada je • posljednji simbol). Ako je produkcija A ® e , tada je stavka jednaka [A ® •, i].
Za svaki j, 0 £ j £ n, treba izgraditi listu stavaka I j tako da je [A ® a • b , i] u I j , za 0 £ i £ j, ako i samo ako za neke g i d vrijedi S * Þ g A d , g * Þ a 1 ...a i i a* Þ a i+i ...a j . Dakle, druga komponenta stavke i broj liste u kojoj se pojavljuje stavljaju u zagradu dio ulaznog niza izvedenog iz a . Drugi uvjeti stavke samo nas osiguravaju od mogucnosti da se produkcija A ® a b može upotrijebiti na nacin kako se pojavljuje u nekom ulaznom nizu konzistentnom s w do pozicije j.
Niz lista I 0 , I 1 , ..., I n može se nazvati lista sintaksne analize ulaznog niza w . Primijetiti da je w u jeziku L ( G ) ako i samo ako postoji stavka oblika [ S ® a •, 0] u I n .
Algoritam 5.5
Earleyjev postupak sintaksne analize.
Ulaz
Beskontekstna gramatika G ={ N , T , P , S ) i ulazni niz w=a 1 ...a n iz T *.
Izlaz
Sintaksna analiza slijeva (niz lijevih recenicnih formi) ili "pogreška".
Postupak
Prvo se konstruira I 0 na sljedeci nacin:
1) Ako je S ® a produkcija u P , dodati [S ® • a , 0] u I 0 . Potom izvršiti korak (2) i (3) sve dok se nova stavka može dodati u I 0 .
2) Ako je [B ® g •, 0] u I 0 , gdje g može biti i e , što znaci da se ovaj korak bio izvršio inicijalno, dodati [A ® a B• b , 0] u I 0 za sve [A ® a •B b , 0].
3) Pretpostavimo da je [A ® a •B b , 0] stavka u I 0 . Dodati u I 0 , za sve produkcije iz P oblika B ® g , stavku [B ® • g , 0] (uz pretpostavku da ta stavka nije vec bila u I 0 ). Sada se može konstruirati I j iz I 0 , I 1 , ..., I j-1
4) Za svaki [B ® a •a b , i] u I j-1 tako da je a=a j dodati [B ® a a• b , i] u I j . Potom izvršavati korake (5) i (6) sve dok se može dodati nova stavka.
5) Neka je [A ® a •, i] stavka u I j . Provjeriti nalaze li se stavke oblika [B ® a •A b , k] u I 1 . Za sve nadene stavke dodati [B ® a A• b , k] u I j .
6) Neka je [A ® a •B b , i] stavka u I j . Za sve B ® g u P dodati [B ® • g , j] u I j .
Primijetiti da se pojavom stavke s terminalom desno od tocke ne tvori nova stavka u koracima (2), (3), (5) i (6). Algoritam, dakle, tvori I j za 0 £ j £ n.
Primjer 5.5
Primijenimo algoritam 5.5 u sintaksnoj analizi jezika jednostavnih aritmetickih izraza generiranog gramatikom G :
E ® T + E (1)
E ® T (2)
T ® F * T (3)
T ® F (4)
F ® (E) (5)
F ® a (6)
i neka je (a+a) *a ulazni niz. Iz koraka (1) dodajemo dvije nove stavke, [E ® •T+E, 0] i [E ® •T, 0] u I 0 . Te ce stavke biti uzete u obzir pri dodavanju stavki [T ® •F*T, 0] i [T ® •F, 0] u I 0 prema pravilu (3). Nastavljajuci, dodaju se [F ® • (E) , 0] i [F ® •a, 0]. Više se nijedna stavka ne može dodati u I 0 .
Sada gradimo I l . Prema (4) dodajemo [F ® (•E), 0], buduci da je a i =(•. Potom se, prema pravilu (6), dodaju [E ® •T+E, 1], [E ® •T, l], [T ® •F*T, 1], [T ® •F, 1], [F ® • (E), l] i [F ® •a, 1]. Sada se više nijedna stavka ne moze dodati u I 1 .
Da bismo izgradili I 2 , primijetimo da je a 2 =a i da se prema pravilu (4) stavka [F ® a•, l] može dodati u I 2 . Dalje, prema pravilu (5), promatramo tu stavku odlazeci u I 1 i tražeci stavke s F koje slijedi tocka. Pronalazimo dvije stavke, [T ® F•*T, 1] i [T ® F•, 1], i dodajemo ih u I 2 . Promatrajuci prvu od njih, ništa, ali druga nas navodi da ponovno pregledamo I 1 , ovog puta stavke sa •T u sebi. Najviše se dvije stavke mogu dodati u I 2 , [E ® T•+E, 1] i [E ® T•, 1]. Opet druga stavka uzrokuje da se [F ® (E•),0] može dodati u I 2 . Sada se više nijedna stavka ne može dodati u I 2 . Nastavljajuci, na kraju bismo dobili liste:
| I 0 | I 1 | I 2 | I 3 |
| [E ® • T+E, 0] | [F ® ( • E), 0] | [F ® a • , l] | [ E ® T+ • E, 1] |
| [E ® • T, 0] | [E ® • T+E, 1] | [T ® F • *T, 1] | [E ® • T+E, 3] |
| [T ® • F*T, 0] | [E ® • T, 1] | [T ® F • , 1] | [E ® • T, 3] |
| [T ® • F, 0] | [E ® • F*T, 1] | [E ® T • +E, 1] | [T ® • F*T, 3] |
| [F ® • (E),0] | [T ® •F, 1] | [E ® T • +E, 1] | [E ® • F, 3] |
| [F ® • a, 0] | [F ® • (E),1] | [F ® (E • ), 0] | [F ® • (E), 3] |
| [F ® • a, l] | [F ® • a, 3] |
| I 4 | I 5 | I 6 | I 7 |
| [F ® a • , 3] | [F ® (E) • , 0] | [T ® F* • T, 0] | [F ® a • , 6] |
| [T ® F • *T, 3] | [T ® F • *T, 0] | [T ® • F*T, 6] | [T ® F • *T, 6] |
| [T ® F • , 3] | [T ® F • , 0] | [T ® • F, 6] | [T ® F •, 6] |
| [E ® T • +E, 3] | [E ® T • +E, 0] | [F ® • (E), 6] | [T ® F*T • , 0] |
| [E ® T • ,3] | [E ® 1 • , 0] | [F ® • a, 6] | [E ® T • +E, 0] |
| [E ® T+E • , 1] | [E ® T • , 0] | ||
| [E ® (E • ), 0] |
Buduci da je [E ® T•, 0] na kraju liste, niz (a+a) *a je u jeziku L ( G ).
E ® E+E| E*E | (E) | a
za uzlaznu sintaksnu analizu. Što zakljucujete? Zašto?| (1) | d (q, a , e ) | = { (q, a )} | za aÎ{a,+,*,(,)} |
| (2) | d (q, e ,E+T) | = {(q,E)} | |
| d (q, e ,T) | = {(q,E)} | ||
| d (q, e ,T*F) | = {(q,T)} | ||
| d (q, e ,F) | = {(q,T)} | ||
| d (q, e ,(E)) | = {(q,F)} | ||
| d (q, e ,a) | = {(q,F)} | ||
| (3) | d (q, e ,$E) | = {(r, e )} |