lfac Gh Grigoras 1

Cursul 9

•Gramatici LR(0)•Automatul LR(0)

•Test LR(0)

•Analizor sintactic LR(0)

•Generatoare de analizoaresintactice - YACC

•Gramatici şi analizoare SLR(1)–Test SLR(1)

–Tabela de analiza SLR(1)

–Analizor sintactic SLR(1)

lfac Gh Grigoras 2

Automatul LR(0)

Algoritmul 1 (procedura închidere(t))

Intrare: Gramatica G = (V, T, S, P);

Mulţimea t de articole din gramatica G;

Ieşire: t’ = închidere( t ) = {q Q | p t, q (p, ) } = (t, )

Metoda:t‟ = t ; flag = true;

while( flag ) {

flag = false;

for ( A B t‟ ) {

for ( B P )

if ( B t‟ ) {

t‟ = t‟ {B }; flag = true;

}//endif

}//endforB

}//endforA

}//endwhile

return t‟;

lfac Gh Grigoras 3

Automatul LR(0)Algoritmul 2 Automatul LR(0)

Intrare: Gramatica G = (N, T, S, P) la care s-a adăugat S’ S;

Ieşire: Automatul determinist M = (T, , g, t0, T) echivalent cu M.

Metoda:

t0=închidere(S‟S); T={t0}; marcat(t0)=false;while(tT && !marcat(t)) { // marcat(t) = false

for( X ) { // = N T

t‟ = ;

for( A X t )

t‟ = t‟ {B X | B X t};

if( t‟ ){

t‟ = închidere( t‟ );

if( t‟ T ) {

T = T { t‟ };

marcat( t‟ ) = false;

}//endif

g(t, X) = t‟;

}//endif

}//endfor

}//endfor

marcat( t ) = true;

}// endwhile

lfac Gh Grigoras 4

Automatul LR(0)

Exemplu S’ S, S aSa | bSb | c

c

a b

SS

b

a

cc

ba

S

S bSb

S aSa

S bSb

S c

S aSa

S aSa

S bSb

S c

S’ S

S aSa

S bSb

S c

S’ S

S c

S bSbS aSa

S aSa S bSb

a

b

lfac Gh Grigoras 5

Test LR(0)

Definiţie Fie G o gramatică şi M automatul LR(0) ataşat

lui G. Spunem că o stare a lui M are un conflict

reducere/reducere dacă ea conţine două articole

complete distincte A , B . Spunem că o stare a

lui M are un conflict deplasare/reducere dacă ea

conţine un articol complet A şi un articol cu

terminal după punct de forma B a. Spunem că o

stare este consistentă dacă ea nu conţine conflicte şi

este inconsistentă în caz contrar.

Teorema Fie G o gramatică şi M automatul său LR(0).

Gramatica G este LR(0) dacă şi numai dacă automatul

M nu conţine stări inconsistente

lfac Gh Grigoras 6

Automatul LR(0)

Exemplu S aAd | bAB A cA | c B d

A

dBd

AA

c

a

c

b

S

S bAB

A cA

S c

S aAd

A cA

A c

S’ S

S aAd

S bABS’ S

A cA

A c

A cA

A c

S bAB

B dS aAd

S aAd B dS bAB

A cA

c

lfac Gh Grigoras 7

Algoritm de analiză sintactică LR(0)

CONTROL

a1 … … an #ai

TABELA

DE

PARSAREtm

tm-1

.

.

t0

Stiva

Intrare

p1 p2 …

Ieşire

lfac Gh Grigoras 8

Algoritm de analiză sintactică LR(0)

• În cazul k = 0, tabela de parsare coincide cu automatul LR(0), M.

