<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <link rel="stylesheet" href="style.css" type="text/css"> <meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type"> <link rel="Start" href="index.html"> <link rel="previous" href="Cfg_intf.SPEC.html"> <link rel="Up" href="Cfg_intf.html"> <link title="Index of types" rel=Appendix href="index_types.html"> <link title="Index of values" rel=Appendix href="index_values.html"> <link title="Index of modules" rel=Appendix href="index_modules.html"> <link title="Index of module types" rel=Appendix href="index_module_types.html"> <link title="Cfg_intf" rel="Chapter" href="Cfg_intf.html"> <link title="Cfg_impl" rel="Chapter" href="Cfg_impl.html"> <link title="Bnf_spec" rel="Chapter" href="Bnf_spec.html"> <link title="Bnf_pp" rel="Chapter" href="Bnf_pp.html"><title>Cfg_intf.CFG</title> </head> <body> <div class="navbar"><a href="Cfg_intf.SPEC.html">Previous</a> <a href="Cfg_intf.html">Up</a> </div> <center><h1>Module type <a href="type_Cfg_intf.CFG.html">Cfg_intf.CFG</a></h1></center> <br> <pre><span class="keyword">module type</span> CFG = <code class="code">sig</code> <a href="Cfg_intf.CFG.html">..</a> <code class="code">end</code></pre>Interface to context-free grammars<br> <hr width="100%"> <pre><span class="keyword">module</span> <a href="Cfg_intf.CFG.Spec.html">Spec</a>: <code class="type"><a href="Cfg_intf.SPEC.html">Cfg_intf.SPEC</a></code><code class="type"> </code></pre><div class="info"> Specification of grammar elements </div> <pre><span class="keyword">module</span> <a href="Cfg_intf.CFG.TSet.html">TSet</a>: <code class="type">Set.S</code><code class="type"> with type elt = t</code></pre><pre><span class="keyword">module</span> <a href="Cfg_intf.CFG.TMap.html">TMap</a>: <code class="type">Map.S</code><code class="type"> with type key = t</code></pre><pre><span class="keyword">module</span> <a href="Cfg_intf.CFG.NTSet.html">NTSet</a>: <code class="type">Set.S</code><code class="type"> with type elt = nt</code></pre><pre><span class="keyword">module</span> <a href="Cfg_intf.CFG.NTMap.html">NTMap</a>: <code class="type">Map.S</code><code class="type"> with type key = nt</code></pre><pre><span class="keyword">module</span> <a href="Cfg_intf.CFG.ProdSet.html">ProdSet</a>: <code class="type">Set.S</code><code class="type"> with type elt = prod * symbol list</code></pre><pre><span class="keyword">module</span> <a href="Cfg_intf.CFG.ProdMap.html">ProdMap</a>: <code class="type">Map.S</code><code class="type"> with type key = prod * symbol list</code></pre><pre><span class="keyword">type</span> <a name="TYPEgrammar"></a><code class="type"></code>grammar </pre> <div class="info"> The type of context-free grammars<br> </div> <pre><span class="keyword">type</span> <a name="TYPElive_grammar"></a><code class="type"></code>live_grammar </pre> <div class="info"> The type of live CFGs<br> </div> <pre><span class="keyword">val</span> <a name="VALempty"></a>empty : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">empty</code> is the empty grammar.<br> </div> <pre><span class="keyword">val</span> <a name="VALadd_prod"></a>add_prod : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -><br> Spec.nt -> Spec.prod -> Spec.symbol list -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">add_prod gr nt prod sl</code> adds a production with tag <code class="code">prod</code> that derives to symbol list <code class="code">sl</code> to nonterminal <code class="code">nt</code> in grammar <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALremove_nt"></a>remove_nt : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> Spec.nt -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">remove_nt gr nt</code> removes nonterminal <code class="code">nt</code> from grammar <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALunion"></a>union : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">union gr1 gr2</code><br> <b>Returns</b> the union grammar of <code class="code">g1</code> and <code class="code">g2</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALdiff"></a>diff : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">diff gr1 gr2</code><br> <b>Returns</b> the difference grammar of <code class="code">g1</code> and <code class="code">g2</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALinter"></a>inter : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">inter gr1 gr2</code><br> <b>Returns</b> the intersection grammar of <code class="code">g1</code> and <code class="code">g2</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALgrammar_of_live"></a>grammar_of_live : <code class="type"><a href="Cfg_intf.CFG.html#TYPElive_grammar">live_grammar</a> -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">grammar_of_live gr</code> converts a live grammar to a normal grammar.<br> </div> <pre><span class="keyword">val</span> <a name="VALprune_unproductive"></a>prune_unproductive : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">prune_unproductive gr</code> prunes all unproductive entitites in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALprune_nonlive"></a>prune_nonlive : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> <a href="Cfg_intf.CFG.html#TYPElive_grammar">live_grammar</a></code></pre><div class="info"> <code class="code">prune_nonlive gr</code> prunes all nonlive entities in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALprune_unreachable"></a>prune_unreachable : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> Spec.nt -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">prune_unreachable gr nt</code> prunes all entities in grammar <code class="code">gr</code> which cannot be reached from nonterminal <code class="code">nt</code>.<br> <b>Raises</b> <code>Not_found</code> if <code class="code">nt</code> is not in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALprune_unreachable_live"></a>prune_unreachable_live : <code class="type"><a href="Cfg_intf.CFG.html#TYPElive_grammar">live_grammar</a> -> Spec.nt -> <a href="Cfg_intf.CFG.html#TYPElive_grammar">live_grammar</a></code></pre><div class="info"> <code class="code">prune_unreachable_live gr nt</code> prunes all entities in live grammar <code class="code">gr</code> which cannot be reached from nonterminal <code class="code">nt</code>. The resulting grammar contains derivation information.<br> <b>Raises</b> <code>Not_found</code> if <code class="code">nt</code> is not in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALmake_sane"></a>make_sane : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> Spec.nt -> <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a></code></pre><div class="info"> <code class="code">make_sane gr nt</code> prunes all useless entities in grammar <code class="code">gr</code> using nonterminal <code class="code">nt</code> as start symbol.<br> <b>Raises</b> <code>Not_found</code> if <code class="code">nt</code> is not in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALmake_sane_live"></a>make_sane_live : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> Spec.nt -> <a href="Cfg_intf.CFG.html#TYPElive_grammar">live_grammar</a></code></pre><div class="info"> <code class="code">make_sane_live gr nt</code> prunes all useless entities in grammar <code class="code">gr</code> using nonterminal <code class="code">nt</code> as start symbol.<br> <b>Raises</b> <code>Not_found</code> if <code class="code">nt</code> is not in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALgrammar_contents"></a>grammar_contents : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> ProdSet.t NTMap.t</code></pre><div class="info"> <code class="code">grammar_contents gr</code> returns a traversable representation of grammar <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALderiv_depth_info"></a>deriv_depth_info : <code class="type"><a href="Cfg_intf.CFG.html#TYPElive_grammar">live_grammar</a> -><br> (int * int ProdMap.t) NTMap.t</code></pre><div class="info"> <code class="code">deriv_depth_info gr</code> returns a traversable representation of live grammar <code class="code">gr</code>: 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.<br> </div> <pre><span class="keyword">val</span> <a name="VALnts_in_grammar"></a>nts_in_grammar : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> NTSet.t</code></pre><div class="info"> <code class="code">nts_in_grammar gr</code> returns the set of all nonterminals in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALts_in_grammar"></a>ts_in_grammar : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> TSet.t</code></pre><div class="info"> <code class="code">ts_in_grammar gr</code> returns the set of all terminals in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALprods_in_grammar"></a>prods_in_grammar : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -> ProdSet.t</code></pre><div class="info"> <code class="code">prods_in_grammar gr</code> returns the set of all productions in <code class="code">gr</code>.<br> </div> <pre><span class="keyword">val</span> <a name="VALbounded_grammar"></a>bounded_grammar : <code class="type"><a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a> -><br> Spec.nt -> int -> (TSet.t * <a href="Cfg_intf.CFG.html#TYPEgrammar">grammar</a>) list</code></pre><div class="info"> <code class="code">bounded_grammar gr nt bound</code> computes a list of derivation levels from grammar <code class="code">gr</code>, starting at start symbol <code class="code">nt</code> and up to <code class="code">bound</code>. Each level contains a set of terminals and a partial grammar which belong into this level.<br> </div> </body></html>