sig
  module type SPEC =
    sig
      type t
      type nt
      type prod
      type symbol = NT of Cfg_intf.SPEC.nt | T of Cfg_intf.SPEC.t
      val compare_t : Cfg_intf.SPEC.t -> Cfg_intf.SPEC.t -> int
      val compare_nt : Cfg_intf.SPEC.nt -> Cfg_intf.SPEC.nt -> int
      val compare_prod : Cfg_intf.SPEC.prod -> Cfg_intf.SPEC.prod -> int
    end
  module type CFG =
    sig
      module Spec : SPEC
      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
        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
        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
        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 : Cfg_intf.CFG.grammar
      val add_prod :
        Cfg_intf.CFG.grammar ->
        Spec.nt -> Spec.prod -> Spec.symbol list -> Cfg_intf.CFG.grammar
      val remove_nt : Cfg_intf.CFG.grammar -> Spec.nt -> Cfg_intf.CFG.grammar
      val union :
        Cfg_intf.CFG.grammar -> Cfg_intf.CFG.grammar -> Cfg_intf.CFG.grammar
      val diff :
        Cfg_intf.CFG.grammar -> Cfg_intf.CFG.grammar -> Cfg_intf.CFG.grammar
      val inter :
        Cfg_intf.CFG.grammar -> Cfg_intf.CFG.grammar -> Cfg_intf.CFG.grammar
      val grammar_of_live : Cfg_intf.CFG.live_grammar -> Cfg_intf.CFG.grammar
      val prune_unproductive : Cfg_intf.CFG.grammar -> Cfg_intf.CFG.grammar
      val prune_nonlive : Cfg_intf.CFG.grammar -> Cfg_intf.CFG.live_grammar
      val prune_unreachable :
        Cfg_intf.CFG.grammar -> Spec.nt -> Cfg_intf.CFG.grammar
      val prune_unreachable_live :
        Cfg_intf.CFG.live_grammar -> Spec.nt -> Cfg_intf.CFG.live_grammar
      val make_sane : Cfg_intf.CFG.grammar -> Spec.nt -> Cfg_intf.CFG.grammar
      val make_sane_live :
        Cfg_intf.CFG.grammar -> Spec.nt -> Cfg_intf.CFG.live_grammar
      val grammar_contents :
        Cfg_intf.CFG.grammar -> Cfg_intf.CFG.ProdSet.t Cfg_intf.CFG.NTMap.t
      val deriv_depth_info :
        Cfg_intf.CFG.live_grammar ->
        (int * int Cfg_intf.CFG.ProdMap.t) Cfg_intf.CFG.NTMap.t
      val nts_in_grammar : Cfg_intf.CFG.grammar -> Cfg_intf.CFG.NTSet.t
      val ts_in_grammar : Cfg_intf.CFG.grammar -> Cfg_intf.CFG.TSet.t
      val prods_in_grammar : Cfg_intf.CFG.grammar -> Cfg_intf.CFG.ProdSet.t
      val bounded_grammar :
        Cfg_intf.CFG.grammar ->
        Spec.nt -> int -> (Cfg_intf.CFG.TSet.t * Cfg_intf.CFG.grammar) list
    end
end