(* TP03 - Exercice 2 *)

type regex = Vide | Eps | C of char | Sigma
| Concat of regex * regex
| Union of regex * regex
| Etoile of regex

(* teste si une regexp matche sur une chaine de caractères *)
let rec matche reg str = 
  let n = String.length str in
  failwith "à implémenter"
;;


print_endline "Debut des tests";;
(* la regexp vide *)
assert (not (matche Vide "hello"));;
assert (not (matche Vide ""));;
(* la regexp epsilon *)
assert (not (matche Eps "hello"));;
assert (matche Eps "");;
(* regexp à une lettre *)
assert (not (matche (C 'a') "h"));;
assert (not (matche (C 'a') ""));;
assert (matche (C 'z') "z");;
assert (not (matche (C 'z') "zz"));;
assert (not (matche (C 'z') "az"));;
(* regexp sigma *)
assert (not (matche Sigma "ah"));;
assert (not (matche Sigma ""));;
assert (matche Sigma "z");;
assert (matche Sigma "a");;
(* union *)
assert (matche (Union (Eps, C 'h')) "h");;
assert (matche (Union (Eps, C 'h')) "");;
assert (matche (Union (Vide, C 'h')) "h");;
assert (matche (Union (C 'a', C 'b')) "a");;
assert (matche (Union (C 'a', C 'b')) "b");;
assert (not (matche (Union (Vide, C 'h')) ""));;
assert (not (matche (Union (Eps, C 'h')) "a"));;
(* concat *)
assert (matche (Concat (Eps, C 'h')) "h");;
assert (matche (Concat (C 'h', C 'e')) "he");;
assert (not (matche (Concat (C 'h', C 'e')) "h"));;
assert (not (matche (Concat (C 'h', C 'e')) "ae"));;
assert (not (matche (Concat (C 'h', C 'e')) "hee"));;
(* etoile *)
assert (matche (Etoile (C 'e')) "");;
assert (matche (Etoile (C 'e')) "e");;
assert (matche (Etoile (C 'e')) "eeeee");;
assert (not (matche (Etoile (C 'e')) "eeeeef"));;
assert (not (matche (Etoile (C 'e')) "eefee"));;
assert (matche (Etoile (Etoile (C 'e'))) "");;
assert (matche (Etoile (Etoile (C 'e'))) "eeeee");;
assert (not (matche (Etoile (Etoile (C 'e'))) "eeeeef"));;

(* la regexp (a.a|b.b)  *)
let reg0 = Union (Concat (C 'a', Concat (Sigma, C 'a')),
                  Concat (C 'b', Concat (Sigma, C 'b')));;
assert (matche reg0 "aaa");;
assert (matche reg0 "ara");;
assert (matche reg0 "bib");;
assert (matche reg0 "bob");;
assert (not (matche reg0 "aab"));;
assert (not (matche reg0 "abba"));;
assert (not (matche reg0 "a"));;

(* la regexp (aa|b)*  *)
let reg1 = Etoile (Union (Concat (C 'a', C 'a'), C 'b'));;
assert (matche reg1 "");;
assert (matche reg1 "aa");;
assert (matche reg1 "bbbb");;
assert (matche reg1 "aaaa");;
assert (matche reg1 "baabbbaaaa");;
assert (matche reg1 "aabaabbb");;
assert (not (matche reg1 "a"));;
assert (not (matche reg1 "aba"));;
assert (not (matche reg1 "aabaaa"));;

(* la regexp a*ab  *)
let reg2 = Concat (Concat (Etoile (C 'a'), C 'a'), C 'b');;
assert (matche reg2 "ab");;
assert (matche reg2 "aab");;
assert (matche reg2 "aaaaab");;
assert (not (matche reg2 "b"));;
assert (not (matche reg2 "aba"));;
assert (not (matche reg2 "aaaa"));;

print_endline "Fin des tests";;