sig
  module Make :
    functor (Spec_ : Cfg_intf.SPEC->
      sig
        module Spec :
          sig
            type t = Spec_.t
            type nt = Spec_.nt
            type prod = Spec_.prod
            type symbol = Spec_.symbol = NT of nt | T of t
            val compare_t : t -> t -> int
            val compare_nt : nt -> nt -> int
            val compare_prod : prod -> prod -> int
          end
        module TSet :
          sig
            type elt = Spec.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) -> t -> '-> '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
          end
        module TMap :
          sig
            type key = Spec.t
            type +'a t
            val empty : 'a t
            val is_empty : 'a t -> bool
            val mem : key -> 'a t -> bool
            val add : key -> '-> 'a t -> 'a t
            val singleton : key -> '-> '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 : ('-> '-> int) -> 'a t -> 'a t -> int
            val equal : ('-> '-> bool) -> 'a t -> 'a t -> bool
            val iter : (key -> '-> unit) -> 'a t -> unit
            val fold : (key -> '-> '-> 'b) -> 'a t -> '-> 'b
            val for_all : (key -> '-> bool) -> 'a t -> bool
            val exists : (key -> '-> bool) -> 'a t -> bool
            val filter : (key -> '-> bool) -> 'a t -> 'a t
            val partition : (key -> '-> 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 : ('-> 'b) -> 'a t -> 'b t
            val mapi : (key -> '-> 'b) -> 'a t -> 'b t
          end
        module NTSet :
          sig
            type elt = Spec.nt
            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) -> t -> '-> '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
          end
        module NTMap :
          sig
            type key = Spec.nt
            type +'a t
            val empty : 'a t
            val is_empty : 'a t -> bool
            val mem : key -> 'a t -> bool
            val add : key -> '-> 'a t -> 'a t
            val singleton : key -> '-> '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 : ('-> '-> int) -> 'a t -> 'a t -> int
            val equal : ('-> '-> bool) -> 'a t -> 'a t -> bool
            val iter : (key -> '-> unit) -> 'a t -> unit
            val fold : (key -> '-> '-> 'b) -> 'a t -> '-> 'b
            val for_all : (key -> '-> bool) -> 'a t -> bool
            val exists : (key -> '-> bool) -> 'a t -> bool
            val filter : (key -> '-> bool) -> 'a t -> 'a t
            val partition : (key -> '-> 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 : ('-> 'b) -> 'a t -> 'b t
            val mapi : (key -> '-> 'b) -> 'a t -> 'b t
          end
        module ProdSet :
          sig
            type elt = Spec.prod * Spec.symbol list
            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) -> t -> '-> '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
          end
        module ProdMap :
          sig
            type key = Spec.prod * Spec.symbol list
            type +'a t
            val empty : 'a t
            val is_empty : 'a t -> bool
            val mem : key -> 'a t -> bool
            val add : key -> '-> 'a t -> 'a t
            val singleton : key -> '-> '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 : ('-> '-> int) -> 'a t -> 'a t -> int
            val equal : ('-> '-> bool) -> 'a t -> 'a t -> bool
            val iter : (key -> '-> unit) -> 'a t -> unit
            val fold : (key -> '-> '-> 'b) -> 'a t -> '-> 'b
            val for_all : (key -> '-> bool) -> 'a t -> bool
            val exists : (key -> '-> bool) -> 'a t -> bool
            val filter : (key -> '-> bool) -> 'a t -> 'a t
            val partition : (key -> '-> 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 : ('-> 'b) -> 'a t -> 'b t
            val mapi : (key -> '-> 'b) -> 'a t -> 'b t
          end
        type grammar
        type live_grammar
        val empty : grammar
        val add_prod :
          grammar -> Spec.nt -> Spec.prod -> Spec.symbol list -> grammar
        val remove_nt : grammar -> Spec.nt -> grammar
        val union : grammar -> grammar -> grammar
        val diff : grammar -> grammar -> grammar
        val inter : grammar -> grammar -> grammar
        val grammar_of_live : live_grammar -> grammar
        val prune_unproductive : grammar -> grammar
        val prune_nonlive : grammar -> live_grammar
        val prune_unreachable : grammar -> Spec.nt -> grammar
        val prune_unreachable_live : live_grammar -> Spec.nt -> live_grammar
        val make_sane : grammar -> Spec.nt -> grammar
        val make_sane_live : grammar -> Spec.nt -> live_grammar
        val grammar_contents : grammar -> ProdSet.t NTMap.t
        val deriv_depth_info : live_grammar -> (int * int ProdMap.t) NTMap.t
        val nts_in_grammar : grammar -> NTSet.t
        val ts_in_grammar : grammar -> TSet.t
        val prods_in_grammar : grammar -> ProdSet.t
        val bounded_grammar :
          grammar -> Spec.nt -> int -> (TSet.t * grammar) list
      end
end