home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Languages / Caml Light 0.7 / examples / grep / auto.ml next >
Encoding:
Text File  |  1995-06-01  |  1.6 KB  |  50 lines  |  [TEXT/MPS ]
  1. #open "expr";;
  2.  
  3. let compteur_d'états = ref 0;;
  4.  
  5. let nouvel_état () =
  6.   incr compteur_d'états;
  7.   { transitions = []; epsilon_transitions = [];
  8.     terminal = false; numéro = !compteur_d'états };;
  9.  
  10. let ajoute_trans n1 c n2 =
  11.   n1.transitions <- (c, n2) :: n1.transitions;;
  12.  
  13. let ajoute_eps_trans n1 n2 =
  14.   n1.epsilon_transitions <- n2 :: n1.epsilon_transitions;;
  15.  
  16. type automate_de_thompson =
  17.   { initial : état;
  18.     final   : état };;
  19.  
  20. let rec thompson = function
  21.     Epsilon ->
  22.       let e1 = nouvel_état() and e2 = nouvel_état() in
  23.       ajoute_eps_trans e1 e2;
  24.       {initial = e1; final = e2}
  25.   | Caractères cl ->
  26.       let e1 = nouvel_état() and e2 = nouvel_état() in
  27.       do_list (function c -> ajoute_trans e1 c e2) cl;
  28.       {initial = e1; final = e2}
  29.   | Alternative(r1, r2) ->
  30.       let t1 = thompson r1 and t2 = thompson r2 in
  31.       let e1 = nouvel_état() and e2 = nouvel_état() in
  32.       ajoute_eps_trans e1 t1.initial; ajoute_eps_trans e1 t2.initial;
  33.       ajoute_eps_trans t1.final e2;   ajoute_eps_trans t2.final e2;
  34.       {initial = e1; final = e2}
  35.   | Séquence(r1, r2) ->
  36.       let t1 = thompson r1 and t2 = thompson r2 in
  37.       ajoute_eps_trans t1.final t2.initial;
  38.       {initial = t1.initial; final = t2.final}
  39.   | Répétition r ->
  40.       let t = thompson r in
  41.       let e1 = nouvel_état() and e2 = nouvel_état() in
  42.       ajoute_eps_trans t.final t.initial;
  43.       ajoute_eps_trans e1 t.initial;
  44.       ajoute_eps_trans t.final e2;
  45.       ajoute_eps_trans e1 e2;
  46.       {initial = e1; final = e2};;
  47.  
  48. let expr_vers_automate r =
  49.   let t = thompson r in t.final.terminal <- true; t.initial;;
  50.