type regexp = Void | Eps | Sym of char
              | Alt of regexp * regexp (* alternativa, reuniune *)
              | Seq of regexp * regexp (* secventiere, concatenare *)
              | Rep of regexp        (* inchidere Kleene=repetitie *)

(* expresia contine sirul vid ? *)
let rec haseps = function
  | Void | Sym _ -> false
  | Eps | Rep _ -> true        (* la Rep daca L nu e vid *)
  | Alt (e1, e2) -> haseps e1 || haseps e2
  | Seq (e1, e2) -> haseps e1 && haseps e2

(* expresia regulata care contine toate sirurile din e care incep cu a *)
let deriv a = 
  let rec drva = function
    | Sym c when a = c -> Eps
    | Alt (e1, e2) -> Alt (drva e1, drva e2)
    | Seq (e1, e2) -> let first = Seq (drva e1, e2)
                      in if haseps e1 then Alt (first, drva e2) else first
    | Rep e -> Seq (drva e, Rep e)
    | _ -> Void
  in drva

This document was generated using caml2html