(** TP2 : Analyse Syntaxique Descendante
	Objectif : Realiser un analyseur syntaxique pour un certain langage.
		   Le code doit etre aisement modifiable et donc documente.

	@author BASSAND Guillaume
	@author NGouye Ndiaye
*)

(* Creation d'un analyseur syntaxique *)

open Analex;;
#load "analex.cma";;

(** Définition des unités lexicales telles que définies dans l'analyseur lexical *)
(*type ul = Ident of string | Operateur of string | ParentheseG | ParentheseD | ET | OU | EoF |  ERREUR of string ;;*)
UL_IDENT "ident";;

(** Definition des non-terminaux, cf la grammaire LL(1) du compte-rendu :

    E -> T B

    B -> "ou" E | epsilon

    T -> F G

    G -> "et" T | epsilon

    F -> R | ( E ) | "si" E "alors" E "sinon" E "fsi"

    R -> I O I

    O -> = | <> | < | > | >= | <=

    I -> Ident
*)
type vn = E | T | B | F | G | R | I | O ;;


(** Definition des terminaux :

    epsilon , = , <> , < , > , >= , <= , fsi , si , alors , sinon , et , ou
*)
type vt = Epsilon | Terminal of unite_lexicale;;

(** v correspond à l'union de Vt et Vn *)
type v = NonTerminal of vn | Term of vt;;


(** Construction d'un arbre concret *)
type arbre_concret = Noeud of (vn*arbre_concret list) |
				Feuille of vt
;;

(* test de l'arbre concret *)
Noeud(E,[Noeud(F,[Feuille(Terminal(UL_IDENT "et"));Feuille( Terminal(UL_IDENT "ou"))])]);;

(** Fonction de dérivation qui dérive un non terminal avec l'unite lexicale lue *)
let derivation (nonT,ulNext) =
  match nonT with E -> begin
    match ulNext with UL_IDENT(_)|UL_PAROUV|UL_SI -> [NonTerminal(T);NonTerminal(B)]
       |_ -> [Term(Terminal(UL_IDENT("ERREUR dans E")))]
  end
    | B -> begin
	match ulNext with UL_OU -> [Term(Terminal(UL_OU));NonTerminal(E)]
	  | _ -> [Term(Epsilon)]
      end
    |T -> begin
	 match ulNext with UL_IDENT(_) |UL_PAROUV |UL_SI -> [NonTerminal(F);NonTerminal(G)]
 |_ -> [Term(Terminal(UL_IDENT("ERREUR dans T")))]
       end
    |G -> begin
	 match ulNext with  UL_ET -> [Term(Terminal(UL_ET));NonTerminal(T)]
	   | _ -> [Term(Epsilon)]
       end
    |F ->  begin
	 match ulNext with UL_IDENT(_) -> [NonTerminal(R)]
	   |UL_PAROUV -> [Term(Terminal(UL_PAROUV));NonTerminal(E);Term(Terminal(UL_PARFERM))]
	   |UL_SI -> [Term(Terminal(UL_SI));NonTerminal(E);Term(Terminal(UL_ALORS));NonTerminal(E);Term(Terminal(UL_SINON));NonTerminal(E);Term(Terminal(UL_FSI))]
 |_ -> [Term(Terminal(UL_IDENT("ERREUR dans F")))]
       end
    |R ->begin
	 match ulNext with UL_IDENT(_) -> [NonTerminal(I);NonTerminal(O);NonTerminal(I)]
 |_ -> [Term(Terminal(UL_IDENT("ERREUR dans R")))]
       end
    |O -> begin
	 match ulNext with
	     UL_EGAL -> [Term(Terminal(UL_EGAL))]
	   | UL_DIFF -> [Term(Terminal(UL_DIFF))]
	   | UL_INF -> [Term(Terminal(UL_INF))]
	   | UL_SUP -> [Term(Terminal(UL_SUP))]
	   | UL_INF_EG -> [Term(Terminal(UL_INF_EG))]
	   | UL_SUP_EG -> [Term(Terminal(UL_SUP_EG))]
 |_ -> [Term(Terminal(UL_IDENT("ERREUR dans O")))]
       end
    |I -> begin
	 match ulNext with
	     UL_IDENT _ -> [Term(Terminal(ulNext))]
	   |_ -> [Term(Terminal(UL_IDENT("ERREUR dans I")))]
       end
;;

(* test de derivation *)
derivation(E,UL_IDENT("t"));;
derivation(T,UL_IDENT("t"));;
derivation(F,UL_IDENT("t"));;
derivation(R,UL_IDENT("t"));;
derivation(I,UL_IDENT("t"));;


(** Fonctions mutuellement récursives analyse_caractere et analyse_mot *)
(** analyse_caractere construit à partir d'une liste d'unités lexicales une feuille si elle rencontre
un terminal, et appelle analyse_mot si elle rencontre un non terminal *)
(** analyse_mot construit un noeud à partir d'un non terminal et d'une liste et de la meme liste d'unités lexicales
pour construire une liste d'arbres concrets. La liste d'objets de type v appel analyse_caractere pour le premier élément
et analyse_mot pour les suivants *)
let rec analyse_caractere (carac,ulList) =
  match carac with Term(_) -> begin
    match ulList with x::r when carac = Term(Terminal(x)) -> (Feuille (Terminal x),r)
      |_ -> (Feuille Epsilon,ulList)
  end
    | NonTerminal(e) -> begin
	match ulList with x::r -> let (arbList,newUlList) = analyse_mot(derivation (e,x),ulList)  in (Noeud(e,arbList),newUlList)
	  |_ -> (Feuille (Terminal(UL_IDENT("Erreur 2"))),[UL_ERR "error2"])
      end
and  analyse_mot (caracList,ulList) =
  match caracList with x::r -> let (arb,newList) = analyse_caractere(x,ulList) in  let (arbList,newUlList) = analyse_mot(r,newList)  in (arb::arbList,newUlList)
    | []->([],ulList)
;;