LR(0) sintaksički analizator

Kod različitih potklasa LR-gramatika, na različite načine se obrađuje preduvidni simbol. Kako se tablice analize LR analizatora formiraju na osnovu pravila gramatike i, eventualno, preduvidnog simbola, njihov sadržaj može biti različit. Tablice analize su LR(0) ako su formirane bez obzira na preduvidni simbol, a u procesu analize naviše se ne javljaju konflikti. LR(0) analizator je analizator za LR(0) gramatike, koji čita ulaz sa leva na desno.

Konstruisanje LR(0)-tablice analize

Konkretna gramatika koju ćemo koristiti kao primer:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Ajtemi

Konstrukcija tablica za LR(0) analizator je zasnovana na LR(0) ajtemima (ovde ćemo ih jednostavno zvati ajtemi). Ajtemi su gramatička pravila koja sadrže metasimbol . (tačka), dodat negde na desnoj strani pravila. Na primer pravilo E → E + B ima četiri odgovarajuća naredna ajtema:

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Pravila oblika A → ε imaju samo jedan ajtem A → •. Ova pravila će biti korišćena da odrede stanje analizatora. Ajtem E → E • + B, na primer, ukazuje da je analizator prepoznao na ulazu nisku koja se izvodi iz neterminala E, i da očekuje da pročita '+' , a zatim nisku koja se izvodi iz neterminala B.

Formiranje stanja analizatora pomoću ajtema

Obično je nemoguće formirati stanje analizatora samo pomoću jednog ajtema zato što se ne može unapred znati, za to stanje, koje pravilo će se koristiti pri prebacivanju. Na primer, ako postoji i pravilo E → E * B onda će oba ajtema, E → E • + B i E → E • * B, biti primenljiva posle niske koja je pročitana sa ulaza i izvodi se iz E. Zato formiranje stanja analizatora vršimo skupom ajtema, u ovom slučaju skupom { E → E • + B, E → E • * B }.

Zatvorenje skupa ajtema

Ajtem sa tačkom ispred neterminala, kao E → E + • B, ukazuje na to da analizator očekuje da mu se prosledi neterminal B tj. očekuje na ulazu nisku koja se izvodi iz B. Da bi skup ajtema sigurno sadržao sva moguća pravila koja se mogu koristiti tokom analize, moraju mu se dodati svi ajtemi koji sadrže izvođenja iz B. To znači da ako u gramatici postoji pravilo kao B → 1 i B → 0 onda skup ajtema mora sadržati i ajteme B → • 1 and B → • 0. Ovaj postupak se može formalno iskazati na sledeći način:

Ako neki skup ajtema sadrži ajtem oblika A → v • Bw i u gramatici postoji pravilo oblika B → w' , onda se skupu mora dodati ajtem B → • w' .

Svaki skup ajtema može biti proširen tako da zadovoljava sledeće pravilo: nastavlja se sa dodavanjem odgovarajućih ajtema sve dok svi neterminali ispred kojih je tačka nisu ubrojani. Minimalno proširenje se naziva zatvorenje skupa ajtema i obeležava se sa clos(I) gde je I skup ajtema. Ova zatvorenja skupova ajtema se uzimaju za stanja analizatora, iako će samo ona koja su dostižna iz početnog stanja biti uključena u tablicu.

Proširena gramatika

Pre nego sto se počne sa određivanjem ( determinizacijom) prelaza između različitih stanja, gramatika se uvek proširi dodatnim pravilom

(0) S → E

gde je S novi početni simbol, a E stari početni simbol. Analizator će koristiti ovo pravilo samo za svođenje(redukciju) kada je ulazna niska prihvaćena.

Za pomenuti primer ovako izgleda postojeć proširena gramatika:

(0) S → E

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Za ovu proširenu gramtiku prave se skupovi ajtema i prelazi između njih.

Konstrukcija tablice

Određivanje dostižnih skupova ajtema i prelaza između njih

Prvi korak u konstrukciji tablice je određivanje prelaza između zatvorenja skupova ajtema (između stanja analizatora). Ovi prelazi se određuju kao da razmatramo konačan automat koji može da čita terminale, kao i neterminale. Početno stanje automata je uvek zatvorenje prvog ajtema dodatog pravila: S → • E:

Skup ajtema (stanje) 0

S → • E

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

Podebljano "+" ispred ajtema označava ajteme koji su dodati da bi se konstruisalo zatvorenje (ne treba ga mešati sa matematičkim operatorom '+' koji je terminal tj. završni simbol). Originalni ajtemi bez "+" zovu se jezgra skupa ajtema.

Počevsi sa stanjem 0 određuju se sva stanja koja su iz njega dostižna. Mogući prelazi za skup stanja pronalaze se posmatrajući simbole ( terminale ili neterminale) koji se nalaze iza metasimbola .; U slučaju stanja 0 to su terminali '0' i '1' i neterminali E i B. Da bi se odredio skup ajtema do koga vodi simbol x, prati se sledeća procedura:

1. Uzima se skup S, svih onih ajtema koji se nalaze u trenutnom skupu, a koji imaju . ispred simbola x.
2. Za svaki ajtem u S, tačka se pomera desno od x.
3. Formira se zatvorenje dobijenog skupa ajtema.

