package cfg

  1. Overview
  2. Docs

Module Bnf_spec.BnfSource

Sourcemodule Spec = Spec

Specification of grammar elements

Sourcemodule TSet : Set.S with type elt = Spec.t
Sourcemodule TMap : Map.S with type key = Spec.t
Sourcemodule NTSet : Set.S with type elt = Spec.nt
Sourcemodule NTMap : Map.S with type key = Spec.nt
Sourcemodule ProdSet : Set.S with type elt = Spec.prod * Spec.symbol list
Sourcemodule ProdMap : Map.S with type key = Spec.prod * Spec.symbol list
Sourcetype grammar

The type of context-free grammars

Sourcetype live_grammar

The type of live CFGs

Sourceval empty : grammar

empty is the empty grammar.

Sourceval 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.

Sourceval remove_nt : grammar -> Spec.nt -> grammar

remove_nt gr nt removes nonterminal nt from grammar gr.

Sourceval union : grammar -> grammar -> grammar

union gr1 gr2

  • returns

    the union grammar of g1 and g2.

Sourceval diff : grammar -> grammar -> grammar

diff gr1 gr2

  • returns

    the difference grammar of g1 and g2.

Sourceval inter : grammar -> grammar -> grammar

inter gr1 gr2

  • returns

    the intersection grammar of g1 and g2.

Sourceval grammar_of_live : live_grammar -> grammar

grammar_of_live gr converts a live grammar to a normal grammar.

Sourceval prune_unproductive : grammar -> grammar

prune_unproductive gr prunes all unproductive entitites in gr.

Sourceval prune_nonlive : grammar -> live_grammar

prune_nonlive gr prunes all nonlive entities in gr.

Sourceval prune_unreachable : grammar -> Spec.nt -> grammar

prune_unreachable gr nt prunes all entities in grammar gr which cannot be reached from nonterminal nt.

Sourceval 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.

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

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

Sourceval 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.

Sourceval grammar_contents : grammar -> ProdSet.t NTMap.t

grammar_contents gr returns a traversable representation of grammar gr.

Sourceval 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.

Sourceval nts_in_grammar : grammar -> NTSet.t

nts_in_grammar gr returns the set of all nonterminals in gr.

Sourceval ts_in_grammar : grammar -> TSet.t

ts_in_grammar gr returns the set of all terminals in gr.

Sourceval prods_in_grammar : grammar -> ProdSet.t

prods_in_grammar gr returns the set of all productions in gr.

Sourceval 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.