Specification of grammar elements

The type of context-free grammars

The type of live CFGs

empty is the empty 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.

remove_nt gr nt removes nonterminal nt from grammar gr.

union gr1 gr2

• returns

  the union grammar of g1 and g2.

diff gr1 gr2

• returns

  the difference grammar of g1 and g2.

inter gr1 gr2

• returns

  the intersection grammar of g1 and g2.

grammar_of_live gr converts a live grammar to a normal grammar.

prune_unproductive gr prunes all unproductive entitites in gr.

prune_nonlive gr prunes all nonlive entities in gr.

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.

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.

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.

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.

grammar_contents gr returns a traversable representation of grammar gr.

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.

nts_in_grammar gr returns the set of all nonterminals in gr.

ts_in_grammar gr returns the set of all terminals in gr.

prods_in_grammar gr returns the set of all productions in gr.

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.