Kanonski LR analizator

Kanonski LR analizator ili LR(1) je LR-analizator čije se tabice analize konstruišu slično kao kod LR(0) analizatora osim što ajtemi u ajtem-skupovima takođe sadrže i Sledeći tj. terminal koji analizator očekuje posle desne strane pravila. Skup Sledeći(A) za dati neterminal A sadrži sve završne simbole koji se mogu pojaviti neposredno iza simbola A, bez obzira na kontekst. Na primer, za pravilo A → B C ajtem bi mogao biti

A → B · C, a

što znači da je analizator pročitao nisku kojoj odgovara neterminal B, da očekuje nisku kojoj odgovara neterminal C iza koga sledi terminal 'a'. LR(1) analizator može da obradi veoma veliku klasu gramatika, međutim problem je što su često tablice analize jako velike. To se najčešće rešava spajanjem ajtem-skupova ukoliko su identični do na Sledeći. To su onda LALR-analizatori.

Konstruisanje LR(1) analizatora

LR(1)-ajtem se sastoji od

LR(0)-ajtema A→α•β

i

preduvidnog simbola x

a obično se predstavljaju u obliku

A→α•β ,x

Intuitivno, takav ajtem nam govori koliko smo do sada pročitali (α), šta možemo da očekujemo (β), i preduvid koji se slaže sa onim što bi sledilo ukoliko bismo izvršili svođenje po pravilu A→α•β. Time što smo dodali preduvidnu informaciju pri formiranju ajtema, omogućava nam da donesemo pametniju odluku o svođenju. Preduvid LR(1)-ajtema je direktno koristi jedino kad razmišljamo o akciji svođenja (na primer, kad je metasimbol • sa desnom kraju).

Jezgro LR(1)-ajtema (A→α•β ,x ) je LR(0)-ajtem (A→α•β). Različiti LR(1)-ajtemi mogu imati isto jezgro, a razlikovati se zbog preduvidnog simbola. Koristimo prednost tog preduvidnog simbola da odlučimo koje svođenje da koristimo. (Jer bi ista situacija kod SLR analizatora možda dovela do svođenje/svođenje konflikta.)

Početni ajtem

Uvodimo početni ajtem

[S’ → · S, ┤].

Oznaka ┤ označava kraj ulaza.

Pravilo zatvorenja

Ako stanje sadrži ajtem:

[A → α · B β, a]

onda su u tom stanju i ajtemi oblika :

[B → · γ, Prvi(βα)]

za svako B-pravilo gramatike.

Pravilo prelaza

Pravilo prelaza je ostalo isto. Ako neko stanje sadrži ajtem:

[A → α · B β, a]

tada postoji prelaz po simbolu B iz stanja koje sadrži taj ajtem u stanje koje sadrži ajtem:

[A → α B · β, a]

Akcija prebacivanja

Akcije prebacivanja se takođe nisu menjale. Ukoliko je ajtem [A → α · b β, a] u stanju Ik i Ik prelazi u stanje Ij po simbolu 'b', onda dodajemo akciju :

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

Akcija Svođenja

Ukoliko je [A → α · , a] u stanju Ik, onda dodajemo akciju (svođenje, A→α). Primetimo da se više ne koristi informacija iz skupa Sledeci(A).

Primer

Za gramatiku izraza:

T

T→T * F

|F

F→( E )

|a

početni ajtem je:

S→•E {┤}

a graf za skup Prvi: S → E → T → F → (,b

tj. Prvi( E ) = Prvi( T ) = Prvi( F ) = { (, b }

Početni ajtem se nalazi u stanju 0. Primenjujući na njega pravilo zavorenja dobijamo: Stanje 0:

S→•E {┤}

E→•E+T {┤}

E→•T {┤}

Međutim, pravilo zatvorenja se sad primenjuje na dodate ajteme. Time dobijamo da je Stanje 0:

S→•E {┤}

E→•E+T {┤}

E→•T {+}

E→•E+T {+}

E→•T {┤}

T→•T * F {┤}

Ovo i dalje nije potpuno stanje 0, jer se postupak nastavlja sve dok nijedan novi LR(1)-ajtem ne može da se doda stanju 0. Drugim rečima,prva tri stanja izgledaju:

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 slično za ostala stanja.