cfg 2.1.0 · OCaml Package

module Spec = Spec

Specification of grammar elements

module TSet : Set.S with type elt = Spec.t

module TMap : Map.S with type key = Spec.t

module NTSet : Set.S with type elt = Spec.nt

module NTMap : Map.S with type key = Spec.nt

module ProdSet : Set.S with type elt = Spec.prod * Spec.symbol list

module ProdMap : Map.S with type key = Spec.prod * Spec.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.

package cfg