12/4/2014 1
Gramatici LR(k)
• analizoare LR(k)
- analiza sintactica ascendenta
- secv. de intrare este citita de la stanga spre dreapta
- se folosesc derivari de dreapta
metoda: deplasare - reducere
12/4/2014 4
Definitie: Gramatica LR(K)
Daca S – nu apare in m.d. al unei r.p.:
si daca:
• S =*>dr a A w =>dr a b w
• S =*>dr g B x =>dr a b y
• FIRSTk(w) = FIRSTk(y)
atunci:
• A = B
• x = y
• a = g
12/4/2014 5
Gramatici LR(K) - terminologie
Prefix viabil
Fie: S =*>dr a A w =>dr a b w
Orice prefix al lui ab se numeste prefix viabil
Element de analiza
se defineste ca fiind: [A→a.b, u]
unde A→ab P si |u|=k
Element de analiza valid
[A→a.b, u] valid pentru prefixul viabil ga daca:
– S =*>dr g A w =>dr g a b w
– u = FIRSTk(w)
12/4/2014 7
Colectia canonica LR(K)
C = {Ii-elementele de analiza pentru un prefix viabil}
• in I0 avem un prim element de analiza
• am un element din Ij (pentru fiecare)
=> le construiesc pe celelalte: functia Closure
• am o multime Ij (pentru fiecare)
=> construiesc multimile goto(Ii,X)
Terminologie: Ii – stare a automatului
Notatie: E – multimea elementelor de analiza
12/4/2014 8
K=0: LR(0)
12/4/2014 9
Gramatica imbogatita
• se adauga S’
– nou simbol de start
– S’→S
12/4/2014 10
Constructia colectiei canonice LR(0)
C = {Ii-elementele de analiza pentru un prefix viabil}
in I0 avem: [S’ → .S]
• I0 = Closure ([S’ → .S])
• C = { I0 }
• repeta
pentru toti Ii din C , X(N U S) executa
C = C U goto (Ii,X)
sf. pentru
pana cand C nu se mai modifica
12/4/2014 11
Functia Closure LR(0)
• Closure : Part(E) → Part(E)
• Fie: e E
daca e = [A → a . Bb]
atunci B→ d P: [B → . d] Closure (e)
12/4/2014 12
Functia goto LR(0)
• goto : Part(E) x (N U S) → Part(E)
• goto(I,X) = Closure({[A→aX.b] | [A→a.Xb] I})
12/4/2014 14
Tabelul de analiza LR(0)
• T(Ii, actiune) =
– s (shift, deplasare)
daca: [A→a.b] Ii , b <>e
si: T(Ii, X) = Ij, daca Ij = goto(Ii,X)
– L (reducere cu r.p. nr. L)
daca [A→a.] Ii
A→a P : regula de prod. cu numarul L
si: T(Ii, X) nu se completeaza
– acc daca: [S’ → S.] Ii
Toate celelalte cazuri se considera eroare .
12/4/2014 15
Automatul LR(0) – model matematic
• configuratie:
(a,b,P)
(stiva_de_lucru, banda_de_intrare, banda_de_iesire)
• pe stiva: prefixe viabile, stari ale analizorului
• config. initiala: ($0,w$, e)
• config. finala: ($0S Iacc , $, P)
12/4/2014 16
Automatul LR(0) – model matematic
Tranzitii
• deplasare:
($ g sk , ai..an$ , P) ├─ ($g skaism , ai+1…an$ , P)
daca: T(sk,action) = s si T(sk,ai) = sm
• reducere
($ g sp-1Xpsp… Xksk, ai..an$,P)├─ ($gsp-1A sm, ai…an$, LP)
daca: T(sk,action) = L
si: A → Xp… Xk – r.p. cu nr. L
T(sp-1, action) = s
T(sp-1, A) = sm
• acceptare: ( $ 0S sacc , $ , P ) ├─ acc.
• eroare: orice alta situatie
12/4/2014 17
• Gramatica data prin urmatoarele r.p. este LR(0) ?
S → Ax
S → By
A → a
B → a
12/4/2014 18
Constructia colectiei canonice LR(k)
C = {Ii-elementele de analiza pentru un prefix viabil}
in I0 avem: [S’ → .S , …]
• I0 = Closure ([S’ → .S , …])
• C = { I0 }
• repeta
pentru toti Ii din C , X(N U S) executa
C = C U goto (Ii,X)
sf. pentru
pana cand C nu se mai modifica
12/4/2014 19
Analiza SLR
• SLR = Simple LR
• element de analiza LR(1):
– [A→a.b, u], |u| =1
– element de analiza SLR:
u = FOLLOW1(A)
• SLR: tine cont de predictie numai pentru reducere
12/4/2014 20
Analiza sintactica SLR
• constructia colectiei canonice (~LR(0))
– [A→a.b, u] , u = FOLLOW1(A)
• constructia tabelului de analiza SLR
– actiunea de reducere depinde de predictia u
=>reducerea va avea o coloana pentru fiecare a S
tabelul: linii: elementele colectiei canonice
coloane: N U S U {$}
celula: sstare,rnr.r.p, acc
• analizorul ~ analizorul pt. LR(0)
automat: configuratii si tranzitii
12/4/2014 21
Analiza LR(1)
• constructia colectiei canonice
element de analiza LR(1):
– [A→a.b, u], |u| =1
• constructia tabelului de analiza
• analiza sintactica
12/4/2014 22
Colectia canonica LR(1)
• elem. initial
[S’ → .S , $]
• Closure
[A → a.Bb, a] =>[B →.g, b]Closure([A→a.Bb, a])
B → g b FIRST1(ba)
• goto
goto (I,X) =
Closure ({[A→aX.b,a] | [A→a.Xb,a] I })
12/4/2014 23
Tabelul de analiza LR(1)
actiune: reducere + goto
X S U {$} X N U S
linii: elementele colectiei canonice
coloane: N U S U {$}
12/4/2014 24
Construirea tab. de analiza LR(1)
• [A→a.Xb,b] Ii : goto (Ii,X) = I j <= functia goto
action(Ii,X) = sj
• [A→a. , a] Ii action(Ii,a) = rL
L – nr. reg. de productie: A → a
A <> S’
• [S’ → S., $] Ii action(Ii,$) = acc
Obs: o gram. este LR(1) daca tabelul de analiza nu
contine conflicte; si reciproc
12/4/2014 25
.
• analizorul LR(1)
• analiza LR(1)
12/4/2014 26
Analiza LALR
• [A → a.b , a ]
nucleu
• colectia canonica LR(1)
• fuzioneaza elementele de analiza cu nuclee identice
si care nu creeaza conflicte
• predictia: reuniunea predictiilor
12/4/2014 27
LR (1 –uri)
• Conflict:
[ A → a1.aa2 , u ]
[ B → b1. , a ]
[ A → a1. , a ]
[ B → b1. , a ]