Gramatici LR(0)

(1)

Curs 9

1

Limbaje formale, automate şi

compilatoare

(2)

Recapitulare



Gramatici LR(0)

 Teorema de caracterizare LR(0)

 Automatul LR(0)

 Parserul LR(0)



FIRST, FOLLOW



Gramatici SLR(1)

(3)

Parser ascendent general

3

Control Tabela de parsare

a₁ ... a_i ... a_n #

X₁ X₁ ...

#

p₁ p₂ ...

(4)

Mulţimile FIRST şi FOLLOW



FIRST(α) = {a|a

∈

T, α

_st

⇒* au } ∪

if (α

_st

⇒*

^ε

) then {

ε

} else ∅.



FOLLOW(A) = {a|a

∈

T ∪ { ε }, S

_st

⇒* uAγ,

a

∈

FIRST (γ) }

(5)

Determinare FIRST

5

 1.for(X ∈ Σ)

 2.if(X ∈ T)FIRST(X)={X} else FIRST(X)=∅;

 3.for(A→aβ ∈ P)

 4.FIRST(A)=FIRST(A)∪{a};

 5.FLAG=true;

 6.while(FLAG){

 7.FLAG=false;

 8.for(A → X₁X₂…X_n∈ P){

 9.i=1;

 10.if((FIRST(X1) ⊈ FIRST(A)){

 11.FIRST(A)=FIRST(A)∪(FIRST(X1)-{ε});

 12.FLAG=true;

 13.}//endif

 14.while(i<n && X_i_st⇒* ε)

 15.if((FIRST(X_i+1) ⊈ FIRST(A)){

o 16.FIRST(A)=FIRST(A)∪FIRST(X_i+1);

o 17.FLAG=true;i++;

 }//endif

 }//endwhile

 }//endfor

 }//endwhile

 for(A ∈N)

 if(A_st⇒* ε)FIRST(A)=FIRST(A)∪{ε};

(6)

Determinare FIRST

 Intrare: Gramatica G=(N,T,S,P).

 Mulţimile FIRST(X),X ∈ Σ.

 α =X₁X₂…X_n, X_i ε Σ,1≤i≤n.

 Ieşire: FIRST(α).

 1.FIRST(α)=FIRST(X₁)-{ε};i=1;

 2.while(i<n && X_i ⇒⁺ ε){

 3.FIRST(α)=FIRST(α)∪(FIRST(X_i+1)-{ε});

 4.i=i+1;

 }//endwhile

 5.if(i==n && X_n ⇒⁺ ε)

 6.FIRST(α)=FIRST(α)∪ {ε};

(7)

Exemplu

P şi β ⇒

⁺

ε, atunci FOLLOW(A) ⊆

FOLLOW(B).

(9)

Determinarea FOLLOW

9

 1. for(A ∈ Σ)FOLLOW(A)=∅;

 2.FOLLOW(S)={ε};

 3.for(A → X₁X₂…X_n){

 4.i=1;

 5.while(i<n){

 6.while(X_i ∉ N)++i;

 7.if(i<n){

 8.FOLLOW(Xi)= FOLLOW(X_i)∪

(FIRST(X_i+1X_i+2…X_n)-{ε});

 9.++i;

 }//endif

 }//endwhile

 }//endfor

(10)

Determinarea FOLLOW

 10.FLAG=true;

 11.while(FLAG){

 12.FLAG=false;

 13.for(A → X₁X₂…X_n){

 14.i=n;

 15.while(i>0 && X_i ∈ N){

 16.if(FOLLOW(A) ⊄ FOLLOW(X_i)){

o 17.FOLLOW(Xi)=FOLLOW(X_i) ∪ FOLLOW(A);

o 18.FLAG=true;

 19.}//endif

 20.if(X_i⇒⁺ε)--i;

 21.else continue;

 22.}//endwhile

 23.}//endfor

 24.}//endwhile

(11)

Exemplu

11



Fie gramatica:



S → E | B, E → ε, _B ^→ a | begin SC end, C →

ε

|

automatului LR(0) sunt îndeplinite condiţiile:

 –Dacă A→α∙, B → β∙ ∈ t,

atunci FOLLOW(A)∩FOLLOW(B) = ∅;

 –Dacă A→α∙, B → β∙aγ ∈ t atunci a ∉ FOLLOW(A).

(13)

Gramatici SLR(1)

13



Analiza sintactică SLR(1) este similară cu cea LR(0);

tabela de analiză sintactică are două componente:

 –Prima, numită ACŢIUNE, determină dacă parserul va face deplasare respectiv reducere, în funcţie de starea ce se află în vârful stivei şi de simbolul următor din intrare

 –Cea de a doua, numită GOTO, determină starea ce se va adăuga în stivă în urma unei reduceri.

(14)

Construcţia tabelei de parsare SLR(1)



Intrare:

 Gramatica G = (N, T, S, P) augmentată cu S’ → S;

 Automatul M = (Q, Σ, g, t₀, Q );

 Mulţimile FOLLOW(A), A∈N



Ieşire:

 Tabela de analiză SLR(1) compusă din două părţi:

 ACŢIUNE(t, a), t ∈ Q, a ∈ T ∪ { # },

 GOTO(t, A), t ∈ Q, A ∈ N.

(15)

Construcţia tabelei de parsare SLR(1)

15

 for(t ∈ Q)

 for (a ∈ T) ACTIUNE(t, a) = “eroare”;

 for (A ∈ V) GOTO(t, A) = “eroare”;

 for(t ∈ Q}{

 for(A→ α∙aβ ∈ t)

 ACTIUNE(t,a)=“D g(t, a)”;//deplasare in g(t, a)

 for(B→ γ∙ ∈ t ){// acceptare sau reducere

 if(B == ‘S’) ACTIUNE(t, #) = “acceptare”;

 else

 for(a ∈ FOLLOW(B)) ACTIUNE(t,a)=“R B→γ”;

 }// endfor

 for (A ∈ N) GOTO(t, A) = g(t, A);

 }//endfor

(16)

Parsarea SLR(1)

 Deplasare: (σt, au#, π)⊢(σtt’, u#, π) dacă ACTIUNE(t, a)=Dt’;

 Reducere: (σtσ’t’, u#, π)⊢( σtt’’, u#, πr) ACTIUNE(t, a) = R_p unde p= A → β, |σ’t’| = |β| şi t’’= GOTO(t, A);

 Acceptare: (t₀t, #, π) dacă ACTIUNE(t,a) = “acceptare”; Analizorul se opreşte cu acceptarea cuvântului de analizat iar π este parsarea acestuia (şirul de reguli care s-a aplicat, în ordine inversă, în

derivarea extrem dreaptă a lui w).

 Eroare: (σ t, au#, π) ⊢ eroare dacă ACTIUNE(t,a) = “eroare”;

Analizorul se opreşte cu respingerea cuvântului de analizat.

(17)

Parsarea SLR(1)

17



Intrare:

 Gramatica G = (N, T, S, P) care este SLR(1) ;

 Tabela de parsare SLR(1) ( ACTIUNE, GOTO);

 Cuvântul de intrare w ∈ T*.



Ieşire:

 Analiza sintactică (parsarea) ascendentă a lui w dacă w∈L(G);

 eroare, în caz contrar.



Se foloseşte stiva St pentru a implementa tranziţiile

deplasare/reducere

(18)

Parsarea SLR(1)

 char ps[] = “w#”; //ps este cuvantul de intrare w

 int i = 0; // pozitia curenta in cuvantul de intrare

 St.push(t0); // se initializeaza stiva cu t0

 while(true) { // se repeta pana la succes sau eroare

 t = St.top();

 a = ps[i] // a este simbolul curent din intrare

 if(ACTIUNE(t,a) == “acceptare”) exit(“acceptare”);

 if(ACTIUNE(t,a) == “Dt‟”){

 St.push(t‟);

 i++; // se inainteaza in w

 }//endif

 else {

 if(ACTIUNE(t,a) == “R A → X₁X₂…X_m”){

 for( i = 1; i ≤m; i++) St.pop();

 St.push(GOTO(St.top, A));

 } //endif

 else exit(“eroare”);

 }//endelse

(19)

Exemplu

19

 0.S → E, 1.E → E+T, 2.E → T, 3.T → T*F, 4.T → F, 5.F →(E), 6.F → a

(20)

Tabela de tranziţie a automatului LR(0)

a + * ( ) E T F

0 5 4 1 2 3

1 6

2 7

3

4 5 4 8 2 3

5

6 5 4 9 3

7 5 4 10

8 6 11

9 7

10

(21)

Test SLR(1)

21



G nu este LR(0) stările 1, 2, 9 conţin conflict de deplasare/reducere



FOLLOW(S)={#}, FOLLOW(E)={#,+,)}



Gramatica este SLR(1) pentru că:

 în starea 1: + ∉ FOLLOW(S);

 în starea 2: * ∉ FOLLOW(E);

 în starea 9: * ∉ FOLLOW(E).

(22)

Tabela de analiză SLR(1)

Stare ACTIUNE GOTO

a + * ( ) # E T F

0 D5 D4 1 2 3

1 D6 accept

2 R2 D7 R2 R2

3 R4 R4 R4 R4

4 D5 D4 8 2 3

5 R6 R6 R6 R6

6 D5 D4 9 3

7 D5 D4 10

8 D6 D11

9 R1 D7 R1 R1

10 R3 R3 R3 R3

(23)

Stiva Intrare Actiune Iesire

0 a*(a+a)# deplasare

05 *(a+a)# reducere 6.F → a

03 *(a+a)# reducere 4.T → F

02 *(a+a)# deplasare

027 (a+a)# deplasare

0274 a+a)# deplasare

02745 +a)# reducere 6.F → a

02743 +a)# reducere 4.T → F

02742 +a)# reducere 2.E → T

02748 +a)# deplasare

23

(24)

Stiva Intrare Actiune Iesire

027486 a)# deplasare

0274865 )# reducere 6.F → a

0274863 )# reducere 4.T → F

