(* 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"));;