← Back to branch summary

~ubuntu-branches/ubuntu/hardy/ocaml-doc/hardy

« back to all changes in this revision

Viewing changes to examples/grep/determ.ml

  • Committer: Bazaar Package Importer
  • Author(s): Samuel Mimram
  • Date: 2007-09-08 01:49:22 UTC
  • mfrom: (0.1.3 upstream)
  • Revision ID: james.westby@ubuntu.com-20070908014922-lvihyehz0ndq7suu
Tags: 3.10-1
* New upstream release.
* Removed camlp4 documentation since it is not up-to-date.
* Updated to standards version 3.7.2, no changes needed.
* Updated my email address.

Show diffs side-by-side

added added

removed removed

Lines of Context:
examples/grep/determ.ml
1
 
(***********************************************************************)
2
 
(*                                                                     *)
3
 
(*                           Objective Caml                            *)
4
 
(*                                                                     *)
5
 
(*               Pierre Weis, projet Cristal, INRIA Rocquencourt       *)
6
 
(*                                                                     *)
7
 
(*  Copyright 2001 Institut National de Recherche en Informatique et   *)
8
 
(*  en Automatique.  All rights reserved.  This file is distributed    *)
9
 
(*  only by permission.                                                *)
10
 
(*                                                                     *)
11
 
(***********************************************************************)
12
 
type �tat =
13
 
  { mutable dtransitions : transition array;
14
 
    dterminal : bool }
15
 
and transition =
16
 
  | Vers of �tat
17
 
  | Rejet;;
18
 
 
19
 
exception �chec;;
20
 
 
21
 
let reconna�t automate cha�ne =
22
 
  let �tat_courant = ref automate in 
23
 
  try
24
 
    for i = 0 to String.length cha�ne - 1 do
25
 
    match !�tat_courant.dtransitions.(int_of_char cha�ne.[i]) with
26
 
    | Rejet  -> raise �chec
27
 
    | Vers e -> �tat_courant := e
28
 
    done;
29
 
    !�tat_courant.dterminal
30
 
  with �chec -> false;;
31
 
 
32
 
open Auto;;
33
 
 
34
 
type ensemble_d'�tats =
35
 
  { contenu  : Ensent.t;
36
 
    �l�ments : Auto.�tat list };;
37
 
 
38
 
let vide = { contenu = Ensent.vide; �l�ments = [] };;
39
 
 
40
 
let est_vide ens =
41
 
  match ens.�l�ments with [] -> true | _ -> false;;
42
 
 
43
 
let appartient �tat ens =
44
 
  Ensent.appartient �tat.num�ro ens.contenu;;
45
 
 
46
 
let ajoute �tat ens =
47
 
  { contenu  = Ensent.ajoute �tat.num�ro ens.contenu;
48
 
    �l�ments = �tat :: ens.�l�ments };;
49
 
 
50
 
let rec ajoute_fermeture �tat ferm =
51
 
  if appartient �tat ferm then ferm else
52
 
    List.fold_right ajoute_fermeture
53
 
      �tat.epsilon_transitions (ajoute �tat ferm);;
54
 
 
55
 
let fermeture �tat = ajoute_fermeture �tat vide;;
56
 
 
57
 
let fermeture_ens ens = List.fold_right ajoute_fermeture ens.�l�ments vide;;
58
 
 
59
 
let d�placements liste_�tats =
60
 
  let t = Array.make 256 vide in
61
 
  List.iter
62
 
    (function �tat ->
63
 
      List.iter
64
 
        (function (car, dest) ->
65
 
          let i = int_of_char car in t.(i) <- ajoute dest t.(i))
66
 
      �tat.transitions)
67
 
    liste_�tats;
68
 
  t;;
69
 
 
70
 
let d�terminise �tat_initial =
71
 
  let �tats_connus = Hashtbl.create 51
72
 
  and �_remplir = Stack.create () in
73
 
  let traduire ens =
74
 
    try Hashtbl.find �tats_connus ens.contenu
75
 
    with Not_found ->
76
 
      let nouvel_�tat =
77
 
        { dterminal = List.exists (function n -> n.terminal) ens.�l�ments;
78
 
          dtransitions = Array.make 256 Rejet } in
79
 
      Hashtbl.add �tats_connus ens.contenu nouvel_�tat;
80
 
      Stack.push (ens.�l�ments, nouvel_�tat) �_remplir;
81
 
      nouvel_�tat in
82
 
  let nouvel_�tat_initial =
83
 
    traduire (fermeture �tat_initial) in
84
 
  begin try
85
 
    while true do
86
 
      let (liste, nouvel_�tat) = Stack.pop �_remplir in
87
 
      let d�pl = d�placements liste in
88
 
      for i = 0 to 255 do
89
 
        if not (est_vide d�pl.(i)) then
90
 
          nouvel_�tat.dtransitions.(i) <-
91
 
            Vers(traduire (fermeture_ens d�pl.(i)))
92
 
      done
93
 
    done
94
 
  with Stack.Empty -> ()
95
 
  end;
96
 
  nouvel_�tat_initial;;