0274869 )# reducere 1.E → E+T

02748 )# deplasare

02748(11) # reducere 5.F →(E)

027(10) # reducere 3.T → T*F

02 # reducere 2.E → T

01 # acceptare

(25)

Gramatici LR(1)

25

 Definiţie

 Fie G = (V, T, S, P) o gramatică redusă. Un articol LR(1) pentru

gramatica G este o pereche (A → α∙β, a), unde A → αβ este un articol LR(0), iar a ∈FOLLOW(A) (se pune # în loc de ε).

 Definiţie

 Articolul (A → β₁∙β₂, a) este valid pentru prefixul viabil αβ₁dacă are loc derivarea

 S dr⇒*αAu ⇒ αβ₁β₂u

 iar a = 1:u (a = # dacă u = ε).

 Teorema

 O gramatică G = (V, T, S, P) este gramatică LR(1) dacă şi numai dacă oricare ar fi prefixul viabil φ, nu există două articole distincte, valide pentru φ, de forma(A → α∙, a), (B →β∙γ, b) unde a ∈ FIRST(γb).

(26)

Gramatici LR(1)

 Nu există conflict deplasare/reducere. Un astfel de conflict înseamnă două articole (A → α∙, a) şi (B → β∙aβ’, b) valide pentru acelaşi prefix.

 Nu există conflict reducere/reducere. Un astfel de conflict

înseamnă două articole complete(A → α∙, a) şi (B → β∙, a) valide pentru acelaşi prefix

 Pentru a verifica dacă o gramatică este LR(1) se construiește automatul LR(1) în mod asemănător ca la LR(0):

 Automatul are ca stări mulțimi de articole LR(1)

 Tranzițiile se fac cu simboluri ce apar după punct

 Închiderea unei mulțimi de articole se bazează pe faptul că dacă articolul (B → β∙Aβ’, b) este valid pentru un prefix viabil atunci toate articolele de forma (A → ∙α, a), unde a ∈FIRTS(β’b) sunt valide pentru același prefix.

(27)

Procedura de închidere LR(1)

27

 flag= true;

 while( flag) {

 flag= false;

 for ( (A→ α∙Bβ, a) ∈ I) {

 for B → γ ∈ P)

 for( b ∈ FIRST(βa)){

o if( (B → ∙γ , b) ∉ I) {

• I = I∪{(B → ∙γ , b)};

• flag= true;

o }//endif

 }//endforb

 }//endforB

 }//endforA

 }//endwhile

 return I;

