• Nu S-Au Găsit Rezultate

# Gramatici LR(0)

N/A
N/A
Protected

Share "Gramatici LR(0) "

Copied!
41
0
0
Arată mai multe ( pagini)

Text complet

(1)

1

(2)

## Recapitulare

### Gramatici LR(0)

Teorema de caracterizare LR(0)

Automatul LR(0)

Parserul LR(0)

(3)

## Parser ascendent general

3

Control Tabela de parsare

a1 ... ai ... an #

X1 X1 ...

#

p1 p2 ...

(4)

## Mulţimile FIRST şi FOLLOW

st

st

ε

ε

st

(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 → X1X2…XnP){

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 && Xi st * ε)

15.if((FIRST(Xi+1) ⊈ FIRST(A)){

o 16.FIRST(A)=FIRST(A)∪FIRST(Xi+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 ∈ Σ.

α =X1X2…Xn, Xi ε Σ,1≤i≤n.

Ieşire: FIRST(α).

1.FIRST(α)=FIRST(X1)-{ε};i=1;

2.while(i<n && Xi + ε){

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

4.i=i+1;

}//endwhile

5.if(i==n && Xn + ε)

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

(7)

7

ε

ε

ε

ε

ε

(8)

## Determinarea FOLLOW

+

### ε, atunci FIRST(X) -{ε}

S * α1A β1 ⇒ α1αBβXγβ1* α1αBXγβ1 şi atunci rezultă FIRST(X)-{ε} ⊆ FOLLOW (B).

+

(9)

## Determinarea FOLLOW

9

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

2.FOLLOW(S)={ε};

3.for(A → X1X2…Xn){

4.i=1;

5.while(i<n){

6.while(Xi ∉ N)++i;

7.if(i<n){

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

(FIRST(Xi+1Xi+2…Xn)-{ε});

9.++i;

}//endif

}//endwhile

}//endfor

(10)

## Determinarea FOLLOW

10.FLAG=true;

11.while(FLAG){

12.FLAG=false;

13.for(A → X1X2…Xn){

14.i=n;

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

16.if(FOLLOW(A) ⊄ FOLLOW(Xi)){

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

o 18.FLAG=true;

19.}//endif

20.if(Xi+ ε)--i;

21.else continue;

22.}//endwhile

23.}//endfor

24.}//endwhile

(11)

11

ε

ε, ; , end

(12)

## Gramatici SLR(1)

### Definiţie

Fie G o gramatică pentru care automatul LR(0) conţine stări inconsistente (deci G nu este LR(0)). Gramatica G este gramatică SLR(1) dacă oricare ar fi starea t a

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

### 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)

### Intrare:

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

Automatul M = (Q, Σ, g, t0, 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) = Rp unde p= A → β, |σ’t’| = |β| şi t’’= GOTO(t, A);

Acceptare: (t0t, #, π) 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.

(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 X1X2…Xm”){

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)

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

### 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 → β1∙β2, a) este valid pentru prefixul viabil αβ1dacă are loc derivarea

S dr⇒*αAu ⇒ αβ1β2u

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(t0)=false;

while( tT&& !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(t0,γ) 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 → β1∙aβ2, b), atunci G nu este LR(1).

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

(30)

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)

***a

a=**a

*a=**a

(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 t1 şi t2 ale automatului LR(1) pentru gramatica G sunt echivalente dacă au acelaşi nucleu.

(36)

## Gramatici LALR(1)

1

2

### putem vorbi de starea t1 ∪ t2.

Fie t1= {(L → *R., {=, # })}, t2= {(L → *R., #)}, atunci t1∪t2=t1 pentru că t2 ⊂ t1 .

### 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 t1, t2 din automatul LR(1), starea t1∪t2 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, t0, Q) Fie Q

= {t0, t1,…, tn}. 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’0, t’1,…, 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’ = t1∪t2∪…, t1, t2,…∈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)

39

(40)

## Exemplu

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

S →aAb | bAd | aBd | bBb

A →e

B →e

(41)

## Bibliografie

41

### Cuza”, Iaşi, 2005

Referințe

DOCUMENTE SIMILARE

-este un demers de transmitere de sfaturi şi informaţii în probleme care depăşeşc competenţa celui căruia i se adresează, fapt care determină, remarca Beja M,

atrăgând atenţia că prezentarea ce urmează a o face reprezintă doar elementele de identitate a celor în cauză şi că în calitatea de nutriţionişti putem îndruma

Dar situaţia în care mă aflu acum… păpuşica asta de treişpe ani, care îmi stă goală în poală, în timp ce tată-său îşi face de lucru în spatele unui paravan,

Dacă funcţia membru este virtuală, atunci la orice apelare a ei, determinarea funcţiei membru corespunzătoare a ierarhiei de clase nu se va face la compilare ci la execuţie, în

„Cultura este o conditiune indispensabila pentru dezvoltarea popoarelor iesite din starea de barbarie.” – Aceasta fiind starea în care Radulescu- Motru considera ca se aflase pîna

avuseserã loc în 1972 ºi 1981), care a produs un im- portant document doctrinar, The Gospel and its Im- plications; în Canada, începând cu octombrie 1983 s-a deschis seria

Un utilizator are posibilitatea de a fi notificat în cazul în care se află în apropierea unui prieten şi de a lăsa pe alţii să-i afle locaţia chiar şi atunci când aplicaţia

De obicei rinichiul unic este mai mare (peste 12 cm în axul lung), dar morfologic normal. Confirmarea absenţei unui rinichi se va face şi cu ajutorul urografiei

Dacă în Germania se poate constata o însemnată deplasare şi delegare a puterii dinspre guvernarea federală către landuri în ceea ce priveşte formula referendumului

Acesta primeşte la intrare o propoziţie etichetată similar cu cele din textul folosit pentru învăţare şi determină pentru fiecare cuvânt, pe baza informaţiilor conţinute

Evaluarea periodică a programelor de studiu se face fie în vederea acreditării (Metodologia de evaluare externă, standardele, standardele de referinŃă şi

MB-departe = Maimuţa se află departe de Banană MB-aproape = Maimuţa se află aproape de Banană MB-ţine = Maimuţa ţine Banana. Starea iniţială: MC-departe,

- plot(x,M) – dacă lungimea vectorului x este egal cu numărul de linii al matricei M atunci se vor reprezenta pe acelaşi grafic coloanele matricei M în funcţie de

Dacă evenimentele aleatoare elementare sunt egal probabile (şi în număr finit), atunci probabilitatea unui eveniment aleator A se determină ca raportul dintre numărul de ele- mente

Referitor la problema (II) se va arăta cum se face adunarea şi înmulţirea numerelor naturale reprezentate într-o bază u. În particular, dacă u=10, se regăsesc

Dacă expresia simbolică depinde de mai mult de o variabilă şi variabila pentru care se face substituţia nu este specificată, substituţia se face pentru variabila

Dacă expresia simbolică depinde de mai mult de o variabilă şi variabila pentru care se face substituţia nu este specificată, substituţia se face pentru variabila

Se stabileşte calitatea modelului creat pe baza acestor ponderi pentru TOATE dintre datele de intrare. Se ajustează ponderile în funcţie de

 În cazul în care calculatorul nu “va vede” Arduino-ul, se poate ca o masură de siguranţă să fi intrat în acţiune (de fapt este o “siguranţă” automatizată – ce

Rezumat: În prezenta teză de doctorat se prezintă concepte şi noţiuni fundamentale privind riscurile în ingineria civilă precum şi principalele surse de risc din acest

În acest mod, în momentul când utilizatorul intră în aplicație se verifică dacă acesta are un meci care se află în desfășurare, iar dacă se află atunci acesta este

observaţii ne poate ea sugera. De sigur că, în linii mari şi la prima vedere, lucrurile se prezintă astfel cu privire la cultură: ea este ceea ce

Democratizarea ţării, prin reforme cinstite, va face din fiecare gospodar un puternic element de luptă, care, când va sună ceasul, va şti pentru ce

Selectați limba dvs.

Site-ul web va fi tradus în limba pe care o selectați.

Limbi sugerate pentru dvs:

Alte: