1. (* TP03 - Exercice 2 - Correction *)
  2.  
  3. type regex = Vide | Eps | C of char | Sigma
  4. | Concat of regex * regex
  5. | Union of regex * regex
  6. | Etoile of regex
  7.  
  8. (* teste si une regexp matche sur une chaine de caractères *)
  9. let rec matche reg str = 
  10.   let n = String.length str in
  11.   match reg with
  12.   | Vide -> false
  13.   | Eps -> n = 0
  14.   | C c -> n = 1 && str.[0] = c
  15.   | Sigma -> n = 1
  16.   | Union (r1, r2) -> matche r1 str || matche r2 str
  17.   | Concat (r1, r2) -> 
  18.     (* on doit tester tous les découpages possibles *)
  19.     let success = ref false in
  20.     for i=0 to n do
  21.       if matche r1 (String.sub str 0 i) && matche r2 (String.sub str i (n-i)) then
  22.           success := true     (* peu efficace : on poursuit, même en cas de succès. *)
  23.     done;
  24.     !success
  25.   | Etoile r -> 
  26.     (* on doit tester tous les découpages possibles *)
  27.     if n = 0 then true (* cas particulier de la chaine vide *)
  28.     else
  29.     let success = ref false in
  30.     (* attention : le découpage chaine vide / chaine complète : risque de boucle infinie 
  31.        on teste à nouveau le matching de la même regexp sur la même chaîne *)
  32.     for i=1 to n do
  33.       if matche r (String.sub str 0 i) && matche reg (String.sub str i (n-i)) then
  34.           success := true     (* peu efficace : on poursuit, même en cas de succès *)
  35.     done;
  36.     !success
  37. ;;
  38.  
  39.  
  40. print_endline "Debut des tests";;
  41. (* la regexp vide *)
  42. assert (not (matche Vide "hello"));;
  43. assert (not (matche Vide ""));;
  44. (* la regexp epsilon *)
  45. assert (not (matche Eps "hello"));;
  46. assert (matche Eps "");;
  47. (* regexp à une lettre *)
  48. assert (not (matche (C 'a') "h"));;
  49. assert (not (matche (C 'a') ""));;
  50. assert (matche (C 'z') "z");;
  51. assert (not (matche (C 'z') "zz"));;
  52. assert (not (matche (C 'z') "az"));;
  53. (* regexp sigma *)
  54. assert (not (matche Sigma "ah"));;
  55. assert (not (matche Sigma ""));;
  56. assert (matche Sigma "z");;
  57. assert (matche Sigma "a");;
  58. (* union *)
  59. assert (matche (Union (Eps, C 'h')) "h");;
  60. assert (matche (Union (Eps, C 'h')) "");;
  61. assert (matche (Union (Vide, C 'h')) "h");;
  62. assert (matche (Union (C 'a', C 'b')) "a");;
  63. assert (matche (Union (C 'a', C 'b')) "b");;
  64. assert (not (matche (Union (Vide, C 'h')) ""));;
  65. assert (not (matche (Union (Eps, C 'h')) "a"));;
  66. (* concat *)
  67. assert (matche (Concat (Eps, C 'h')) "h");;
  68. assert (matche (Concat (C 'h', C 'e')) "he");;
  69. assert (not (matche (Concat (C 'h', C 'e')) "h"));;
  70. assert (not (matche (Concat (C 'h', C 'e')) "ae"));;
  71. assert (not (matche (Concat (C 'h', C 'e')) "hee"));;
  72. (* etoile *)
  73. assert (matche (Etoile (C 'e')) "");;
  74. assert (matche (Etoile (C 'e')) "e");;
  75. assert (matche (Etoile (C 'e')) "eeeee");;
  76. assert (not (matche (Etoile (C 'e')) "eeeeef"));;
  77. assert (not (matche (Etoile (C 'e')) "eefee"));;
  78. assert (matche (Etoile (Etoile (C 'e'))) "");;
  79. assert (matche (Etoile (Etoile (C 'e'))) "eeeee");;
  80. assert (not (matche (Etoile (Etoile (C 'e'))) "eeeeef"));;
  81.  
  82. (* la regexp (a.a|b.b)  *)
  83. let reg0 = Union (Concat (C 'a', Concat (Sigma, C 'a')),
  84.                   Concat (C 'b', Concat (Sigma, C 'b')));;
  85. assert (matche reg0 "aaa");;
  86. assert (matche reg0 "ara");;
  87. assert (matche reg0 "bib");;
  88. assert (matche reg0 "bob");;
  89. assert (not (matche reg0 "aab"));;
  90. assert (not (matche reg0 "abba"));;
  91. assert (not (matche reg0 "a"));;
  92.  
  93. (* la regexp (aa|b)*  *)
  94. let reg1 = Etoile (Union (Concat (C 'a', C 'a'), C 'b'));;
  95. assert (matche reg1 "");;
  96. assert (matche reg1 "aa");;
  97. assert (matche reg1 "bbbb");;
  98. assert (matche reg1 "aaaa");;
  99. assert (matche reg1 "baabbbaaaa");;
  100. assert (matche reg1 "aabaabbb");;
  101. assert (not (matche reg1 "a"));;
  102. assert (not (matche reg1 "aba"));;
  103. assert (not (matche reg1 "aabaaa"));;
  104.  
  105. (* la regexp a*ab  *)
  106. let reg2 = Concat (Concat (Etoile (C 'a'), C 'a'), C 'b');;
  107. assert (matche reg2 "ab");;
  108. assert (matche reg2 "aab");;
  109. assert (matche reg2 "aaaaab");;
  110. assert (not (matche reg2 "b"));;
  111. assert (not (matche reg2 "aba"));;
  112. assert (not (matche reg2 "aaaa"));;
  113.  
  114. print_endline "Fin des tests";;