**** éléments de correction td3-LT-RICM2 ****
****Laurent Mounier et Laure Gonnord ****
**** v2 25 oct 2005 ****

Exo 1
-----

Directeur(Z -> S#) = Premier(S) union {#}
		   = {a,b} union {#}
		   = {a,b,#} 

Directeur(S -> Xa) = Premier(X) union {a}
		   = {a,b} union {a}
		   = {a,b}

Directeur(S -> epsilon) = Suivant(S) = {#} 

Directeur(X -> bX) = {b}

Directeur(X->epsilon) = Suivant(X) = {a} union Suivant(Y)
				   = {a} union {a,b}
				   = {a,b}

Directeur(Y->aX) = {a}

Directeur(Y->epsilon) = Suivant(Y) = {a,b}

La grammaire n'est pas LL(1) ...


Exo 2 
-----

Il suffit de considérer les règles récursives à gauche :

	Directeur(X->Xa) = {a}
	Directeur(X->epsilon) = Suivant(X) = {a}

"théorème" : une grammaire récursive à gauche ne peut pas être LL(1) ...

Langage décrit par :
	Y : d.b*
	X : a*
	S : a* + db*c
	Z : a.*# + db*c#

Pour trouver une grammaire reconnaissant le même langage il faut essayer 
d'éliminer la récursivité à gauche :

	X -> Xa et X -> epsilon peut etre re-écrit :
		X -> aX
		X -> epsilon

	Y->Yb et Y->d peut etre re-écrit :
		Y -> dT
		T -> bT | epsilon

On obtient donc la nouvelle grammaire :

	Z -> S#
	S -> X | Yc
	X -> aX | epsilon
	Y -> dT
	T -> bT | epsilon 

qui est LL(1) :

	Directeur(S->X) = Premier(X) union Suivant(X) = {a,#} 
	Directeur(S->Yc) = Premier(Y)= {b,d} 
	Directeur(X->aX) =  {a}
	Directeur(X->epsilon) = Suivant(X) = {#}
	Directeur(T->bT) = {b} 
	Directeur(T->epsilon) = Suivant(T) = {d} 


Exo 3 - rajout du 25 oct 05 --
-----

Cette grammaire n'est pas LL(1) à cause des deux récursivités à gauche
pour le E et pour le T. On commence par solutionner le problème le
plus "intérieur", c'est-à-dire la récursivité sur l'étoile.

"pour enlever la récursivité à gauche sur A, avec A=>Aa, si on a
A->Aa|B (B terminal ou non), alors on remplace par A->BR et R->aR|eps"

ici on a T->T*F|F : 'T' joue le rôle de 'A', 
'*F' joue le rôle de 'a' et 'F' le rôle de 'B' donc on obtient (A LA
PLACE !!!):
T->FR et R->*FR|eps et la suite, ie F->i|e|(E)
A-t-on bien supprimé le conflit des directeurs ?
Directeur(R->*FR) = {i,e,'(' } et directeur(R->eps)= suivants(R)=
Suivants (T) = pour l'instant on ne peut pas conclure ...

Maintenant, regardons la récursion sur E->E+T|T, dans la "recette de
cuisine", 'E' joue le rôle de A, '+T' joue le rôle de 'a' et 'T' le
rôle de B, donc :
E->TU et U->+TU|eps

Finalement, on trouve la grammaire équivalente :

	    Z -> E#
	    E -> TU
	    U -> +TU | eps 
	    T -> FR
	    R -> *FR | eps

avec Directeur(R->eps)={+} <> Directeur(R->*FR) = {i,e,'(' }
et Directeur(U->+TU)={+} <> Directeur (U->eps)=Suivants(U)={#}

ok ?

Exo 4
-----

On peut essayer la grammaire du TD2 :

	Z -> X
	X -> a | b | epsilon | aXa | bXb

Clairement pas LL(1) car Dir(X->a)={a}=Dir(X->aXa)

On peut tenter de la modifier :

	X -> aY | bT | epsilon
	Y -> Xa | epsilon
	T -> Xb | epsilon

toujours pas LL(1) : Dir(Y -> Xa)={a,b} et Dir(Y->epsilon)={a,b}

Intuitivement, on ne peut pas trouver d'analyseur descendant déterministe 
pour reconnaitre un palindrome : on ne peut jammais savoir si on a ou non 
atteint la "moitié" du palindrome, cad s'il faut continuer à lire (X->aXa)
ou non (X->a), car Dir(X->a)=Dir(X->aXa). 

Exo 5  
------

Cette grammaire n'est pas LL(1). Le langage décrit est de la forme : 

	(i:)*i:=e;

On peut essayer de ré-ecrire cette grammaire :

	Z -> X ;
	X -> Y i : = e
	Y -> i : Y | epsilon		/* le langage de Y est (i:)* */

Cette grammaire n'est pas LL(1) car Suivant(Y) = {i},
donc Dir(Y->i:Y) = Dir(Y->epsilon).

Une solution pour résoudre ce pb est de modifier l'ensemble des symboles
terminaux en choisisant Vt = {:, aff, ;, i, e} ou "aff" représente :=.
On obtient alors :
	
	Z -> S ;
	S -> i X 
	X -> aff e
	X -> : S
	

**** fin ****