home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Languages / Caml Light 0.7 / examples / grep / determ.ml < prev    next >
Encoding:
Text File  |  1995-06-01  |  2.1 KB  |  71 lines  |  [TEXT/MPS ]
  1. exception Échec;;
  2.  
  3. let reconnaît automate chaîne =
  4.   let état_courant = ref automate in 
  5.   try
  6.     for i = 0 to string_length chaîne - 1 do
  7.     match !état_courant.dtransitions.(int_of_char(nth_char chaîne i))
  8.     with Rejet  -> raise Échec
  9.        | Vers e -> état_courant := e
  10.     done;
  11.     !état_courant.dterminal
  12.   with Échec -> false;;
  13. #open "auto";;
  14.  
  15. type ensemble_d'états =
  16.   { contenu  : ensent__t;
  17.     éléments : auto__état list };;
  18. let vide = { contenu = ensent__vide; éléments = [] };;
  19. let est_vide ens =
  20.   match ens.éléments with [] -> true | _ -> false;;
  21. let appartient état ens =
  22.   ensent__appartient état.numéro ens.contenu;;
  23. let ajoute état ens =
  24.   { contenu  = ensent__ajoute état.numéro ens.contenu;
  25.     éléments = état :: ens.éléments };;
  26. let rec ajoute_fermeture état ferm =
  27.   if appartient état ferm then ferm else
  28.     list_it ajoute_fermeture
  29.             état.epsilon_transitions (ajoute état ferm);;
  30.  
  31. let fermeture état = ajoute_fermeture état vide;;
  32.  
  33. let fermeture_ens ens = list_it ajoute_fermeture ens.éléments vide;;
  34. let déplacements liste_états =
  35.   let t = make_vect 256 vide in
  36.   do_list
  37.     (function état ->
  38.       do_list
  39.         (function (car, dest) ->
  40.           let i = int_of_char car in t.(i) <- ajoute dest t.(i))
  41.       état.transitions)
  42.     liste_états;
  43.   t;;
  44. let déterminise état_initial =
  45.   let états_connus = hashtbl__new 51
  46.   and à_remplir = stack__new () in
  47.   let traduire ens =
  48.     try hashtbl__find états_connus ens.contenu
  49.     with Not_found ->
  50.       let nouvel_état =
  51.         { dterminal = exists (function n -> n.terminal) ens.éléments;
  52.           dtransitions = make_vect 256 Rejet } in
  53.       hashtbl__add états_connus ens.contenu nouvel_état;
  54.       stack__push (ens.éléments, nouvel_état) à_remplir;
  55.       nouvel_état in
  56.   let nouvel_état_initial =
  57.     traduire (fermeture état_initial) in
  58.   begin try
  59.     while true do
  60.       let (liste, nouvel_état) = stack__pop à_remplir in
  61.       let dépl = déplacements liste in
  62.       for i = 0 to 255 do
  63.         if not est_vide dépl.(i) then
  64.           nouvel_état.dtransitions.(i) <-
  65.             Vers(traduire (fermeture_ens dépl.(i)))
  66.       done
  67.     done
  68.   with stack__Empty -> ()
  69.   end;
  70.   nouvel_état_initial;;
  71.