<!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 exceptions" rel=Appendix href="index_exceptions.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="Bnf_spec" rel="Chapter" href="Bnf_spec.html">
<link title="Bnf_parser" rel="Chapter" href="Bnf_parser.html">
<link title="Bnf_lexer" rel="Chapter" href="Bnf_lexer.html">
<link title="Bnf_pp" rel="Chapter" href="Bnf_pp.html">
<link title="Cfg_intf" rel="Chapter" href="Cfg_intf.html">
<link title="Cfg_impl" rel="Chapter" href="Cfg_impl.html"><title>Cfg_intf.CFG</title>
</head>
<body>
<div class="navbar"><a class="pre" href="Cfg_intf.SPEC.html" title="Cfg_intf.SPEC">Previous</a>
<a class="up" href="Cfg_intf.html" title="Cfg_intf">Up</a>
</div>
<h1>Module type <a href="type_Cfg_intf.CFG.html">Cfg_intf.CFG</a></h1>
<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><div class="info modtype top">
Interface to context-free grammars<br>
</div>
<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 id="TYPEgrammar"><span class="keyword">type</span> <code class="type"></code>grammar</span> </pre>
<div class="info ">
The type of context-free grammars<br>
</div>
<pre><span id="TYPElive_grammar"><span class="keyword">type</span> <code class="type"></code>live_grammar</span> </pre>
<div class="info ">
The type of live CFGs<br>
</div>
<pre><span id="VALempty"><span class="keyword">val</span> empty</span> : <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 id="VALadd_prod"><span class="keyword">val</span> add_prod</span> : <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 id="VALremove_nt"><span class="keyword">val</span> remove_nt</span> : <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 id="VALunion"><span class="keyword">val</span> union</span> : <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 id="VALdiff"><span class="keyword">val</span> diff</span> : <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 id="VALinter"><span class="keyword">val</span> inter</span> : <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 id="VALgrammar_of_live"><span class="keyword">val</span> grammar_of_live</span> : <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 id="VALprune_unproductive"><span class="keyword">val</span> prune_unproductive</span> : <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 id="VALprune_nonlive"><span class="keyword">val</span> prune_nonlive</span> : <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 id="VALprune_unreachable"><span class="keyword">val</span> prune_unreachable</span> : <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 id="VALprune_unreachable_live"><span class="keyword">val</span> prune_unreachable_live</span> : <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 id="VALmake_sane"><span class="keyword">val</span> make_sane</span> : <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 id="VALmake_sane_live"><span class="keyword">val</span> make_sane_live</span> : <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 id="VALgrammar_contents"><span class="keyword">val</span> grammar_contents</span> : <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 id="VALderiv_depth_info"><span class="keyword">val</span> deriv_depth_info</span> : <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 id="VALnts_in_grammar"><span class="keyword">val</span> nts_in_grammar</span> : <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 id="VALts_in_grammar"><span class="keyword">val</span> ts_in_grammar</span> : <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 id="VALprods_in_grammar"><span class="keyword">val</span> prods_in_grammar</span> : <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 id="VALbounded_grammar"><span class="keyword">val</span> bounded_grammar</span> : <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>
