package cfg

  1. Overview
  2. Docs

Module type Cfg_intf.CFGSource

Interface to context-free grammars

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.

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.

val make_sane : grammar -> Spec.nt -> grammar

make_sane gr nt prunes all useless entities in grammar gr using nonterminal nt as start symbol.

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.

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.