**** Éléments de correction du quick 2005 du 27/10/2005 ****
**** Laurent Mounier et Laure Gonnord ****

Question 1  :
------------
  G0 n'est pas LL(1) : Dir(I->i) = Dir(I->i(I)) = {i}
  On peut factoriser et obtenir G'0 :

		Z -> I #
		I -> i J
		J -> eps | (I)

	Dir(J->eps) = Suivants(J) = Suivants(I) {)  #}
	Dir(J->(I)) = {(}

		G'0 est LL(1) ...	

Question 2 : 
------------
	0	Z -> .I# 	I	1
		I -> .i		i	2
		I -> .i(I) 	i 	2
	1	Z -> I.#	#	accept
	2	I -> i.	        #  )	Red
		I -> i.(I)	(	3
	3	I -> i(.I)	I 	4
		I -> .i		i	2
		I -> .i(I)	i	2
	4	I -> i(I.)	)	5
	5	I -> i(I).	# )	Red

	G0 n'est pas LR(0) (conflit sur l'état 2), mais est SLR(1).

Question 3 :
------------
	On part de la grammaire G suivante :

		Z -> I#
		I -> i | i(P)
		P -> I | I,P

	Après factorisation, on obtient G1 :

		Z -> I#
		I -> i J
		J -> eps | (P)
		P -> I K
		K -> eps | , P

	Dir(J->eps) = Suivants(J) = Suivants(I) {)  #  ,}
	Dir(J->(I)) = {(}
	Dir(K->eps) = Suivants(K) = Suivants(P) {)}
	Dir(K->, P) = {,}

	donc G1 est LL(1) 

Question 4 : 
------------
	G est SLR(1), c'est notre choix pour G2 :

	0	Z -> .I#	I 	1
		I -> .i		i 	2
		I -> .i(P)	i	2
	1	Z -> I.#	#	accept
	2	I -> i.	        #,)	Red
		I -> i.(P)	(	3
	3	I -> i(.P)	P	4
		P -> .I		I	5
		P -> .I,P	I	5
		I -> .i		i	2
		i -> .i(P)	i	2
	4	I -> i(P.)	)	6
	5	P -> I.		)	Red	
		P -> I.,P	,	7
	6	I -> i(P).	#,)	Red
	7	P -> I,.P	P	8
		P -> .I		I	5
		P -> .I,P	I 	5
		I -> .i		i	2
		I -> .i(P)	i	2
	8	P -> I,P.	)	Red

Question 5 : 
------------

	On montre que la phrase "i(i,i(i#" n'est pas reconnue :

i(i,i(i#	0
 (i,i(i#	0i2
  i,i(i#	0i2(3
   ,i(i#	0i2(3i2
   ,i(i#	0i2(3I5
    i(i#	0i2(3I5,7
     (i#	0i2(3I5,7i2
      i#	0i2(3I5,7i2i3
       #	0i2(3I5,7i2i3i2
       #	0i2(3I5,7i2i3I5

Pas de transitions pour "#" dans l'etat 5 -> Erreur ...

L'erreur ne doit apparaître que sur la lecture du #, en effet, comme
i(i,i(i))# est dans le langage, on doit pouvoir lire ce mot avec
succès, or, on lit de gauche à droite, donc on ne peut dire "erreur"
qu'au moment de lire le dièse. A ce moment là, on doit pouvoir lire
une parenthèse fermante ou encore une virgule.

Question 6 : 
------------
	- Jusqu'à la phase d'analyse syntaxique incluse le compilateur
	ne peut	pas distinguer les deux interpretations (puisque la
	syntaxe est identique !)

	- la distinction se fait lors de l'analyse sémantique,
        notamment pour vérifier que le typage est correct.

Questions subsidiaires 
----------------------

 1  L0 n'est pas un langage régulier :
	Les nombres de parenthéses ouvrantes et fermantes doivent être
	égaux dans toute phrase du langage, il faut donc "compter" des
	lexèmes pour reconnaitre une phrase, ce qui est impossible
	avec un automate d'état fini. 
    L n'est donc pas régulier non plus (L0 inclus dans L).

 2. G0 est bien une grammaire LL(2) : en examinant 2 symboles en avant on 
	lève le conflit  : i# <> i) <> i(

 3.  Si on supprime la virgule dans G2, les modifications débutent à l'état 5 :

     Nouvel état 5 :
		
	5	P -> I.		)	Red	
		P -> I. P	P	...
		P -> .I		I	8
		P -> .I P	I	8
		I -> .i		i	2
		I -> .i(P)	i	2

	8	P -> I.		)	Red	
		P -> I.P	P	...
		P -> .i		i	2
		P -> .i(P)	i	2

Il n'y a pas de nouveaux conflits introduits, on peut supprimer la
virgule (intuitivement, comme chaque paramètre est "bien parenthésé",
on peut distinguer lors de l'analyse la fin d'un paramètre du début du
suivant). 

****