ЛР(0) синтаксички анализатор

Код различитих поткласа ЛР-граматика, на различите начине се обрађује предувидни симбол. Како се таблице анализе ЛР анализатора формирају на основу правила граматике и, евентуално, предувидног симбола, њихов садржај може бити различит. Таблице анализе су ЛР(0) ако су формиране без обзира на предувидни симбол, а у процесу анализе навише се не јављају конфликти. ЛР(0) анализатор је анализатор за ЛР(0) граматике, који чита улаз са лева на десно.

Конструисање ЛР(0)-таблице анализе

Конкретна граматика коју ћемо користити као пример:

(1) Е → Е * B

(2) Е → Е + B

(3) Е → B

(4) B → 0

(5) B → 1

Ајтеми

Конструкција таблица за ЛР(0) анализатор је заснована на ЛР(0) ајтемима (овде ћемо их једноставно звати ајтеми). Ајтеми су граматичка правила која садрже метасимбол . (тачка), додат негде на десној страни правила. На пример правило Е → Е + B има четири одговарајућа наредна ајтема:

Е → • Е + B

Е → Е • + B

Е → Е + • B

Е → Е + B •

Правила облика А → ε имају само један ајтем А → •. Ова правила ће бити коришћена да одреде стање анализатора. Ајтем Е → Е • + B, на пример, указује да је анализатор препознао на улазу ниску која се изводи из нетерминала Е, и да очекује да прочита '+' , а затим ниску која се изводи из нетерминала B.

Формирање стања анализатора помоћу ајтема

Обично је немогуће формирати стање анализатора само помоћу једног ајтема зато што се не може унапред знати, за то стање, које правило ће се користити при пребацивању. На пример, ако постоји и правило Е → Е * B онда ће оба ајтема, Е → Е • + B и Е → Е • * B, бити применљива после ниске која је прочитана са улаза и изводи се из Е. Зато формирање стања анализатора вршимо скупом ајтема, у овом случају скупом { Е → Е • + B, Е → Е • * B }.

Затворење скупа ајтема

Ајтем са тачком испред нетерминала, као Е → Е + • B, указује на то да анализатор очекује да му се проследи нетерминал B тј. очекује на улазу ниску која се изводи из B. Да би скуп ајтема сигурно садржао сва могућа правила која се могу користити током анализе, морају му се додати сви ајтеми који садрже извођења из B. То значи да ако у граматици постоји правило као B → 1 и B → 0 онда скуп ајтема мора садржати и ајтеме B → • 1 анд B → • 0. Овај поступак се може формално исказати на следећи начин:

Ако неки скуп ајтема садржи ајтем облика А → в • Bw и у граматици постоји правило облика B → w' , онда се скупу мора додати ајтем B → • w' .

Сваки скуп ајтема може бити проширен тако да задовољава следеће правило: наставља се са додавањем одговарајућих ајтема све док сви нетерминали испред којих је тачка нису убројани. Минимално проширење се назива затворење скупа ајтема и обележава се са clos(I) где је I скуп ајтема. Ова затворења скупова ајтема се узимају за стања анализатора, иако ће само она која су достижна из почетног стања бити укључена у таблицу.

Проширена граматика

Пре него сто се почне са одређивањем ( детерминизацијом) прелаза између различитих стања, граматика се увек прошири додатним правилом

(0) S → Е

где је S нови почетни симбол, а Е стари почетни симбол. Анализатор ће користити ово правило само за свођење(редукцију) када је улазна ниска прихваћена.

За поменути пример овако изгледа постојећ проширена граматика:

(0) S → Е

(1) Е → Е * B

(2) Е → Е + B

(3) Е → B

(4) B → 0

(5) B → 1

За ову проширену грамтику праве се скупови ајтема и прелази између њих.

Конструкција таблице

Одређивање достижних скупова ајтема и прелаза између њих

Први корак у конструкцији таблице је одређивање прелаза између затворења скупова ајтема (између стања анализатора). Ови прелази се одређују као да разматрамо коначан аутомат који може да чита терминале, као и нетерминале. Почетно стање аутомата је увек затворење првог ајтема додатог правила: S → • Е:

Скуп ајтема (стање) 0

S → • Е

+ Е → • Е * B

+ Е → • Е + B

+ Е → • B

+ B → • 0

+ B → • 1

Подебљано "+" испред ајтема означава ајтеме који су додати да би се конструисало затворење (не треба га мешати са математичким оператором '+' који је терминал тј. завршни симбол). Оригинални ајтеми без "+" зову се језгра скупа ајтема.

Почевси са стањем 0 одређују се сва стања која су из њега достижна. Могући прелази за скуп стања проналазе се посматрајући симболе ( терминале или нетерминале) који се налазе иза метасимбола .; У случају стања 0 то су терминали '0' и '1' и нетерминали Е и B. Да би се одредио скуп ајтема до кога води симбол x, прати се следећа процедура:

