Sur les expressions arithmétiques, les grammaires, les parseurs en ocaml
on suppose que l'analyse lexicale a été faite à ce stade, on ne parle
que de l'analyse SYNTAXIQUE .

** étape 1 : expressions additives

Ce sont des expressions qui ne contiennent que des + et des - et des
entiers, donc on peut facilement écrire:

	E-> E+E | E-E | i

(i est un entier)


Le problème c'est que nos parseurs ocaml "mangent" les flots, c'est à
dire qu'un parseur de E écrit de la manière suivante :
     let rec parserE = parser
	 |  [< e1=parseurE; ' Tplus ;e2 = parserE >]
	 |  [< e1=parseurE; ' Tmoins;e2 = parserE >]
va commencer par manger (si il peut) la première partie de
l'expression pour suivre la première règle de filtrage et si il tombe
sur le token 'TMoins, l'analyse échoue car le parser a mangé la partie
du flot correpondant à l'expression e1, et se retrouve avec un flot
dont le premier token est Tmoins.

Il faut donc faire en sorte que le parseur n'ait pas le choix, en
"retardant" la décision de choix de la dérivation dans les règles:

	    E -> i A 
	    A -> + i A |  - i A  | eps

qui est la grammaire de l'énoncé du tp4.

Rque : cette grammaire suppose, tout comme la premiere grammaire, que
l'expression à analyser/parser est non vide. l'expression valide la
plus simple est un unique entier, par exemple 42.

(pour parler technique, cette grammaire est devenue LL(1)).

Maintenant, lorsqu'on écrit le parseur, c'est-à dire que l'on veut non
seulement analyser l'expression mais aussi obtenir un arbre
syntaxique, ie un arbre de type expr:
type expr = Plus of expr * expr 
	    | Moins of expr * expr 
	    | Int of int     ,

il faut construire l'arbre syntaxique au fur et à mesure de la
construction du flot. Pour cela, nous allons construire des parseurs
pour chaque règle, le parseur de la règle A construisant l'arbre
syntaxique. Pour cela, nous avons besoin d'une mémoire qui garde
l'expression à gauche du token 'Tplus que nous sommes en train de
traiter, puisque le flux a déjà été consommé et traité. C'est l'objet
de l'argument u de la fonction p_add ci dessous : 

let rec p_expr = parser
  | [< nb = p_terminal ; t=p_add nb>] -> t
and p_add u = parser
  | [< 'TPlus; t=p_terminal; res=p_add (Plus(u,t)) >] -> res
  | [< 'TMoins; t=p_terminal; res=p_add (Moins(u,t)) >] -> res
  | [< >] -> u
and p_terminal = parser
  | [< 'TEnt(n) >] -> Int(n)


(p_terminal est utilisé pour parser i, ce n'est pas forcément très
utile)

regardons maintenant les règles :

p_expr = parser
  | [< nb = p_terminal ; t=p_add nb>] -> t

ceci exprime que parser une expression c'est trouver un p_terminal (n)
et ensuite relancer le parseur de A (p_add) sur le reste du flux en
ayant gardé en mémoire l'entier n

p_add u = parser
  | [< 'TPlus; t=p_terminal; res=p_add (Plus(u,t)) >] -> res

cela signifie que pour parser une expression A avec l'accumulateur u
il faut avoir un token TPlus, et ensuite un p_terminal t et ensuite le
resultat de l'analyse c'est le resultat de l'analyse du reste du flux
avec comme nouvel accumulateur Plus(u,t) (c'est exactement la
grammaire, avec la construction de l'arbre en plus)

(l'évaluation des arbres syntaxiques est triviale ensuite)

** étape 2 : ajout de la multiplication

On ne peut ajouter l'opérateur de multiplication dans la
sous-grammaire A à la même hauteur que l'addition car sinon dans ce
cas l'analyse ne prend pas en compte les priorités, pour voir cela on
peut essayer d'évaluer les expressions 2+3*5 et 3*5+2 en ayant ajouté
la ligne   | [< 'TMult; t=p_terminal; res=p_add (Fois(u,t)) >] -> res
dans le parseur p_add...

On va donc modifier la grammaire pour avoir le bon arbre syntaxique,
qui prend en compte la priorité de * sur + :
	E -> E + T | E - T | T 
	T -> T * i | i
(la vérification pour les deux expressions + haut est laissée au lecteur)

On a le même problème que précédemment, on modifie la grammaire en
conséquence, en commençant par T (eps n'appartient pas a T)
	T -> T * i | i (pb de recursivité à gauche) devient :
	
	T -> i R
	R -> * i R | eps

maintenant, il faut aussi enlever la recursivité à gauche pour E :

	E-> T A
	A -> + T A | - T A | eps
	T -> i R
	R -> * i R | eps
	
bien vérifier que 2+5*3 et 5*3 + 2 peuvent etre deduites .
Cette grammaire peut maintenant être traduite, et c'est laissé au
lecteur ! 


Dernière remarque :
je ne sais pas si ça va vous servir, mais bon :
"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"


** étape 3, gestion des parenthèses.

à vous de jouer !