(* USAGE:

 * Pour afficher la traduction en ocaml:
      camlp4o -impl anbn.parser

 * Pour g�n�rer  la traduction dans un fichier .ml:
      camlp4o -impl anbn.parser -o anbn.ml

 * Pour interpr�ter le fichier ocaml g�n�r�:
      ledit ocaml dynlink.cma camlp4o.cma
      #use "anbn.ml";;
 *)


(* STREAM.is_empty does not exist. We define it to check if a stream is empty *)

let (is_empty: 't Stream.t -> bool) =
  fun stream -> Stream.peek stream = None



(* EXERCISE
   ===============================================================
   Implement in ocaml the following grammar

     S -1-> ""
     S -2-> "a" . S . "b"

   The language generated by this grammar is { a^b^n | n in Nat }

   This grammar is not ambigous since, given n in Nat,
   there is only one way to derive a^nb^n.
   =============================================================== *)


(* -1- A RECOGNIZER *)

let rec (anbn_recognizer: char Stream.t -> bool) =
  parser
  | [< ' 'a' ; bool = anbn_recognizer ; ' 'b' >] -> bool
  | [< >] -> true
;;

let (run:  (char Stream.t -> bool) -> string -> bool) =
  fun parse word ->
	begin
	  print_string (String.concat "" [ "\n parser \"" ; word ; "\" = \n"]) ;
	  let stream = Stream.of_string word
	  in let recognized = parse stream
	  and empty = is_empty stream (* the parser red all the stream *)
	  in empty && recognized
	end
;;


(* TEST *)

run anbn_recognizer "" ;;

run anbn_recognizer "ab" ;;

run anbn_recognizer "aabb" ;;

run anbn_recognizer "ba" ;;



(* -2- A PARSER that counts the number of "a" in the word *)

let rec (anbn_parser_with_counter: char Stream.t -> int) =
  parser
  | [< ' 'a' ; n = anbn_parser_with_counter ; ' 'b' >] -> n+1
  | [< >] -> 0
;;

let (run:  (char Stream.t -> int) -> string -> bool * int) =
  fun parse word ->
	begin
	  print_string (String.concat "" [ "\n parser \"" ; word ; "\" = \n"]) ;
	  let stream = Stream.of_string word
	  in let result = parse stream
	  and empty = is_empty stream
	  in (empty,result)
	end
;;


(* TEST *)

run anbn_parser_with_counter "" ;;

run anbn_parser_with_counter "ab" ;;

run anbn_parser_with_counter "aabb" ;;

run anbn_parser_with_counter "ba" ;;



(* -3- A PARSER that builds the derivation tree of the word *)

type nonterminal = S

type rule = int

type derivation_tree =
  | D of nonterminal * rule * derivation_tree list
  | L of char
  | Erreur


let rec (anbn_parser_with_derivation_tree: char Stream.t -> derivation_tree) =
  parser
  | [< ' 'a' ; d = anbn_parser_with_derivation_tree ; ' 'b' >]
      -> D(S,1,[L 'a' ; d ; L 'b'])
  | [< >] -> D(S,0,[])
;;

let (run:  (char Stream.t -> 'result) -> string -> bool * 'result) =
  fun parse word ->
	begin
	  print_string (String.concat "" [ "\n parser \"" ; word ; "\" = \n"]) ;
	  let stream = Stream.of_string word
	  in let result = parse stream
	  and empty = is_empty stream
	  in (empty,result)
	end
;;


(* TEST *)

run anbn_parser_with_derivation_tree "" ;;

run anbn_parser_with_derivation_tree "ab" ;;

run anbn_parser_with_derivation_tree "aabb" ;;

run anbn_parser_with_derivation_tree "ba" ;;