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 ]