Канонски ЛР анализатор
Канонски ЛР анализатор или ЛР(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 слично за остала стања.