let build' p =
let count = ref 0 in
let transitions = ref [] in
let epsilons : (int * int) list ref = ref [] in
let state () = let id = !count in incr count; id in
let ( --> ) q1 t q2 =
match t with
| QEPSILON -> epsilons := (q1,q2) :: !epsilons; q1
| QCLASS cl -> transitions := (q1,cl,q2) :: !transitions; q1
in
let rec loop qf = function
| Epsilon -> qf
| Word u ->
let m = String.length u in
let q0 = state () in
let rec loop q i =
if i = m then
q0
else
begin
let q' =
if i = m - 1 then
qf
else
state ()
in
let _ = (q --> QCLASS(Atom(u.[i], u.[i]))) q' in
loop q' (i + 1)
end
in
loop q0 0
| Class cl ->
let q1 = state () in
(q1 --> QCLASS cl) qf
| Star p ->
let q2 = state () in
let q1 = loop q2 p in
let _ = (q1 --> QEPSILON) qf in
let _ = (q2 --> QEPSILON) q1 in
let _ = (q2 --> QEPSILON) q1 in
q1
| Concat(p1,p2) ->
let q12 = state () in
let q1 = loop q12 p1 in
let q2 = loop qf p2 in
let _ = (q12 --> QEPSILON) q2 in
q1
| Union pl ->
let qi = state () in
List.iter
begin fun p ->
let q = loop qf p in
let _ = (qi --> QEPSILON) q in
()
end
pl;
qi
in
let qf = state () in
let qi = loop qf p in
let m = !count in
let graph = Array.make m IS.empty in
List.iter
begin fun (q,q') ->
graph.(q) <- IS.add q' graph.(q)
end
!epsilons;
let closure = Array.make m IS.empty in
let rec transitive past = function
| [] -> past
| q :: future ->
let past' = IS.add q past in
let future' =
IS.fold
begin fun q' future' ->
if IS.mem q' past' then
future'
else
q' :: future'
end
graph.(q)
future
in
transitive past' future'
in
for i = 0 to m - 1 do
closure.(i) <- transitive IS.empty [i]
done;
let table = Array.make m [] in
List.iter
begin fun (q,t,q') ->
table.(q) <- (t, closure.(q')) :: table.(q)
end
!transitions;
(graph, closure,
{ mc_qi = closure.(qi);
mc_table = table;
mc_qf = qf;
mc_power_table = Hashtbl.create 37 })