Za terminal '0' se dobija:

Stanje 1

B → 0 •

i za terminal '1':

Stanje 2

B → 1 •

i za neterminal E:

Stanje 3

S → E •

E → E • * B

E → E • + B

i za neterminal B:

Stanje 4

E → B •

Može se primetiti da se prilikom formiranja zatvorenja ne dodaju uvek novi ajtemi. Ovaj proces se nastavlja sve dok se mogu formirati novi skupovi ajtema tj. stanja. Za stanja 1, 2, i 4 neće biti jos prelaza jer nema tačke ni ispred jednog simbola. U stanju 3 tačka je isped terminala '*' i '+'. Za '*' prelaz izgleda ovako:

Stanje 5

E → E * • B

+ B → • 0

+ B → • 1

a za '+' izgleda ovako:

Stanje 6

E → E + • B

+ B → • 0

+ B → • 1

Za stanje 5 treba razmatrati terminale ‘0’ i ‘1’ i neterminal B. Za terminale se primećuje da se formira zatvorenje koje je jednako zatvorenjima skupova ajtema koja već postoje. To su stanja 1 i 2, respektivno. Za neterminal B prelaz izgleda ovako:

Stanje 7

E → E * B •

Za stanje 6 treba razmatrati terminale '0' i '1' i neterminal B. Kao i ranije, za terminale se formira zatvorenje koje jednako zatvorenjima skupova ajtema koje već imamo. To su stanja 1 i 2. Za neterminal B prelaz izgleda ovako:

Stanje 8

E → E + B •

Konačno, ovo stanje nema simbola ispred kojih je tačka, pa nema više stanja koja se mogu dodati i proces je završen. Tablica prelaza za analizator (automat) sada izgleda ovako:

Stanje	*	+	0	1	E	B
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

Konstrukcija ACTION/GOTO tablica

Od tablice koja je već konstruisana i od skupova ajtema pravi se ACTION/GOTO tablica na sledeći način:

1. kolone za neterminale se prepišu u GOTO deo tablice
2. kolone za terminale se prepišu u ACTION deo tablice kao akcije prebacivanja (shift)
3. dodaje se nova kolona za marker kraja ulaza '$' u ACTION deo tablice, koja sadrži acc(prihvatanje) za svako stanje koje sadrži ajtem S → E .
4. Ako neki skup ajtema sadrži ajtem oblika A → w • i A → w je pravilo koje smo obeležili sa m (gde je m > 0) onda se red za stanje i u ACTION delu tablice kompletno popunjava akcijom svođenja (reduce) tj. obeležava se sa rm.

Čiltalac može da proveri da kada se primene navedena pravila konstrukcije dobija se ACTION/GOTO tablica koja je ovde predstavljena.

Primećuje se da samo korak 4. iz prethodne procedure dovodi do primene akcije svođenja, i da sve akcije svođenja moraju zauzeti čitav red tabele, sto znači da se vrši svođenje bez obzira na to koji će se simbol naći na ulazu. Ovo je zato što su ovo baš LR(0) tablice analize: one ne koriste preduvidne simbole u odlučivanju koja će se akcija naredna izvršiti. Gramatike koje koriste preduvidne simbole u odlučivanju o narednoj akciji, moraju imati tablice analize koje će sadržati u redovima različite akcije svođenja za različite kolone. Gornja procedura ne omogućava pravljenje ovakvih redova.

Usavršavanjem LR(0) tablica dobijaju se tablice kao sto su SLR i LALR, kod kojih akcija svođenja ne zauzima čitav red i koje zato mogu služiti za analiziranje većeg broja gramatika.

Konflikti u dobijenim tablicama

Analizator je konstruisan na takav način da je osigurano da on bude deterministicki. Međutim, kada se u ACTION tablicu dodaju akcije svođenja, može se desiti da je ista ćelija tablice popunjena i akcijom svođenja i akcijom prebacivanja ( takozvani prebacivanje-svođenje konflikt) ili sa dve akcije svođenja (svođenje - svođenje konflikt). Može se pokazati da kada se ovo desi to znači da gramatika nije LR(0).

Jednostavan primer jedne gramatike koja nije LR(0) sa prebacivanje - svođenje konfliktom :

(1) E → 1 E

(2) E → 1

Jedan od skupova ajtema koje se pojavljuju je:

Stanje 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Ovde se javlja prebacivanje - svođenje konflikt jer u ACTION tablici za ovo stanje i terminal '1' moze se izvršiti akcija prebacivanja u stanje 1 i akcija svođenja po pravilu 2.

Jednostavan primer jedne gramatike koja nije LR(0) sa svođenje - svođenje konfliktom :

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

U ovom slučaju dobijamo sledeći skup ajtema:

Stanje 1

A → 1 •

B → 1 •

Ovde se javlja svođenje - svođenje konflikt jer u ACTION tablici za ovo stanje i terminal '1' može se izvršiti akcija svođenja po pravilu 3, kao i po pravilu 2.

Oba navedena primera se mogu rešiti pomoću preduvidnog simbola i prethodne analize, korišćenjem skupova Sledi (Follow) za neterminale. Na taj način se formiraju SLR analizatori.