**** éléments de correction td3BIS-LT-RICM2 **** **** Laurent Mounier et Laure Gonnord **** **** V2 - 12 octobre 2005 **** Exo 1 ----- Cette grammaire n'est pas LL(1) car : -- recursive à gauche (cf règle de E) -- Conflit de directeurs sur A : Directeurs(A->ac)={a}=Directeur(A->eps) pour dérécursiver, on change les règles de E en E->gE et E->f pour enlever le conflit des directeurs (qui vient des règles 2,3,4), on va faire une règle pour dériver le premier a à part : S->aRE R->aR|c|d (qui remplacent les règles 1 à 4) Exo 2 ----- Cette grammaire n'est pas LL(1) car : Dir(If Statement -> IF '(' Expression ')' Statement) = Dir(If Statement -> IF '(' Expression ')' Statement ELSE Statement) = {IF} On peut aussi dire que c'est une grammaire ambiguë (comme on l'a vu au TD2), or une grammaire ambiguë ne peut pas être LL(1) ! En effet : - dans une grammaire LL(1) au plus une seule dérivation est possible pour reconnaitre une phrase du langage donnée (par construction !) - donc une grammaire LL(1) n'est pas ambiguë - donc une grammaire ambiguë n'est pas LL(1) (par contraposée ...) - un espoir est donc de repartir de la grammaire non ambiguë proposée pour ce langage en introduisant des statements "ouverts" (qui se terminent par un if sans partie else) ou "fermés" (les autres). Statement -> Statement_Ferme Statement -> Statement_Ouvert Statement_Ferme -> IF (Expression) Statement_Ferme ELSE Statement_Ferme StatemenT_Ferme -> Other_Statements Statement_Ouvert -> IF (Expression) Statement Statement_Ouvert -> IF (Expression) Statement_Ferme ELSE Statement_Ouvert Elle n'est pas LL(1), mais on peut essayer de factoriser certaines règles, par exemple tout ce qui commence par "IF (Expression)" : Statement -> Statement_Ferme Statement -> Statement_Ouvert Statement_Ferme -> If_exp Statement_Ferme ELSE Statement_Ferme StatemenT_Ferme -> Other_Statements Statement_Ouvert -> If_exp Suite_Statement_Ouvert Suite_Statement_Ouvert -> Statement Statement_Ouvert -> Statement_Ferme ELSE Statement_Ouvert If_exp -> IF (Expression) Cette grammaire n'est toujours pas LL(1) ! Mais on voit maintenant que pour la rendre LL(1) il faut être capable de distinguer entre un "Statement_Ferme" et un "Statement_Ouvert" pour savoir quelle règle appliquer lorsqu'il s'agit de reconnaitre un "Statement" qui commence par "IF ...". Or, pour cela, il faut déterminer si ce "IF" contient ou non une partie "else", ce qui signifie lire de nombreux symboles en avant dans le texte. Exemple : IF (Expression) IF (Expression) O ELSE O est reconnu par : Statement => Statement_Ouvert => IF (Expression) Statement => IF (Expression) Statement_Ferme => IF (Expression) IF (Expression) Statement_Ferme ELSE Statement_Ferme =>* IF (Expression) IF (Expression) O ELSE O Par contre, IF (Expression) IF (Expression) O ELSE O ELSE O est reconnu par : Statement => Statement_Ferme => IF (Expression) Statement_Ferme else Statement_Ferme => IF (Expression) IF (Expression) Statement_Ferme ELSE Statement_Ferme ELSE Statement_Ferme =>* IF (Expression) IF (Expression) O ELSE O ELSE O On voit que pour choisir la 1ère dérivation il faut aller lire un "else" bien loin dans le texte ! Cette grammaire n'est donc pas LL(1) (ni LL(k) pour aucun k ...). On peut donc supposer qu'il n'existe pas de grammaire LL(1) pour ce langage ... (Mouais ?). ****