• Configuraţie: (, u#, ) unde t0T*, u T*, P*.

• Configuraţia iniţială este (t0, w#, ),

• Tranziţiile:– Deplasare: ( t, au#, ) ( tt’, u#, ) dacă g (t, a) = t’.

– Reducere: ( t’t’, u#, ) ( tt’’, u#, r) dacă A t’,

r = A , |’t’ | = || şi t’’= g (t, A).

– Acceptare: (t0t1, #, ) este configuraţia de acceptare dacă

S’ S t1, este parsarea acestuia (şirul de reguli care s-a aplicat, în ordine inversă, în derivarea extrem dreaptă a lui w).

– Eroare: o configuraţie căreia nu i se poate aplica nici o tranziţie este configuraţie de eroare. Analizorul se opreşte cu respingerea cuvântului de analizat.

lfac Gh Grigoras 9

Algoritmul de analiză sintactică LR(0)

Intrare: Gramatica G (cu S’ S), Automatul LR(0) notat M = (T, , g, t0, T ), Cuvântul de intrare w T*.

Ieşire: Analiza sintactică (parsarea) ascendentă a lui w dacă w L(G); Eroare, în caz contrar.

Metoda: Fie STIVA o stivă, a simbolul curent, char ps[] = “w#”; //ps este sirul de intrare w

i = 0; // pozitia in sirul de intrare

STIVA.push(t0); // se initializeaza stiva cu t0

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

t = STIVA.top();

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

if( g(t, a) { //deplasare

STIVA.push(g(t, a));

i++; //se inainteaza in intrare

}

else {

if(A X1X2…Xm t){

if(A == „S‟‟)

if(a == „#‟)exit( “acceptare”);

else exit(“eroare”);

else // reducere

for( i = 1; i m; i++) STIVA.pop();

STIVA.push(g(top(STIVA), A));

} //endif

else exit(“eroare”);

}//endelse

}//endwhile

lfac Gh Grigoras 10

Exemplu S’ S S E$ E E+T T (E) E T T a

+

a

(

$

T

+

E

)

(

a

a

T

(

T

E

S

S’ SS E$

E E+T

E TT (E)

T a

S’ S

0 1

S E$E E+T

2

E T

3

T (E)E E+T

E TT (E)

T a

4

T a

5

S E$

6

E E+TT (E)

T a

7T (E)E E+T

8

E E+T

9

T (E)

10

lfac Gh Grigoras 11

Exemplu S’ S S E$ E E+T T (E) E T T a

G a + ( ) $ S E T

0 5 4 1 2 3

1

2 7 6

3

4 5 4 8 3

5

6

7 5 4 9

8 7 10

9

10

lfac Gh Grigoras 12

Exemplu S’ S S E$ E E+T T (E) E T T a

STIVA INTRARE ACŢIUNE IEŞIRE

0 a+(a+a)$# deplasare

5 +(a+a)$ # reducere T a

03 +(a+a)$ # reducere E T

02 +(a+a)$ # deplasare

027 (a+a)$ # deplasare

0274 a+a)$ # deplasare

02745 +a)$ # reducere T a

02743 +a)$ # reducere E T

02748 +a)$ # deplasare

lfac Gh Grigoras 13

Exemplu S’ S S E$ E E+T T (E) E T T a

027487 a)$ # deplasare

0274875 )$ # reducere T a

0274879 )$ # reducere E E+T

02748 )$ # deplasare

02748(10) $# reducere T (E)

0279 $# reducere E E+T

02 $# deplasare

026 # reducere S E$

01 # acceptare

lfac Gh Grigoras 14

Corectitudinea parserului LR(0)

Lema 1 Fie G = (N, T, S, P) o gramatică LR(0), t0, t0 drumuri în

automatul LR(0) etichetate cu respectiv şi u, v T*. Atunci, dacă în

parserul LR(0) are loc (t0, uv#, ) + (t0, v#, ), atunci în G are loc

derivarea u.

Lema 2 Fie G = (N, T, S, P) o gramatică LR(0) şi + o formă

propoziţională a lui G astfel încât u, cu * şi dacă este nenul

atunci :1 este neterminal. Atunci în parserul LR(0) are loc calculul

(t0, uv#, ) * (t0, v#, )

unde t0 şi t0 sunt drumuri în automatul LR(0) etichetate cu respectiv

, pentru orice cuvânt v T*.

Teorema Dacă G este gramatică LR(0) atunci, oricare ar fi cuvântul de

intrare w T*, parserul LR(0) ajunge la configuraţia de acceptare pentru

w, adică (t0, w#, ) + (t0t1, #, ), dacă şi numai dacă S w.

~

dr

~

dr

~

dr

Generatoare de analizoare sintactice

• YACC (“Yet Another Compiler Compiler’’)

conceput şi realizat în 1975 de S. C. Johnson la

Bell Laboratory

• Bison, compatibil în întregime cu YACC, scris de

Robert Corbett şi Richard Stallmann (2006 –

versiunea 2.3)

• http://dinosaur.compilertools.net/

• http://epaperpress.com/lexandyacc/index.html

• http://www.gnu.org/software/bison/

lfac Gh Grigoras 15

Utilizarea generatorului de parsere YACC

• yacc nume_fisier.y

• Structura fișierului de intrare:

Declaraţii

%%

Reguli

%%

Rutine C

lfac Gh Grigoras 16

Declaraţii

• %{ Declarații C %}

• Declararea token-urilor:

%token <nume _unitate _lexicală>

• Declararea simbolului de start al gramaticii:

%start <nume _simbol _de _start>

• Alte declarații:type - pentru definirea tipului;

left - pentru asociativitate stânga a operatorilor;

right - pentru asociativitate dreapta a operatorilor;

prec - pentru precizarea precedenţei operatorilor;

nonassoc - pentru declaraţiile de neasociativitate

lfac Gh Grigoras 17

Reguli

• Forma unei reguli:

<neterminal> : <parte dreapta> {cod C}

expr : NUMAR {$$ = $1;}

| expr „+‟ expr {$$ = $1+$3;}

| expr „-‟ expr {$$ = $1-$3;}

| expr „*‟ expr {$$ = $1*$3;}

| expr „/‟ expr {$$ = $1/$3;}

| „(„ expr‟)‟ {$$ = $2;}

;

lfac Gh Grigoras 18

Exemplu

%token a b c d

%%

S : A a {printf(“ S -> Aa \n”);}

| b A c {printf(“ S -> bAc \n”);}

| B c {printf(“ S -> Bc \n”);}

| b B a {printf(“ S -> bBa \n”);}

A : d {printf(“ A -> d \n”);}

B : d {printf(“ B -> d \n”);}

%%

int main(void) {

yyparse();

}

lfac Gh Grigoras 19

Exemplu%token CINT VAR

%left '+' '-'

%left '*' '/‟

%%

program:

program statement '\n'

| /* NULL */

;

statement:

expression {printf("%d\n", $1);}

| VAR '=' expression { sym[$1] = $3; }

;

expression:

CINT

| VAR { $$ = sym[$1]; }

| expression '+' expression { $$ = $1 + $3; }

| expression '-' expression { $$ = $1 - $3; }

| expression '*' expression { $$ = $1 * $3; }

| expression '/' expression { $$ = $1 / $3; }

| '(' expression ')' { $$ = $2; }

;

%%

lfac Gh Grigoras 20

lfac Gh Grigoras 21

Gramatici şi analizoare SLR(1)

Definiţia 5.4.1 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).

Modelul de algoritm de analiză sintactică SLR(1) este acelaşi ca cel

LR(0); tabela de analiză sintactică se construieşte astfel:

– Prima, numită ACŢIUNE, determină dacă parserul va face deplasare

respectiv reducere, în funcţie de starea ce se află în topul 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.

lfac Gh Grigoras 22

Construcţia tabelei de parsare SLR(1) )

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

Automatul M = (Q, , g, t0, Q );Mulţimile FOLLOW(A), A V

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 V.

Metoda:

for(t Q)//Se initializeaza tabela de parsare

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, a) = “acceptare”;

