(* TP03 - Exercice 2 - version étendue *)

type regex = Vide | Eps | C of char | Sigma
| Concat of regex * regex
| Union of regex * regex
| Etoile of regex
| Opt of regex  (*etendu*)
| NotC of char  (*etendu*)

exception Succes

(* teste si une regexp matche sur une chaine de caractères *)
let rec matche reg str = 
  let n = String.length str in
  match reg with
  | Vide -> false
  | Eps -> n = 0
  | Sigma -> n = 1
  | C c -> n = 1 && str.[0] = c
  | Union (r1, r2) -> matche r1 str || matche r2 str
  | Concat (r1, r2) -> 
    (* on doit tester tous les découpages possibles *)
    begin (* arret des le premier succes : avec un booleen et une boucle while *)
    let i = ref 0 in
    let success = ref false in
    while ((!i <= n) && (not !success)) do
      if matche r1 (String.sub str 0 !i) && matche r2 (String.sub str !i (n - !i)) then
        success := true;
      i := !i + 1
      done;
    !success
    end
  | Etoile r -> 
    (* on doit tester tous les découpages possibles *)
    if n = 0 then true 
    else
    begin (* arret des le premier succes : en utilisant une exception *)
      try 
        for i=1 to n do
          if matche r (String.sub str 0 i) && matche reg (String.sub str i (n-i)) then
            raise Succes
        done;
        false (* aucun découpage ne convient *)
      with
        Succes -> true
    end
  (* etendu *)
  | NotC c -> n = 1 && str.[0] <> c
  | Opt r -> n = 0 || matche r str
;;

assert (not (matche Vide "hello"));;
assert (not (matche Eps "hello"));;
assert (matche Eps "");;
assert (not (matche (C 'a') "h"));;
assert (matche (C 'h') "h");;
assert (matche (Union (Eps, C 'h')) "h");;
assert (matche (Union (Eps, C 'h')) "");;
assert (not (matche (Union (Eps, C 'h')) "a"));;
assert (matche (Concat (Eps, C 'h')) "h");;
assert (matche (Concat (C 'h', C 'e')) "he");;
assert (matche (Etoile (C 'e')) "eeeee");;
assert (not (matche (Etoile (C 'e')) "eeeeef"));;
assert (not (matche (Etoile (C 'e')) "eefee"));;

let reg0 = Etoile (Union (Concat (C 'a', C 'a'), C 'b'));;

assert (matche reg0 "");;
assert (matche reg0 "aa");;
assert (matche reg0 "bbbb");;
assert (matche reg0 "aaaa");;
assert (matche reg0 "baabbbaaaa");;
assert (matche reg0 "aabaabbb");;
assert (not (matche reg0 "a"));;
assert (not (matche reg0 "aba"));;
assert (not (matche reg0 "aabaaa"));;

let reg1 = Concat (Concat (Etoile (NotC ' '), C '@'), Etoile (NotC ' '));;

assert (matche reg1 "hello@gmail.com");;
assert (not (matche reg1 "hel lo@gmail.com"));;