**** éléments de correction td4bis-LT-RICM2 sur LR(0)/SLR(1)****
****Laurent Mounier et Laure Gonnord ****
**** v3 - 25 octobre 2005 ****


Grammaire :
----------
  Z->C;
  C->p|p(P)
  P->i,P|i


Question 1
----------  

On construit l'analyseur LR(0)/SLR(1) :


0	Z -> *C;	C	1
	C -> *p		p	2
	C-> *p(P)	p	2

1	Z -> C*;	; 	Accept

2	C -> p*	      epsilon	Red	car Suivants(C)=vide 
	C -> p*(P)	(	3

3	C -> p(*P)	P	4	
	P -> *i,P	i	5
	P -> *i		i 	5

4 	C -> p(P*)	)	6
	
5	P -> i*,P	,	7
	P -> i*		)	Red	car Suivants(P)={)}

6	C -> p(P)*		Red

7	P -> i,*P	P	8
	P -> *i,P	i	5	
	P -> *i		i	5

8	P -> i,P*              	Red

Les états 2 et 6 sont des états de conflit LR(0) (shift/reduce).
Il n'y a pas d'états de conflit SLR(1) => G est donc SLR(1).

Question 2
----------  

 Exemple d'analyse de "p(i,i);" :

p(i,i);				0
 (i,i);				0p2
  i,i);				0p2(3
   ,i);				0p2(3i5
    i);				0p2(3i5,7
     );				0p2(3i5,7i5
     );				0p2(3i5,7P8
     );				0p2(3P4
     ;				0p2(3P4)6
     ;				0C1
     epsilon			0Z
				ACCEPT
 

Question 3
----------  
Le conflit LR(0) de l'état 2 vient du fait que le langage proposé doit
	contenir au moins  les deux chaînes suivantes : 
	p 
	p (i) 

Or, pour que la grammaire soit LR(0), il ne faut pas qu'elle contienne
deux règles  de la forme :
		X -> alpha
		X -> alpha.c.beta, avec c un element de Vt 
	(sinon on a un conflit lecture/reduction à tous les coups !).

Avec cette grammaire un analyseur LR(0) ne peut pas savoir, sans
regarder un symbole en avant, si,  après avoir lu "p" on doit réduire
immédiatement (si'il n'y a plus de symbole derrière), ou continuer à
lire (s'il y a une "(" derrière). Pour résoudre ce pb on peut modifier
la grammaire pour "descendre" le ";" sur les règles 2 et 3.

Le conflit de l'état 5 vient juste du fait que la grammaire proposée
est récursive à droite. 
En remplaçant la  récursivité à droite par une récursivité à gauche ce
conflit disparait :	

		P -> P, i 
		P -> i

Pour résoudre le problème on peut donc :

 - soit ajouter des symboles terminaux # et _ pour résoudre
   "brutalement" les conflits des etats 2 et 5 :

		Z -> C ; 
		C -> p #
		C -> p ( P ) 
		P -> i, P 
		P -> i _
	
(le langage est alors modifié, mais l'énoncé ne l'interdit pas).

 - soit modifier la grammaire pour la rendre LR(0), sans changer le
   langage (c'est possible sur cet exemple, ce n'est bien sur pas
   toujours le cas)

		Z -> C 
		C -> p ;
		C -> p ( P ) ;
		P -> P, i 
		P -> i

Il faut alors encore vérifier que cette nouvelle grammaire est bien
LR(0) en construisant l'analyseur ...
		

****