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
- A→
Intuitivno, takav ajtem nam govori koliko smo do sada pročitali (
Jezgro LR(1)-ajtema (A→
Početni ajtem
[уреди | уреди извор]Uvodimo početni ajtem
- [S’ → · S, ┤].
Oznaka ┤ označava kraj ulaza.
Pravilo zatvorenja
[уреди | уреди извор]Ako stanje sadrži ajtem:
- [A →
α · Bβ , a]
- [A →
onda su u tom stanju i ajtemi oblika :
- [B → ·
γ , Prvi(β α )]
- [B → ·
za svako B-pravilo gramatike.
Pravilo prelaza
[уреди | уреди извор]Pravilo prelaza je ostalo isto. Ako neko stanje sadrži ajtem:
- [A →
α · Bβ , a]
- [A →
tada postoji prelaz po simbolu B iz stanja koje sadrži taj ajtem u stanje koje sadrži ajtem:
- [A →
α B ·β , a]
- [A →
Akcija prebacivanja
[уреди | уреди извор]Akcije prebacivanja se takođe nisu menjale. Ukoliko je ajtem [A →
- T[k ,a]=(prebacivanje, j )
Akcija Svođenja
[уреди | уреди извор]Ukoliko je [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.