СЛР анализатор

СЛР-анализатор (од енглеског Simple LR-parser) је врста ЛР-анализатора. Постоји генератор СЛР-анализатора који чита граматику у Бекусовој нотацији и конструише ЛР(0) стања машине и рачуна предувидне скупове за свако свођење у стању испитивањем скупа Следећи за нетерминале који су повезани са тим свођењем. Граматика је СЛР ако конфликте који се јављају у ЛР(0)-анализи могуће отклонити узимајући у обзир све скупове Следећи симбола граматике. Скуп Следећи за сваки нетерминал се одређује гледајући који терминали следе нетерминале у граматици. Корисно је имати скуп Први већ израчунат кад се прави скуп Следећи. У току рада СЛР-анализатора, свођење по правилу A → w ће се извршити ако се следећи симбол на улазу налази у скупу Следећи(A).

Проблем са СЛР-анализатором је то што је одређивање предувидних скупова сувише упрошћено јер се користе једино правила граматике да би се одредили. Прецизнији начин да се одреде предувидни скупови је да се испитају превођења по нетерминалима у сваком стању у оквиру ЛР(0) машине. Тако одређени предувидни скупови се називају ЛАЛР(1) предувидни скупови.

Конструкција СЛР-таблице:

1. Одредимо ЛР(0)-Ајтеме. I за граматику G’ (Увели смо ново почетно стање S’→S┤ у граматику G) конструишемо канонску колекцију K ЛР(0)-ајтема. Свакој колекцији ајтема Ii одговара стање i коначног аутомата.

2. Акције у стању и се одређују:

а) Ако је ајтем A→α•Aβ припада Ii (а припада Σ) и постоји прелаз из стања i у стање j по симболу a, тада

T[i,a]=(пребацивање, j )

б) Ако је ајтем A→α• припада Ii тада је

T[i,a]=(свођење, A→α)

за свако а из Следећи(A), где је A нетерминал различит од S’. Наравно треба претходно истиснути α | симбола са потисне листе.

ц) Ако је S’→S• ┤ припада Ii ,тада је

T[i,┤]= прихватање

д) Ако постоји прелаз из стања i у стање j по нетерминалу A, тада

T[i,A]= (пребацивање, j )

Треба напоменути да се овај корак јавља после акције свођења и у њему се дефинише нови симбол на врху потисне листе - симбол који одговара левој страни правила по коме је извршено свођење.

3. Грешка. Они елементи таблице који остану недефинисани представљају акцију одбацивања тј. грешке.

4. Почетно стање анализатора је стање које садржи ајтем

S’→•S┤

Пример:

Граматика која може да се анализира СЛР-анализатором али не и ЛР(0) је следећа:

(1) E → a E

(2) E → a

Конструкцијом скупова ајтема и ЛР(0) таблице бисмо добили:

Ајтем скуп 0

S → • E

E → • a E

E → • a

Ајтем скуп 1

E → a • E

E → a •

Ајтем скуп 2

S → E •

Ајтем скуп 3

E → a E •

табела:

	акција		прелаз
стање	a	┤	E
0	s1		2
1	s1/r2	r2	3
2		acc
3	r1	r1

Као што можемо да приметимо постоји пребацивање-свођење конфликт за стање 1 и терминал ‘a’. Међутим, скуп Следећи(E) је {┤} тако да су акције свођења r1 и r2 једино ваљане за колону ┤. Резултат је разрешен конфликт код СЛР таблице:

	акција		прелаз
стање	a	┤	E
0	s1		2
1	s1	r2	3
2		acc
3		r1