open Nfa
open Regexp

let rex2nfa regex =
  let addeps src dest = SM.add src (EM.singleton None (S.singleton dest))
  and mapsum = SM.merge (fun _ -> function
    | None -> (function | None -> assert false | Some a -> Some a)
    | Some b -> (function | None -> Some b | Some _ -> assert false))
  and twoelem e1 e2 = S.add e2 (S.singleton e1) in
  let cntwrap cnt =
    let newstate() = (incr cnt; !cnt) in
    let rec r2n = function
      | Void -> { i = newstate(); f = newstate(); esm = SM.empty; }
      | Eps -> let s = newstate() in { i = s; f = s; esm = SM.empty; }
      | Char c -> let si = newstate() and sf = newstate() in {
        i = si; f = sf; esm = SM.singleton si (EM.singleton (Some c) (S.singleton sf)); }
      | Alt (e1, e2) -> let si = newstate() and a1 = r2n e1 and a2 = r2n e2 and sf = newstate() in {
        i = si; f = sf; esm = addeps a2.f sf (addeps a1.f sf (SM.add si (
          EM.singleton None (twoelem a1.i a2.i)) (mapsum a1.esm a2.esm))); }
      | Seq (e1, e2) -> let a1 = r2n e1 and a2 = r2n e2 in {
        i = a1.i; f = a2.f; esm = addeps a1.f a2.i (mapsum a1.esm a2.esm); }
      | Star e -> let si = newstate() and a = r2n e and sf = newstate() in {
        i = si; f = sf;        esm = let m2 = EM.singleton None (twoelem a.i sf)
                             in SM.add si m2 (SM.add a.f m2 a.esm); }
    in let res = r2n regex in { res with esm = SM.add res.f EM.empty res.esm; }
  in cntwrap (ref 0)

This document was generated using caml2html