Канонски ЛР анализатор

Канонски ЛР анализатор или ЛР(1) је ЛР-анализатор чије се табице анализе конструишу слично као код ЛР(0) анализатора осим што ајтеми у ајтем-скуповима такође садрже и Следећи тј. терминал који анализатор очекује после десне стране правила. Скуп Следећи(A) за дати нетерминал A садржи све завршне симболе који се могу појавити непосредно иза симбола A, без обзира на контекст. На пример, за правило A → B C ајтем би могао бити

A → B · C, a

што значи да је анализатор прочитао ниску којој одговара нетерминал B, да очекује ниску којој одговара нетерминал C иза кога следи терминал 'a'. ЛР(1) анализатор може да обради веома велику класу граматика, међутим проблем је што су често таблице анализе јако велике. То се најчешће решава спајањем ајтем-скупова уколико су идентични до на Следећи. То су онда ЛАЛР-анализатори.

Конструисање ЛР(1) анализатора

ЛР(1)-ајтем се састоји од

ЛР(0)-ајтема A→α•β

и

предувидног симбола x

а обично се представљају у облику

A→α•β ,x

Интуитивно, такав ајтем нам говори колико смо до сада прочитали (α), шта можемо да очекујемо (β), и предувид који се слаже са оним што би следило уколико бисмо извршили свођење по правилу A→α•β. Тиме што смо додали предувидну информацију при формирању ајтема, омогућава нам да донесемо паметнију одлуку о свођењу. Предувид ЛР(1)-ајтема је директно користи једино кад размишљамо о акцији свођења (на пример, кад је метасимбол • са десном крају).

Језгро ЛР(1)-ајтема (A→α•β ,x ) је ЛР(0)-ајтем (A→α•β). Различити ЛР(1)-ајтеми могу имати исто језгро, а разликовати се због предувидног симбола. Користимо предност тог предувидног симбола да одлучимо које свођење да користимо. (Јер би иста ситуација код СЛР анализатора можда довела до свођење/свођење конфликта.)

Почетни ајтем

Уводимо почетни ајтем

[S’ → · S, ┤].

Ознака ┤ означава крај улаза.

Правило затворења

Ако стање садржи ајтем:

[A → α · B β, a]

онда су у том стању и ајтеми облика :

[B → · γ, Први(βα)]

за свако B-правило граматике.

Правило прелаза

Правило прелаза је остало исто. Ако неко стање садржи ајтем:

[A → α · B β, a]

тада постоји прелаз по симболу B из стања које садржи тај ајтем у стање које садржи ајтем:

[A → α B · β, a]

Акција пребацивања

Акције пребацивања се такође нису мењале. Уколико је ајтем [A → α · b β, a] у стању Ik i Ik прелази у стање Iј по симболу 'б', онда додајемо акцију :

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

Акција Свођења

Уколико је [A → α · , a] у стању Ik, онда додајемо акцију (свођење, A→α). Приметимо да се више не користи информација из скупа Следеци(A).

Пример

За граматику израза:

T

T→T * F

|F

F→( E )

|a

почетни ајтем је:

S→•E {┤}

а граф за скуп Први: S → E → T → F → (,b

тј. Први( E ) = Први( T ) = Први( F ) = { (, b }

Почетни ајтем се налази у стању 0. Примењујући на њега правило заворења добијамо: Стање 0:

S→•E {┤}

E→•E+T {┤}

E→•T {┤}

Међутим, правило затворења се сад примењује на додате ајтеме. Тиме добијамо да је Стање 0:

S→•E {┤}

E→•E+T {┤}

E→•T {+}

E→•E+T {+}

E→•T {┤}

T→•T * F {┤}

Ово и даље није потпуно стање 0, јер се поступак наставља све док ниједан нови ЛР(1)-ајтем не може да се дода стању 0. Другим речима,прва три стања изгледају:

Stanje 0:

S→•E {┤}

E→•E+T {┤,+}

E→•T {┤,+}

T→•T * F {┤,+,*}

T→•F {┤,+,*}

F→•(E) {┤,+,*}

F→•b {┤,+,*}

Stanje 1:

S→E• {┤}

E→E•+T {┤,+}

Stanje 2:

E→T• {┤,+}

T→T• * F {┤,+,*}

I слично за остала стања.