(28)

Automatul LR(1)

 t0 = închidere((S’ →

∙

^S,#));T={t0};marcat(t₀)=false;

 while(∃ t∈T&& !marcat(t)){ // marcat(t) = false

 for( X ∈ Σ) {

 t’ = Φ;

 for( (A→ α∙Xβ ,a) ∈ t )

 t’ = t’ ∪{(B→ αX∙β ,a) | (B B→ α∙Xβ,a) ∈ t};

 if( t’ ≠ Φ){

o t’ = închidere( t’ );

o if( t’T) {

• T= T ∪{ t’ };

• marcat( t’ ) = false;

o }//endif

o g(t, X) = t’;

 } //endif

 } //endfor

(29)

Automatul LR(1)

29

 Teorema

 Automatul M construit în algoritmul 2 este determinist şi L(M) coincide cu mulţimea prefixelor viabile ale lui G. Mai mult, pentru orice prefix viabil γ, g(t₀,γ) reprezintă mulţimea articolelor LR(1) valide pentru γ.

 Automatul LR(1) pentru o gramatică G, se foloseşte pentru a verifica dacă G este LR(1)

 Conflict reducere/reducere: Dacă în T există o stare ce conţine articole de forma (A → α∙, a), (B → β∙, a) atunci gramatica nu este LR(1);

 Conflict deplasare/reducere: Dacă în Texistă o stare ce conţine articole de forma (A → α∙, a) şi (B → β₁∙aβ₂, b), atunci G nu este LR(1).

 O gramatică este LR(1) dacă orice stare t ∈Teste liberă de conflicte

(30)

Exemplu

 S

→

_{L=R|R, L}

→

_{*R|a, R}

→

_L

(31)

Tabela de tranziţie

31

(32)

Construcţia tabelei de analiză LR(1)

 for(t ∈ T)

 for (a ∈ T) ACTIUNE(t, a) = “eroare”;

 for (A ∈ V) GOTO(t, A) = “eroare”;

 for(t ∈ T}{

 for((A→ α∙aβ, L) ∈ t)

 ACTIUNE(t,a)=“D g(t, a)”;//deplasare in g(t, a)

 for((B→ γ∙, L) ∈ t ){// acceptare sau reducere

 for(c ∈ L) {

 if(B == ‘S’) ACTIUNE(t, #) = “acceptare”;

 else ACTIUNE(t,c)=“R B→γ”;//reducere cu B→γ

 }//endfor

 }// endfor

 for (A ∈ N) GOTO(t, A) = g(t, A);

 }//endfor

(33)

33

 0:S’→S, 1:S →L=R, 2:S →R, 3:L →*R, 4:L →a, 5:R →L

Stare ACTIUNE GOTO

a = * # S L R

0 D5 D4 1 2 3

1 Acc

2 D6 R5

3 R2

4 D5 D4 8 7

5 R4 R4

6 D12 S11 10 9

7 R3 R3

8 R5 R5

9 R1

10 R5

11 D12 D11 10 13

12 R4

13 R3

(34)

Exemplu



Fie cuvintele

 ***a

 a=**a

 *a=**a



Analiza LR(1)?

(35)

Gramatici LALR(1)

35



Definiţie

 Fie t o stare în automatul LR(1) pentru G. Nucleul acestei stări este mulţimea articolelor LR(0) care apar ca prime componente în articolele LR(1) din t.



Defininiţie

 Două stări t₁ şi t₂ ale automatului LR(1) pentru gramatica G sunt echivalente dacă au acelaşi nucleu.

(36)

Gramatici LALR(1)



Fiecare stare a automatului LR(1) este o mulţime de articole LR(1). Pornind de la două stări t

₁

şi t

₂

putem vorbi de starea t1 ∪ t2.

 Fie t₁= {(L → *R., {=, # })}, t₂= {(L → *R., #)}, atunci t₁∪t₂=t₁ pentru că t₂ ⊂ t₁ .



Definiţie

 Fie G gramatică LR(1) şi M = (Q, Σ, g, t0, Q) automatul LR(1) corespunzător. Spunem că gramatica G este

LALR(1) ( Look Ahead LR(1)) dacă oricare ar fi

perechea de stări echivalente t₁, t₂ din automatul LR(1), starea t₁∪t₂ este liberă de conflicte.

(37)

Tabela de analiză LALR(1)

37

 Intrare: Gramatica G = (N, T, S, P) augmentată cu S’ → S;

 Ieşire: Tabela de analiză LALR(1) ( ACŢIUNE şi GOTO ).

 Algoritm:

 1. Se construieşte automatul LR(1), M = (Q, Σ, g, t₀, Q) Fie Q

= {t₀, t₁,…, t_n}. Dacă toate stările din Q sunt libere de conflict, urmează 2, altfel algoritmul se opreşte deoarece gramatica nu este LR(1).

 2. Se determină stările echivalente din Q şi, prin reuniunea acestora, se obţine o nouă mulţime de stări Q’ = {t’₀, t’₁,…, t’_m}

 3. Dacă în Q’ există stări ce conţin conflicte, algoritmul se opreşte deoarece gramatica G nu este LALR(1).

(38)

Tabela de analiză LALR(1)

 4. Se construieşte automatul M’ = (Q’, Σ, g’, t’0, Q’), unde ∀ t’∈Q’:

 5. Dacă t’ ∈ Q atunci g’(t’, X) = g(t, X), ∀X∈Σ;

 6. Dacă t’ = t₁∪t₂∪…, t₁, t₂,…∈Q, atunci

 7. g’(t’, X) = g(t1, X)∪^{g(t2, X)}∪….

 8. Se aplică algoritmul pentru construirea tabelei de parsare LR(1) pornind de la automatul M’. Tabela

obţinută se numeşte tabela LALR(1) pentru gramatica G.

(39)

Exemplu

39



Pentru gramatica discutată anterior avem 4∪11 = 4, 5∪12

= 5, 7∪13 = 7, 8∪10 = 8

(40)

Exemplu



Există gramatici LR(1) care nu sunt LALR(1).

 S →aAb | bAd | aBd | bBb

 A →e

 B →e

(41)

Bibliografie

41



A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman,

Compilers: Principles, Techniques, and Tools, Second Edition. Addison-Wesley, 2007



Gramatici LR(0)

Curs 9

Limbaje formale, automate şi

compilatoare

Recapitulare

Gramatici LR(0)

FIRST, FOLLOW

Gramatici SLR(1)

Parser ascendent general

Mulţimile FIRST şi FOLLOW

FIRST(α) = {a|a

T, α

⇒* au } ∪

if (α

⇒*

) then {

} else ∅.

FOLLOW(A) = {a|a

T ∪ { ε }, S

⇒* uAγ,

a

FIRST (γ) }

Determinare FIRST

Determinare FIRST

Exemplu

Fie gramatica:

S → E | B, E → ε, B → a | begin SC end, C →

| ; SC

FIRST(S) = {a, begin,

} FIRST(E) = {

}

FIRST(B) = {a, begin} FIRST(C) = {;,

}.

FIRST(SEC) = {a, begin, ;,

},

FIRST(SB)= {a, begin},

FIRST(;SC)= {;}.

Determinarea FOLLOW

ε ∈ FOLLOW(S).

Dacă A → αBβXγ

P şi β ⇒

ε, atunci FIRST(X) -{ε}

⊆ FOLLOW (B).

Dacă A → αBβ

P atunci FIRST(β)-{ε} ⊆ FOLLOW (B).

Dacă A → αBβ

P şi β ⇒

ε, atunci FOLLOW(A) ⊆

FOLLOW(B).

Determinarea FOLLOW

Determinarea FOLLOW

Exemplu

Fie gramatica:

S → E | B, E → ε, B → a | begin SC end, C →

|

; SC

FOLLOW(S)=FOLLOW(E)=FOLLOW(B) ={

}

FOLLOW(C) = {end}.

Gramatici SLR(1)

Definiţie

Gramatici SLR(1)

Analiza sintactică SLR(1) este similară cu cea LR(0);

tabela de analiză sintactică are două componente:

Construcţia tabelei de parsare SLR(1)

Intrare:

Ieşire:

Construcţia tabelei de parsare SLR(1)

Parsarea SLR(1)

Parsarea SLR(1)

Intrare:

Ieşire:

Se foloseşte stiva St pentru a implementa tranziţiile

deplasare/reducere

Parsarea SLR(1)

Exemplu

Tabela de tranziţie a automatului LR(0)

Test SLR(1)

G nu este LR(0) stările 1, 2, 9 conţin conflict de deplasare/reducere

FOLLOW(S)={#}, FOLLOW(E)={#,+,)}

S → E | B, E → ε, _B ^→ a | begin SC end, C →

S → E | B, E → ε, _B ^→ a | begin SC end, C →