Module type Cfg_intf.CFG

module type CFG = sig .. end
Interface to context-free grammars

module Spec: Cfg_intf.SPEC 
Specification of grammar elements
module TSet: Set.S  with type elt = t
module TMap: Map.S  with type key = t
module NTSet: Set.S  with type elt = nt
module NTMap: Map.S  with type key = nt
module ProdSet: Set.S  with type elt = prod * symbol list
module ProdMap: Map.S  with type key = prod * symbol list
type grammar 
The type of context-free grammars
type live_grammar 
The type of live CFGs
val empty : grammar
empty is the empty grammar.
val add_prod : grammar ->
Spec.nt -> Spec.prod -> Spec.symbol list -> grammar
add_prod gr nt prod sl adds a production with tag prod that derives to symbol list sl to nonterminal nt in grammar gr.
val remove_nt : grammar -> Spec.nt -> grammar
remove_nt gr nt removes nonterminal nt from grammar gr.
val union : grammar -> grammar -> grammar
union gr1 gr2
Returns the union grammar of g1 and g2.
val diff : grammar -> grammar -> grammar
diff gr1 gr2
Returns the difference grammar of g1 and g2.
val inter : grammar -> grammar -> grammar
inter gr1 gr2
Returns the intersection grammar of g1 and g2.
val grammar_of_live : live_grammar -> grammar
grammar_of_live gr converts a live grammar to a normal grammar.
val prune_unproductive : grammar -> grammar
prune_unproductive gr prunes all unproductive entitites in gr.
val prune_nonlive : grammar -> live_grammar
prune_nonlive gr prunes all nonlive entities in gr.
val prune_unreachable : grammar -> Spec.nt -> grammar
prune_unreachable gr nt prunes all entities in grammar gr which cannot be reached from nonterminal nt.
Raises Not_found if nt is not in gr.
val prune_unreachable_live : live_grammar -> Spec.nt -> live_grammar
prune_unreachable_live gr nt prunes all entities in live grammar gr which cannot be reached from nonterminal nt. The resulting grammar contains derivation information.
Raises Not_found if nt is not in gr.
val make_sane : grammar -> Spec.nt -> grammar
make_sane gr nt prunes all useless entities in grammar gr using nonterminal nt as start symbol.
Raises Not_found if nt is not in gr.
val make_sane_live : grammar -> Spec.nt -> live_grammar
make_sane_live gr nt prunes all useless entities in grammar gr using nonterminal nt as start symbol.
Raises Not_found if nt is not in gr.
val grammar_contents : grammar -> ProdSet.t NTMap.t
grammar_contents gr returns a traversable representation of grammar gr.
val deriv_depth_info : live_grammar ->
(int * int ProdMap.t) NTMap.t
deriv_depth_info gr returns a traversable representation of live grammar gr: the left part of the tuple to which nonterminals are mapped tells the minimum derivation depth needed to completely derive the corresponding nonterminal, the right part contains a map of productions which are mapped to their minimum derivation depth.
val nts_in_grammar : grammar -> NTSet.t
nts_in_grammar gr returns the set of all nonterminals in gr.
val ts_in_grammar : grammar -> TSet.t
ts_in_grammar gr returns the set of all terminals in gr.
val prods_in_grammar : grammar -> ProdSet.t
prods_in_grammar gr returns the set of all productions in gr.
val bounded_grammar : grammar ->
Spec.nt -> int -> (TSet.t * grammar) list
bounded_grammar gr nt bound computes a list of derivation levels from grammar gr, starting at start symbol nt and up to bound. Each level contains a set of terminals and a partial grammar which belong into this level.