**** éléments de correction td4-LT-RICM2 sur LR(0)**** ****Laurent Mounier et Laure Gonnord **** Exercice 1 : ------------ (pour des raisons de lisibilité je remplace les bullet par * Construction de l'automate : 0 Z->*S$ S 1 S->*SA S 1 S->*A A 2 A->*aSb a 3 A->*ab a 3 « pas de conflit S/R 1 Z->S*$ $ 4 S->S*A A 5 A->*aSb a 3 2 S->A* Red 3 A->A*Sb S 6 A->a*b b 7 S->*SA S 6 « pas de conflit S/R S->*A A 2 4 Z->S$* Red 5 S->SA* Red 6 A->aS*b b 8 S->S*A A 5 A->*aSb a 3 A->*ab a 3 7 A->ab* Red 8 A->aSb* Red Analyse de (ab)^3$ chaine pile ababab |- 0 babab |- 0a3 abab |- 0a3b7 REDUCE abab |- 0A abab |- 0A2 REDUCE abab |- 0S abab |- 0S1 bab |- 0S1a3 ab |- 0S1a3b7 REDUCE ab |- 0S1A ab |- 0S1A5 REDUCE ab |- 0S ab |- 0S1 b |- 0S1a3 $ |- 0S1a3b7 REDUCE $ |- 0S1A $ |- 0SA5 $ |- 0S $ |- 0S1 vide |- 0S1$4 REDUCE vide |- 0Z FINI Remarque : on n'a pas "trop d'augmentation " sur la pile car la grammaire est rec à gauche... On trouve donc comme dérivation la plus à droite (un peu compactée) Z->S$ -> SA$ -> S(ab)$->SAab$ -> Sabab$ -> ababab$ On remarque que l'on utilise jamais la règle A->aSb ... Exercice 2 : ------------ On regarde les règles A->a et A-> a (S). Lorsqu'on va avoir A->a* et A->a*(S), on ne pourra pas savoir où l'on va en lisant a. Soit on obtient un état "reduce", soit un état "shift". Il y a donc un conflit shift/reduce qui pourrait être résolu en ayant un "look-ahead" de 1 (si on pouvait "voir" le prochain bidule à lire). C'est clair ?? Exercice 3 : ------------ ~~~~ Grammaire 1 : 0 Z->*A$ A 1 A->*ADd a 2 1 Z->A*$ $ 3 2 A->a*Dd D 4 D->*eps eps 5 D->*Db D 4 3 Z->A$* Red 4 A->aD*d d 6 D->D*b b 7 5 D->eps* Red 6 A->aDd* Red 7 D->Db* Red Donc pas de conflit, elle est LR(0). Bien remarquer comment on traite les règles donnant epsilon. ~~~~ Grammaire 2 : 0 Z->*cAc$ c 1 1 Z->c*Ac$ A 2 A->*CaBc C 3 A->*BbBc B 4 C->*bC b 5 C->*eps eps 6 B->*eps eps 6 conflit red/red Cette grammaire n'est pas LR(0). Comment enlever ce conflit, si possible ? ~~~~ Grammaire 3 : 0 Z->*E$ E 1 E->*E+T E 1 E->*T T 2 1 Z->E*$ $ 3 E->E*+T + 4 2 E->T* red 3 Z->E$. red 4 E->E+*T T 5 T->*T'fois'F T 5 « « conflit shift/reduce T->*F F F->*'idf' 'idf' 8 F->*(E) ( 9 La grammaire n'est donc pas LR(0), ce conflit va disparaitre si on fait une analyse SLR(1) Exercice 4 : ------------ On a vu dans les différents exercices qu'il vaut mieux prendre une grammaire récursive à gauche... ****