else

for(aFOLLOW(B))ACTIUNE(t,a)=“R B”;

}// endfor

for (A V) GOTO(t, A) = g(t, A);

}//endfor

lfac Gh Grigoras 23

Algoritmul de analiză sintactică SLR(1)

• Deplasare: ( t, au#, ) ( tt’, u#, ) dacă ACTIUNE(t, a) = Dt’ ;

• Reducere: ( t’t’, u#, ) ( tt’’, u#, p) dacă 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.

lfac Gh Grigoras 24

Algoritmul de analiză sintactică SLR(1)

• Intrare:

– Gramatica G = (V, 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.

• Metoda: Se foloseşte stiva St pentru a

implementa tranziţiile deplasare/reducere

lfac Gh Grigoras 25

Algoritmul de analiză sintactică 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

}//endwhile

lfac Gh Grigoras 26

Exemplu: Fie gramatica expresiilor aritmetice:

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

S EE E+T

E TT T*F

T FF (E)

F a

0

S EE E+T

1

T T*F

F (E)E E+TT T*F

E E+TT T*F

T FF (E)

F a

6

11

T T*FF (E)

F a

7F (E)E E+T

8

E TT T*F

2

T F

3

F a

F (E)

E E+T

E TT T*F

T FF (E)

F a

4

5

9

10

lfac Gh Grigoras 27

Tabela de tranziţie a automatului LR(0)

g 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 11

9 7

10

11

lfac Gh Grigoras 28

Tabela de analiză SLR(1)

ACŢIUNE GOTO

STARE a + * ( ) # E T F

0 D5 D4 1 2 3

1 D6 accepta

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 D11

9 R1 D7 R1 R1

10 R3 R3 R3 R3

11 R5 R5 R5 R5

lfac Gh Grigoras 29

Test SLR(1)

• Din automatul construit se deduce că G nu este LR(0): stările 1, 2, 9

conţin conflict de deplasare/reducere. Pentru a verifica dacă

gramatica este SLR(1) avem nevoie de mulţimile FOLLOW(S) şi

FOLLOW(E).

• Gramatica este SLR(1) pentru că:

– în starea 1: + FOLLOW(S);

– în starea 2: * FOLLOW(E);

– în starea 9: * FOLLOW(E).

NETERMINAL FOLLOW

S #

E #, +, )

T #, +, *, )

F #, +, *, )

lfac Gh Grigoras 30

STIVA INTRARE ACŢIUNE IEŞIRE

0 a*(a+a)# deplasare

5 *(a+a)# reducere F a

3 *(a+a)# reducere T F

2 *(a+a)# deplasare

27 (a+a)# deplasare

274 a+a)# deplasare

2745 +a)# reducere F a

02743 +a)# reducere T F

02742 +a)# reducere E T

lfac Gh Grigoras 31

STIVA INTRARE ACŢIUNE IEŞIRE

02748 +a)# deplasare

027486 a)# deplasare

0274865 )# reducere F a

0274863 )# reducere T F

0274869 )# reducere E E+T

02748 )# reducere

02748(11) # reducere F (E)

027(10) # reducere T T*F

02 # reducere E T

01 # acceptare

lfac Gh Grigoras 32

Exemplu: 1.S L=R, 2.S R, 3.L *R, 4.L a, 5.R L

*

*

R

R

L

L

a

a

=

a

L

S

*

R

S’ SS L=R

S RL *RL aR L

0

L a

S’ S

1

S L=R

R L

2

S R

3

5

L *RR LL *RL a

4

S L=RR LL *RL a

6

L *R

7

R L

8

S L=R

9