**** éléments de correction td2-LT-RICM2 ****
****Laurent Mounier et Laure Gonnord ****


Exercice 1 :  
------------

grammaire G1 :
	Z -> AbC
	A -> aA | epsilon
	C -> cC | epsilon
	
grammaire G2 :
	Z -> X
	X -> b | aXc
 
grammaire G3 :
	Z -> X 
	X -> abcc | Xc |  aXc


grammaire G4 :
	Z -> X
	X -> epsilon | aXa | bXb | cXc | a | b | c

attention à bien mettre les terminaux a,b,c car sinon on n'attrape pas
les palindromes de longueur impaire...


Exercice 2 : 
------------

1. 

Arbre de dérivation ou "parsing tree" : arbre obtenu avec les règles,
les noeuds sont des symboles non terminaux, les fils d'un noeud
correspondent à la règle dérivée : exemple par ici :
http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/main6/_9217_figure369.gif
ici :
http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/main6/node15.html
on trouvera une explicartion claire entre arbre de dérivation et arbre
syntaxique concret / arbre syntaxique abstrait.

On remarque en appliquant les règles que :
** à  chaque fois, un seul arbre syntaxique est faisable
** le jeu des parenthèses et des règles fait que on a :
l'associativité à gauche, et priorité du * sur le +.



2. Apres ajout du "-" unaire :
	
	Z -> E
	E -> E + T | T 
	T -> T * F | F
	F -> P | -P
	P -> i | e | (E)

3. Apres ajout du "-" binaire et du puissance :

	Z -> E
	E -> E + T | E - T | T 
	T -> T * F | F
	F -> G ^ F | G 		/* associativite a gauche */
	G -> P | -P
	P -> i | e | (E)

(vérifier sur un exemple que la grammaire proposee est correcte ...)


Exercice 3 : 
------------

1. UNE phrase ambigue est "if e then if e else a".

2. On peut le rendre non ambigue de la maniere suivante : 

	Z -> I
	I -> J | K
	J -> if e then J else J | a 
	K -> if e then I | if e then J else K

intuitivement, on choisit de "matcher" le else avec le if "le plus proche". 
	- J = instructions if-then-else "fermée" (ou a)
	- K = instructions if-then "ouverte" (terminée par un "then"). 

convaincus ?