accept.ml

type __ = Obj.t
let __ = let rec f _ = Obj.repr f in Obj.repr f

type 'a sig0 =
  'a
  (* singleton inductive, whose constructor was exist *)



type a = char

type regexp =
| Regexp_zero
| Regexp_unit
| Regexp_char of a
| Regexp_plus of regexp * regexp
| Regexp_times of regexp * regexp
| Regexp_star of regexp

type ('a, 'b) list_t = 'a option

(** val p_list_dec :
    ('a1 * 'a2) -> (('a1 * 'a2) -> __ -> bool) -> ('a1 -> 'a1 * 'a2) -> 'a1
    list -> ('a1, 'a2) list_t **)

let rec p_list_dec ab p_dec f = function
| [] -> None
| a0 :: l' -> if p_dec (f a0) __ then Some a0 else p_list_dec ab p_dec f l'

type regexps_no_c_t = regexp list

(** val regexps_no_c_F :
    (regexp * a) -> ((regexp * char) -> __ -> regexps_no_c_t) ->
    regexps_no_c_t **)

let regexps_no_c_F rc regexps_no_c_rec =
  match fst rc with
  | Regexp_char c -> if (=) c (snd rc) then Regexp_unit :: [] else []
  | Regexp_plus (r1, r2) ->
    List.append (regexps_no_c_rec (r1, (snd rc)) __)
      (regexps_no_c_rec (r2, (snd rc)) __)
  | Regexp_times (r, r2) ->
    (match r with
     | Regexp_zero -> []
     | Regexp_unit -> regexps_no_c_rec (r2, (snd rc)) __
     | Regexp_char c -> if (=) c (snd rc) then r2 :: [] else []
     | Regexp_plus (r11, r12) ->
       List.append (regexps_no_c_rec ((Regexp_times (r11, r2)), (snd rc)) __)
         (regexps_no_c_rec ((Regexp_times (r12, r2)), (snd rc)) __)
     | Regexp_times (r11, r12) ->
       regexps_no_c_rec ((Regexp_times (r11, (Regexp_times (r12, r2)))),
         (snd rc)) __
     | Regexp_star r1 ->
       List.append (regexps_no_c_rec (r2, (snd rc)) __)
         ((fun a b c -> List.fold_left a c b) (fun l r' -> (Regexp_times (r',
           (Regexp_times ((Regexp_star r1), r2)))) :: l)
           (regexps_no_c_rec (r1, (snd rc)) __) []))
  | Regexp_star r ->
    (fun a b c -> List.fold_left a c b) (fun l' r' -> (Regexp_times (r',
      (Regexp_star r))) :: l') (regexps_no_c_rec (r, (snd rc)) __) []
  | _ -> []

(** val regexps_no_c : (regexp * a) -> regexps_no_c_t **)

let rec regexps_no_c x =
  regexps_no_c_F x (fun y _ -> regexps_no_c y)

type accept_t = bool

(** val accept_list_dec :
    (regexp * char list) -> ((regexp * char list) -> __ -> bool) -> (regexp
    -> regexp * char list) -> regexp list -> (regexp, char list) list_t **)

let accept_list_dec ab p_dec f l =
  p_list_dec ab p_dec f l

(** val accept_F :
    (regexp * char list) -> ((regexp * char list) -> __ -> accept_t) ->
    accept_t **)

let accept_F rs accept_rec =
  match snd rs with
  | [] ->
    (match fst rs with
     | Regexp_zero -> false
     | Regexp_char _ -> false
     | Regexp_plus (r1, r2) ->
       if accept_rec (r1, []) __ then true else accept_rec (r2, []) __
     | Regexp_times (r1, r2) ->
       if accept_rec (r1, []) __ then accept_rec (r2, []) __ else false
     | _ -> true)
  | c::s' ->
    (match fst rs with
     | Regexp_char c' ->
       (match s' with
        | [] -> (=) c c'
        | _::_ -> false)
     | Regexp_plus (r1, r2) ->
       if accept_rec (r1, (c::s')) __
       then true
       else accept_rec (r2, (c::s')) __
     | Regexp_times (r, r2) ->
       (match r with
        | Regexp_zero -> false
        | Regexp_unit -> accept_rec (r2, (c::s')) __
        | Regexp_char c' ->
          if (=) c c' then accept_rec (r2, s') __ else false
        | Regexp_plus (r11, r12) ->
          if accept_rec ((Regexp_times (r11, r2)), (c::s')) __
          then true
          else accept_rec ((Regexp_times (r12, r2)), (c::s')) __
        | Regexp_times (r11, r12) ->
          accept_rec ((Regexp_times (r11, (Regexp_times (r12, r2)))),
            (c::s')) __
        | Regexp_star r1 ->
          if accept_rec (r2, (c::s')) __
          then true
          else (match accept_list_dec rs accept_rec (fun r0 -> ((Regexp_times
                        (r0, (Regexp_times ((Regexp_star r1), r2)))), s'))
                        (regexps_no_c (r1, c)) with
                | Some _ -> true
                | None -> false))
     | Regexp_star r' ->
       (match accept_list_dec rs accept_rec (fun r0 -> ((Regexp_times (r0,
                (Regexp_star r'))), s')) (regexps_no_c (r', c)) with
        | Some _ -> true
        | None -> false)
     | _ -> false)

(** val accept : (regexp * char list) -> accept_t **)

let rec accept x =
  accept_F x (fun y _ -> accept y)