**** éléments de correction td6-LT-RICM2 sur LR, SLR, LALR**** ****Laurent Mounier et Laure Gonnord **** Exercice 1 : fonctionnement de l'automate donné sur **i=**i# ------------ (les étoiles dénotent bien les étoiles ici) chaîne pile **i=**i# |- 0 *i=**i# |- 0*4 i=**i# |- 0*4*4 =**i# |- 0*4*4i5 RED =**i# |- 0*4*4L8 RED =**i# |- 0*4*4R7 RED |- 0*4L8 RED |- 0*4R7 RED =**i# |- 0L2 **i# |- 0L2=6 *i# |- 0L2=6*4 i# |- 0L2=6*4*4 # |- 0L2=6*4*4i5 RED # |- 0L2=6*4*4L8 RED # |- 0L2=6*4*4R7 RED # |- 0L2=6*4L8 RED # |- 0L2=6*4R7 RED # |- 0L2=6L8 RED # |- 0L2=6R9 RED # |- 0S1 ACCEPT Exercice 2 : On doit construire les analyseurs ------------ Grammaire 1 ~~~~~~~~~~~ 0 Z->*S# S 1 S->*Aa A 2 A->*d d 3 1 Z->S*# # 4 2 S->A*a a 5 3 A->d* RED 4 Z->S#* RED donc LR(0) donc tout le reste ... Grammaire 2 ~~~~~~~~~~~ 0 Z->*S# S 1 S->*Aa A 2 S->*dc d lect 3 A->*d d lect 3 1 Z->S*# # accept 2 S->A*a a lect 4 3 A->d* S->d*c Conflit Shift/reduce, donc grammaire non LR(0) Construisons l'état 3 à l'aide des Suivants(A)={a}, 'd' n'est pas dedans donc le conflit n'est pas un conflit SLR(1), continuons 3 A->d* a red S->d*c c lect 5 4 S->Aa* # red pas de problème supplémentaire, cette grammaire est bien SLR(1). Grammaire 3 ~~~~~~~~~~~ Le début de la construction ressemble à celle de la grammaire 2, merci le copier-coller :-) 0 Z->*S# S 1 S->*Aa A 2 S->*dc d lect 3 A->*d d lect 3 S->*bAc b lect 4 1 Z->S*# # accept 2 S->A*a a lect 5 3 A->d* suivant(A)={a,c} S->d*c c lect 6 donc c'est un conflit SLR(1), on va donc construire l'analyseur LR(1). C'est reparti .... ------ automate LR(1) Suivants(Z)=eps Suivants(S)={#} Suivants(A)={a,c} 0 Z->*S# {eps} S 1 S->*Aa {#} A 2 S->*dc {#} d lect 3 A->*d {a} d lect 3 « voir rque. S->*bAc {#} b lect 4 Rque La règle (A->*d) a été ammenée par la cloture de S->Aa, donc le seul caractère suivant possible est 'a' 1 Z->S*# {eps} # accept 2 S->A*a {#} a lect 5 3 S->d*c {#} c lect 6 A->d* {a} a reduction 4 S->b*Ac {#} A 7 A->*d {c} d lect 8 (dernière règle obtenue par clotûre à partir de S->bAc, donc suivant =c) 5 S->Aa* {#} # reduction 6 S->dc* {#} # reduction 7 S->bA*c {#} c lect 9 A->*d {c} d lect 8 « ouffff 8 A->d* {c} c reduction 9 S->bAc* {#} # reduction On n'a eu aucun problème pour construire l'automate LR(1), donc la grammaire est LR(1). Maintenant, est-elle LALR(1) ? Tous les ensembles de noyaux sont distincts, donc pas de fusion possible, donc OUI Grammaire 4 ~~~~~~~~~~~ Et encore un analyseur LR(1) ... Suivants(Z)={eps} Suivants(A)={#} Suivants(X)={b} 0 Z->*A# {eps} S 1 A->*aXb {#} a Lect 2 1 Z->A*# {eps} # accept 2 A->a*Xb {#} X Lect 3 X->*b {b} b Lect 4 X->*bb {b} b Lect 4 3 A->aX*b {#} b Lect 5 4 X->b* {b} b Red X->b*b {b} b Lecture Il y a ici un conflit LR(1). Cette grammaire n'est pas LR(1), et donc a fortiori pas LALR(1) non plus. Exercice 3 : ------------ Analyseur syntaxique descendant : On commence par calculer les directeurs~: dir(R0) = {a, b} dir(R1) = {a,b} dir(R2) = {b} dir(R3) = {a} dir(R4) = {b} dir(R5) = {a} dir(R6) = {e} dir(R7) = {f} dir(R8) = {#} Et voilà donc l'analyseur : Rec_Z : init_sequence() si symbole_courant() appartient à {a,b} alors Rec_S ; sinon erreur() Rec_terminal(#) Rec_S : si symbole_courant() appartient à {a,b} alors Rec_X ; Rec_terminal (a) ; Rec_Y ; sinon erreur() Rec_X : si symbole_courant() = b alors Rec_W sinon si symbole_courant() = a alors Rec_T sinon erreur() Rec_W : si symbole_courant() = b alors Rec_terminal(b) ; Rec_terminal(c) sinon erreur() Rec_T : si symbole_courant() = a alors Rec_terminal(a) ; Rec_terminal(c) sinon erreur() Rec_Y : si symbole_courant() = e alors Rec_terminal(e) ; Rec_Y sinon si symbole_courant() = f alors Rec_terminal(f) sinon si symbole_courant() = # alors /* rien */ sinon erreur() Rec_terminal (t : terminal) : si symbole_courant() = t alors avancer() sinon erreur() ****