sig
module OrderedNamePairs :
sig
type t = Subtyping_letter.actual_letter
val compare : t -> t -> int
end
module TypeName_Glushkov :
sig
module Regexp :
sig
type position = int
module Position :
sig type t = position val compare : t -> t -> int end
module PositionSet :
sig
type elt = position
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
type letter = OrderedNamePairs.t
type regexp =
RSym of (letter * position)
| RSeq of (regexp * regexp)
| REmpty
| RChoice of (regexp * regexp)
| RNone
| RPlus of regexp
| RStar of regexp
| RAmp of (regexp * regexp)
val nullable : regexp -> bool
val pos : regexp -> PositionSet.t
val first : regexp -> PositionSet.t
val last : regexp -> PositionSet.t
val follow : regexp -> position -> PositionSet.t
val chi : regexp -> position -> letter
val star_normalize_aux : regexp -> regexp
val star_normalize : regexp -> regexp
end
module NFA :
sig
type state
type letter = OrderedNamePairs.t
module StateSet :
sig
type elt = int
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
module Alphabet :
sig
type elt = OrderedNamePairs.t
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
module StateToTransitionMap :
sig
type key = int
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val max_binding : 'a t -> key * 'a
val choose : 'a t -> key * 'a
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
end
module TransitionMap :
sig
type key = OrderedNamePairs.t
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val max_binding : 'a t -> key * 'a
val choose : 'a t -> key * 'a
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
end
type nfa = {
mutable nfa_states : StateSet.t;
mutable nfa_alphabet : Alphabet.t;
mutable nfa_start_state : StateSet.elt option;
mutable nfa_final_states : StateSet.t;
mutable nfa_transitions :
StateSet.t TransitionMap.t StateToTransitionMap.t;
}
val nfa_empty : nfa
val fresh_nfa_empty : unit -> nfa
val get_nfa_alphabet : nfa -> Alphabet.t
val add_letter : nfa -> Alphabet.elt -> unit
val add_all_letters : nfa -> Alphabet.t -> unit
val get_nfa_states : nfa -> StateSet.t
val get_nfa_start_state : nfa -> StateSet.elt option
val get_nfa_final_states : nfa -> StateSet.t
val add_state : nfa -> StateSet.elt -> unit
val set_start_state : nfa -> StateSet.elt -> unit
val set_final_states : nfa -> StateSet.t -> unit
val add_final_state : nfa -> StateSet.elt -> unit
val get_nfa_transitions :
nfa -> StateSet.t TransitionMap.t StateToTransitionMap.t
val get_TransitionMap :
nfa -> StateToTransitionMap.key -> StateSet.t TransitionMap.t
val get_destStateSet :
'a TransitionMap.t -> TransitionMap.key -> 'a
val get_destStateSet_s :
nfa ->
StateToTransitionMap.key -> TransitionMap.key -> StateSet.t
val add_transitions_aux :
nfa ->
StateToTransitionMap.key -> Alphabet.elt * StateSet.elt -> unit
val add_transitions :
nfa -> StateSet.elt -> (Alphabet.elt * StateSet.elt) list -> unit
val print_automata :
nfa -> (Alphabet.elt -> unit) -> (StateSet.elt -> unit) -> unit
val empty : nfa -> bool
end
module DFA :
sig
type state
type letter = OrderedNamePairs.t
module StateSet :
sig
type elt = int
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
module Alphabet :
sig
type elt = OrderedNamePairs.t
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
module StateToTransitionMap :
sig
type key = int
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val max_binding : 'a t -> key * 'a
val choose : 'a t -> key * 'a
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
end
module TransitionMap :
sig
type key = OrderedNamePairs.t
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val max_binding : 'a t -> key * 'a
val choose : 'a t -> key * 'a
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
end
type dfa = {
mutable dfa_states : StateSet.t;
mutable dfa_alphabet : Alphabet.t;
mutable dfa_start_state : StateSet.elt option;
mutable dfa_final_states : StateSet.t;
mutable dfa_transitions :
StateSet.elt TransitionMap.t StateToTransitionMap.t;
}
val dfa_empty : dfa
val fresh_dfa_empty : unit -> dfa
val get_dfa_alphabet : dfa -> Alphabet.t
val add_letter : dfa -> Alphabet.elt -> unit
val add_all_letters : dfa -> Alphabet.t -> unit
val get_dfa_states : dfa -> StateSet.t
val get_dfa_start_state : dfa -> StateSet.elt
val get_dfa_final_states : dfa -> StateSet.t
val add_state : dfa -> StateSet.elt -> unit
val set_start_state : dfa -> StateSet.elt -> unit
val set_final_states : dfa -> StateSet.t -> unit
val add_final_state : dfa -> StateSet.elt -> unit
val get_dfa_transitions :
dfa -> StateSet.elt TransitionMap.t StateToTransitionMap.t
val get_TransitionMap :
dfa -> StateToTransitionMap.key -> StateSet.elt TransitionMap.t
val get_destStateSet :
StateSet.elt TransitionMap.t -> TransitionMap.key -> StateSet.t
val get_destStateSet_s :
dfa ->
StateToTransitionMap.key -> TransitionMap.key -> StateSet.t
val add_transitions_aux :
dfa ->
StateToTransitionMap.key -> Alphabet.elt * StateSet.elt -> unit
val add_transitions :
dfa -> StateSet.elt -> (Alphabet.elt * StateSet.elt) list -> unit
val print_automata :
dfa -> (Alphabet.elt -> unit) -> (StateSet.elt -> unit) -> unit
end
module NFAPair :
sig
type state
type letter = OrderedNamePairs.t
module StateSet :
sig
type elt = int * int
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
module Alphabet :
sig
type elt = OrderedNamePairs.t
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
val for_all : (elt -> bool) -> t -> bool
val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> t * bool * t
val find : elt -> t -> elt
val of_list : elt list -> t
end
module StateToTransitionMap :
sig
type key = int * int
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val max_binding : 'a t -> key * 'a
val choose : 'a t -> key * 'a
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
end
module TransitionMap :
sig
type key = OrderedNamePairs.t
type +'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val max_binding : 'a t -> key * 'a
val choose : 'a t -> key * 'a
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
end
type nfa = {
mutable nfa_states : StateSet.t;
mutable nfa_alphabet : Alphabet.t;
mutable nfa_start_state : StateSet.elt option;
mutable nfa_final_states : StateSet.t;
mutable nfa_transitions :
StateSet.t TransitionMap.t StateToTransitionMap.t;
}
val nfa_empty : nfa
val fresh_nfa_empty : unit -> nfa
val get_nfa_alphabet : nfa -> Alphabet.t
val add_letter : nfa -> Alphabet.elt -> unit
val add_all_letters : nfa -> Alphabet.t -> unit
val get_nfa_states : nfa -> StateSet.t
val get_nfa_start_state : nfa -> StateSet.elt option
val get_nfa_final_states : nfa -> StateSet.t
val add_state : nfa -> StateSet.elt -> unit
val set_start_state : nfa -> StateSet.elt -> unit
val set_final_states : nfa -> StateSet.t -> unit
val add_final_state : nfa -> StateSet.elt -> unit
val get_nfa_transitions :
nfa -> StateSet.t TransitionMap.t StateToTransitionMap.t
val get_TransitionMap :
nfa -> StateToTransitionMap.key -> StateSet.t TransitionMap.t
val get_destStateSet :
'a TransitionMap.t -> TransitionMap.key -> 'a
val get_destStateSet_s :
nfa ->
StateToTransitionMap.key -> TransitionMap.key -> StateSet.t
val add_transitions_aux :
nfa ->
StateToTransitionMap.key -> Alphabet.elt * StateSet.elt -> unit
val add_transitions :
nfa -> StateSet.elt -> (Alphabet.elt * StateSet.elt) list -> unit
val print_automata :
nfa -> (Alphabet.elt -> unit) -> (StateSet.elt -> unit) -> unit
val empty : nfa -> bool
end
val build_glushkov : Regexp.regexp -> NFA.nfa
val build_dtm_glushkov : Regexp.regexp -> DFA.dfa
val negates_in_alphabet_space : DFA.dfa -> DFA.Alphabet.t -> DFA.dfa
val intersects : NFA.nfa -> NFA.nfa -> NFAPair.nfa
val intersects_dtm : NFA.nfa -> DFA.dfa -> NFAPair.nfa
val print_intersection :
(NFAPair.Alphabet.elt -> unit) ->
(NFAPair.StateSet.elt -> unit) -> NFAPair.nfa -> unit
end
end