Узима се скуп S, свих оних ајтема који се налазе у тренутном скупу, а који имају . испред симбола x.
За сваки ајтем у S, тачка се помера десно од x.
Формира се затворење добијеног скупа ајтема.

За терминал '0' се добија:

Стање 1

B → 0 •

и за терминал '1':

Стање 2

B → 1 •

и за нетерминал Е:

Стање 3

S → Е •

Е → Е • * B

Е → Е • + B

и за нетерминал B:

Стање 4

Е → B •

Може се приметити да се приликом формирања затворења не додају увек нови ајтеми. Овај процес се наставља све док се могу формирати нови скупови ајтема тј. стања. За стања 1, 2, и 4 неће бити јос прелаза јер нема тачке ни испред једног симбола. У стању 3 тачка је испед терминала '*' и '+'. За '*' прелаз изгледа овако:

Стање 5

Е → Е * • B

+ B → • 0

+ B → • 1

а за '+' изгледа овако:

Стање 6

Е → Е + • B

+ B → • 0

+ B → • 1

За стање 5 треба разматрати терминале ‘0’ и ‘1’ и нетерминал B. За терминале се примећује да се формира затворење које је једнако затворењима скупова ајтема која већ постоје. То су стања 1 и 2, респективно. За нетерминал B прелаз изгледа овако:

Стање 7

Е → Е * Б •

За стање 6 треба разматрати терминале '0' и '1' и нетерминал Б. Као и раније, за терминале се формира затворење које једнако затворењима скупова ајтема које већ имамо. То су стања 1 и 2. За нетерминал B прелаз изгледа овако:

Стање 8

Е → Е + B •

Коначно, ово стање нема симбола испред којих је тачка, па нема више стања која се могу додати и процес је завршен. Таблица прелаза за анализатор (аутомат) сада изгледа овако:

Стање	*	+	0	1	Е	Б
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

Конструкција ACTION/GOTO таблица

Од таблице која је већ конструисана и од скупова ајтема прави се ACTION/GOTO таблица на следећи начин:

колоне за нетерминале се препишу у GOTO део таблице
колоне за терминале се препишу у ACTION део таблице као акције пребацивања (shift)
додаје се нова колона за маркер краја улаза '$' у ACTION део таблице, која садржи acc(прихватање) за свако стање које садржи ајтем S → Е .
Ако неки скуп ајтема садржи ајтем облика А → w • и А → w је правило које смо обележили са м (где је м > 0) онда се ред за стање и у ACTION делу таблице комплетно попуњава акцијом свођења (reduce) тј. обележава се са рм.

Чилталац може да провери да када се примене наведена правила конструкције добија се ACTION/GOTO таблица која је овде представљена.

Примећује се да само корак 4. из претходне процедуре доводи до примене акције свођења, и да све акције свођења морају заузети читав ред табеле, сто значи да се врши свођење без обзира на то који ће се симбол наћи на улазу. Ово је зато што су ово баш ЛР(0) таблице анализе: оне не користе предувидне симболе у одлучивању која ће се акција наредна извршити. Граматике које користе предувидне симболе у одлучивању о наредној акцији, морају имати таблице анализе које ће садржати у редовима различите акције свођења за различите колоне. Горња процедура не омогућава прављење оваквих редова.

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

Конфликти у добијеним таблицама

Анализатор је конструисан на такав начин да је осигурано да он буде детерминистицки. Међутим, када се у ACTION таблицу додају акције свођења, може се десити да је иста ћелија таблице попуњена и акцијом свођења и акцијом пребацивања ( такозвани пребацивање-свођење конфликт) или са две акције свођења (свођење - свођење конфликт). Може се показати да када се ово деси то значи да граматика није ЛР(0).

Једноставан пример једне граматике која није ЛР(0) са пребацивање - свођење конфликтом :

(1) Е → 1 Е

(2) Е → 1

Један од скупова ајтема које се појављују је:

Стање 1

Е → 1 • Е

Е → 1 •

+ Е → • 1 Е

+ Е → • 1

Овде се јавља пребацивање - свођење конфликт јер у ACTION таблици за ово стање и терминал '1' мозе се извршити акција пребацивања у стање 1 и акција свођења по правилу 2.

Једноставан пример једне граматике која није ЛР(0) са свођење - свођење конфликтом :

(1) Е → А 1

(2) Е → Б 2

(3) А → 1

(4) Б → 1

У овом случају добијамо следећи скуп ајтема:

Стање 1

А → 1 •

Б → 1 •

Овде се јавља свођење - свођење конфликт јер у ACTION таблици за ово стање и терминал '1' може се извршити акција свођења по правилу 3, као и по правилу 2.

Оба наведена примера се могу решити помоћу предувидног симбола и претходне анализе, коришћењем скупова Следи (Follow) за нетерминале. На тај начин се формирају СЛР анализатори.