SLR analizator

SLR-analizator (od engleskog Simple LR-parser) je vrsta LR-analizatora. Postoji generator SLR-analizatora koji čita gramatiku u Bekusovoj notaciji i konstruiše LR(0) stanja mašine i računa preduvidne skupove za svako svođenje u stanju ispitivanjem skupa Sledeći za neterminale koji su povezani sa tim svođenjem. Gramatika je SLR ako konflikte koji se javljaju u LR(0)-analizi moguće otkloniti uzimajući u obzir sve skupove Sledeći simbola gramatike. Skup Sledeći za svaki neterminal se određuje gledajući koji terminali slede neterminale u gramatici. Korisno je imati skup Prvi već izračunat kad se pravi skup Sledeći. U toku rada SLR-analizatora, svođenje po pravilu A → w će se izvršiti ako se sledeći simbol na ulazu nalazi u skupu Sledeći(A).

Problem sa SLR-analizatorom je to što je određivanje preduvidnih skupova suviše uprošćeno jer se koriste jedino pravila gramatike da bi se odredili. Precizniji način da se odrede preduvidni skupovi je da se ispitaju prevođenja po neterminalima u svakom stanju u okviru LR(0) mašine. Tako određeni preduvidni skupovi se nazivaju LALR(1) preduvidni skupovi.

Konstrukcija SLR-tablice:

1. Odredimo LR(0)-Ajteme. I za gramatiku G’ (Uveli smo novo početno stanje S’→S┤ u gramatiku G) konstruišemo kanonsku kolekciju K LR(0)-ajtema. Svakoj kolekciji ajtema Ii odgovara stanje i konačnog automata.

2. Akcije u stanju i se određuju:

a) Ako je ajtem A→α•Aβ pripada Ii (a pripada Σ) i postoji prelaz iz stanja i u stanje j po simbolu a, tada

T[i,a]=(prebacivanje, j )

b) Ako je ajtem A→α• pripada Ii tada je

T[i,a]=(svođenje, A→α)

za svako a iz Sledeći(A), gde je A neterminal različit od S’. Naravno treba prethodno istisnuti α | simbola sa potisne liste.

c) Ako je S’→S• ┤ pripada Ii ,tada je

T[i,┤]= prihvatanje

d) Ako postoji prelaz iz stanja i u stanje j po neterminalu A, tada

T[i,A]= (prebacivanje, j )

Treba napomenuti da se ovaj korak javlja posle akcije svođenja i u njemu se definiše novi simbol na vrhu potisne liste - simbol koji odgovara levoj strani pravila po kome je izvršeno svođenje.

3. Greška. Oni elementi tablice koji ostanu nedefinisani predstavljaju akciju odbacivanja tj. greške.

4. Početno stanje analizatora je stanje koje sadrži ajtem

S’→•S┤

Primer:

Gramatika koja može da se analizira SLR-analizatorom ali ne i LR(0) je sledeća:

(1) E → a E

(2) E → a

Konstrukcijom skupova ajtema i LR(0) tablice bismo dobili:

Ajtem skup 0

S → • E

E → • a E

E → • a

Ajtem skup 1

E → a • E

E → a •

Ajtem skup 2

S → E •

Ajtem skup 3

E → a E •

tabela:

	akcija		prelaz
stanje	a	┤	E
0	s1		2
1	s1/r2	r2	3
2		acc
3	r1	r1

Kao što možemo da primetimo postoji prebacivanje-svođenje konflikt za stanje 1 i terminal ‘a’. Međutim, skup Sledeći(E) je {┤} tako da su akcije svođenja r1 i r2 jedino valjane za kolonu ┤. Rezultat je razrešen konflikt kod SLR tablice:

	akcija		prelaz
stanje	a	┤	E
0	s1		2
1	s1	r2	3
2		acc
3		r1