<html>
<head>
<title>Symbols</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<link rel="stylesheet" href="theme/style.css" type="text/css">
</head>
<body>
<table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2">
<tr>
<td width="10">
</td>
<td width="85%">
<font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Symbols</b></font>
</td>
<td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td>
</tr>
</table>
<br>
<table border="0">
<tr>
<td width="10"></td>
<td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
<td width="30"><a href="distinct.html"><img src="theme/l_arr.gif" border="0"></a></td>
<td width="30"><a href="trees.html"><img src="theme/r_arr.gif" border="0"></a></td>
</tr>
</table>
<p>This class symbols implements a symbol table. The symbol table holds a dictionary
of symbols where each symbol is a sequence of CharTs (a <tt>char</tt>, <tt>wchar_t</tt>,
<tt>int</tt>, enumeration etc.) . The template class, parameterized by the character
type (CharT), can work efficiently with 8, 16, 32 and even 64 bit characters.
Mutable data of type T is associated with each symbol.<br>
</p>
<p>Traditionally, symbol table management is maintained seperately outside the
BNF grammar through semantic actions. Contrary to standard practice, the Spirit
symbol table class <tt>symbols</tt> is-a parser. An instance of which may be
used anywhere in the EBNF grammar specification. It is an example of a dynamic
parser. A dynamic parser is characterized by its ability to modify its behavior
at run time. Initially, an empty symbols object matches nothing. At any time,
symbols may be added, thus, dynamically altering its behavior.</p>
<p>Each entry in a symbol table has an associated mutable data slot. In this regard,
one can view the symbol table as an associative container (or map) of key-value
pairs where the keys are strings. </p>
<p>The symbols class expects two template parameters (actually there is a third,
see detail box). The first parameter <tt>T</tt> specifies the data type associated
with each symbol (defaults to <tt>int</tt>) and the second parameter <tt>CharT</tt>
specifies the character type of the symbols (defaults to <tt>char</tt>). </p>
<pre><span class=identifier> </span><span class=keyword>template
</span><span class=special><
</span><span class=keyword>typename </span><span class=identifier>T </span><span class=special>= </span><span class=keyword>int</span><span class=special>,
</span><span class=keyword>typename </span><span class=identifier>CharT </span><span class=special>= </span><span class=keyword>char</span><span class=special>,
</span><span class=keyword>typename </span><span class=identifier>SetT </span><span class=special>= </span><span class=identifier>impl</span><span class=special>::</span><span class=identifier>tst</span><span class=special><</span><span class=identifier>T</span><span class=special>, </span><span class=identifier>CharT</span><span class=special>>
</span><span class=special>>
</span><span class=keyword>class </span><span class=identifier>symbols</span><span class=special>;</span></pre>
<table width="80%" border="0" align="center">
<tr>
<td class="note_box"><img src="theme/lens.gif" width="15" height="16"> <b>Ternary
State Trees</b><br>
<br>
The actual set implementation is supplied by the SetT template parameter
(3rd template parameter of the symbols class) . By default, this uses the
tst class which is an implementation of the Ternary Search Tree. <br>
<br>
Ternary Search Trees are faster than hashing for many typical search problems
especially when the search interface is iterator based. Searching for a
string of length k in a ternary search tree with n strings will require
at most O(log n+k) character comparisons. TSTs are many times faster than
hash tables for unsuccessful searches since mismatches are discovered earlier
after examining only a few characters. Hash tables always examine an entire
key when searching.<br>
<br>
For details see <a href="http://www.cs.princeton.edu/%7Ers/strings/">http://www.cs.princeton.edu/~rs/strings/</a>.</td>
</tr>
</table>
<p>Here are some sample declarations:</p>
<pre><span class=identifier> </span><span class=identifier>symbols</span><span class=special><> </span><span class=identifier>sym</span><span class=special>;
</span><span class=identifier>symbols</span><span class=special><</span><span class=keyword>short</span><span class=special>, </span><span class=keyword>wchar_t</span><span class=special>> </span><span class=identifier>sym2</span><span class=special>;
</span><span class=keyword>struct </span><span class=identifier>my_info
</span><span class=special>{
</span><span class=keyword>int </span><span class=identifier>id</span><span class=special>;
</span><span class=keyword>double </span><span class=identifier>value</span><span class=special>;
</span><span class=special>};
</span><span class=identifier>symbols</span><span class=special><</span><span class=identifier>my_info</span><span class=special>> </span><span class=identifier>sym3</span><span class=special>;</span></pre>
<p>After having declared our symbol tables, symbols may be added statically using
the construct:</p>
<pre><span class=identifier> sym </span><span class=special>= </span><span class=identifier>a</span><span class=special>, </span><span class=identifier>b</span><span class=special>, </span><span class=identifier>c</span><span class=special>, </span><span class=identifier>d </span><span class=special>...;</span></pre>
<p>where <tt>sym</tt> is a symbol table and <tt>a..d</tt> etc. are strings. <img src="theme/note.gif" width="16" height="16">Note
that the comma operator is separating the items being added to the symbol table,
through an assignment. Due to operator overloading this is possible and correct
(though it may take a little getting used to) and is a concise way to initialize
the symbol table with many symbols. Also, it is perfectly valid to make multiple
assignments to a symbol table to iteratively add symbols (or groups of symbols)
at different times.</p>
<p>Simple example:<br>
</p>
<pre><span class=identifier> sym </span><span class=special>= </span><span class=string>"pineapple"</span><span class=special>, </span><span class=string>"orange"</span><span class=special>, </span><span class=string>"banana"</span><span class=special>, </span><span class=string>"apple"</span><span class=special>, </span><span class=string>"mango"</span><span class=special>;</span></pre>
<p>Note that it is invalid to add the same symbol multiple times to a symbol table,
though you may modify the value associated with a symbol artibrarily many times.</p>
<p>Now, we may use sym in the grammar. Example:</p>
<pre><span class=identifier> fruits </span><span class=special>= </span><span class=identifier>sym </span><span class=special>>> </span><span class=special>*(</span><span class=literal>',' </span><span class=special>>> </span><span class=identifier>sym</span><span class=special>);</span></pre>
<p>Alternatively, symbols may be added dynamically through the member functor
<tt>add</tt> (see <tt><a href="#symbol_inserter">symbol_inserter</a></tt> below).
The member functor <tt>add</tt> may be attached to a parser as a semantic action
taking in a begin/end pair:</p>
<pre><span class=identifier> p</span><span class=special>[</span><span class=identifier>sym</span><span class=special>.</span><span class=identifier>add</span><span class=special>]</span></pre>
<p>where p is a parser (and sym is a symbol table). On success, the matching portion
of the input is added to the symbol table.</p>
<p><tt>add</tt> may also be used to directly initialize data. Examples:</p>
<pre><span class=identifier> sym</span><span class=special>.</span><span class=identifier>add</span><span class=special>(</span><span class=string>"hello"</span><span class=special>, </span><span class=number>1</span><span class=special>)(</span><span class=string>"crazy"</span><span class=special>, </span><span class=number>2</span><span class=special>)(</span><span class=string>"world"</span><span class=special>, </span><span class=number>3</span><span class=special>);</span></pre>
<p>Assuming of course that the data slot associated with <tt>sym</tt> is an integer.</p>
<p>The data associated with each symbol may be modified any time. The most obvious
way of course is through <a href="semantic_actions.html">semantic actions</a>.
A function or functor, as usual, may be attached to the symbol table. The symbol
table expects a function or functor compatible with the signature:</p>
<p><b>Signature for functions:</b></p>
<pre><code><font color="#000000"><span class=identifier> </span><span class=keyword>void </span><span class=identifier>func</span><span class=special>(</span><span class=identifier>T</span><span class="special">&</span><span class=identifier> data</span><span class=special>);</span></font></code></pre>
<p><b>Signature for functors:</b><br>
</p>
<pre><code><font color="#000000"><span class=special> </span><span class=keyword>struct </span><span class=identifier>ftor
</span><span class=special>{
</span><span class=keyword>void </span><span class=keyword>operator</span><span class=special>()(</span><span class=identifier>T</span><span class="special">&</span><span class=identifier> data</span><span class=special>) </span><span class=keyword>const</span><span class=special>;
</span><span class=special>};</span></font></code></pre>
<p>Where <tt>T</tt> is the data type of the symbol table (the <tt>T</tt> in its
template parameter list). When the symbol table successfully matches something
from the input, the data associated with the matching entry in the symbol table
is reported to the semantic action.</p>
<h2>Symbol table utilities</h2>
<p>Sometimes, one may wish to deal with the symbol table directly. Provided are
some symbol table utilities.</p>
<p><b>add</b></p>
<pre><span class=identifier> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>T</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SetT</span><span class=special>>
</span><span class=identifier>T</span><span class=special>* </span><span class=identifier>add</span><span class=special>(</span><span class=identifier>symbols</span><span class=special><</span><span class=identifier>T</span><span class=special>, </span><span class=identifier>CharT</span><span class=special>, </span><span class=identifier>SetT</span><span class=special>>& </span><span class=identifier>table</span><span class=special>, </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>* </span><span class=identifier>sym</span><span class=special>, </span><span class=identifier>T </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>data </span><span class=special>= </span><span class=identifier>T</span><span class=special>());</span></pre>
<p>adds a symbol <tt>sym</tt> (C string) to a symbol table <tt>table</tt> plus
an optional data <tt>data</tt> associated with the symbol. Returns a pointer
to the data associated with the symbol or <tt>NULL</tt> if add failed (e.g.
when the symbol is already added before).<br>
<br>
<b>find</b></p>
<pre><span class=special> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>T</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SetT</span><span class=special>>
</span><span class=identifier>T</span><span class=special>* </span><span class=identifier>find</span><span class=special>(</span><span class=identifier>symbols</span><span class=special><</span><span class=identifier>T</span><span class=special>, </span><span class=identifier>CharT</span><span class=special>, </span><span class=identifier>SetT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>table</span><span class=special>, </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>* </span><span class=identifier>sym</span><span class=special>);</span></pre>
<p>finds a symbol <tt>sym</tt> (C string) from a symbol table <tt>table</tt>.
Returns a pointer to the data associated with the symbol or <tt>NULL</tt> if
not found</p>
<h2><a name="symbol_inserter"></a>symbol_inserter</h2>
<p>The symbols class holds an instance of this class named <tt>add</tt>. This
can be called directly just like a member function, passing in a first/last
iterator and optional data:<br>
<br>
</p>
<pre><span class=identifier> sym</span><span class=special>.</span><span class=identifier>add</span><span class=special>(</span><span class=identifier>first</span><span class=special>, </span><span class=identifier>last</span><span class=special>, </span><span class=identifier>data</span><span class=special>);</span></pre>
<p>Or, passing in a C string and optional data:<br>
</p>
<pre><span class=identifier> sym</span><span class=special>.</span><span class=identifier>add</span><span class=special>(</span><span class=identifier>c_string</span><span class=special>, </span><span class=identifier>data</span><span class=special>);</span></pre>
<p>where <tt>sym</tt> is a symbol table. The <tt>data</tt> argument is optional.
The nice thing about this scheme is that it can be cascaded. We've seen this
applied above. Here's a snippet from the roman numerals parser</p>
<pre> <span class=comment>// Parse roman numerals (1..9) using the symbol table.
</span> <span class=keyword>struct </span><span class=identifier>ones </span><span class=special>: </span><span class=identifier>symbols</span><span class=special><</span><span class=keyword>unsigned</span><span class=special>>
</span><span class=special>{
</span><span class=identifier>ones</span><span class=special>()
</span><span class=special>{
</span><span class=identifier>add
</span><span class=special>(</span><span class=string>"I" </span><span class=special>, </span><span class=number>1</span><span class=special>)
</span><span class=special>(</span><span class=string>"II" </span><span class=special>, </span><span class=number>2</span><span class=special>)
</span><span class=special>(</span><span class=string>"III" </span><span class=special>, </span><span class=number>3</span><span class=special>)
</span><span class=special>(</span><span class=string>"IV" </span><span class=special>, </span><span class=number>4</span><span class=special>)
</span><span class=special>(</span><span class=string>"V" </span><span class=special>, </span><span class=number>5</span><span class=special>)
</span><span class=special>(</span><span class=string>"VI" </span><span class=special>, </span><span class=number>6</span><span class=special>)
</span><span class=special>(</span><span class=string>"VII" </span><span class=special>, </span><span class=number>7</span><span class=special>)
</span><span class=special>(</span><span class=string>"VIII" </span><span class=special>, </span><span class=number>8</span><span class=special>)
</span><span class=special>(</span><span class=string>"IX" </span><span class=special>, </span><span class=number>9</span><span class=special>)
</span><span class=special>;
</span><span class=special>}
</span><span class=special>} </span><span class=identifier>ones_p</span><span class=special>;</span></pre>
<p>Notice that a user defined struct <tt>ones</tt> is subclassed from <tt>symbols</tt>.
Then at construction time, we added all the symbols using the <tt>add</tt> symbol_inserter.</p>
<p> <img height="16" width="15" src="theme/lens.gif"> The full source code can be <a href="../example/fundamental/roman_numerals.cpp">viewed here</a>. This is part of the Spirit distribution.</p>
<p>Again, <tt>add</tt> may also be used as a semantic action since it conforms
to the action interface (see semantic actions):<br>
</p>
<pre><span class=special></span><span class=identifier> p</span><span class=special>[</span><span class=identifier>sym</span><span class=special>.</span><span class=identifier>add</span><span class=special>]</span></pre>
<p>where p is a parser of course.<span class=special><br>
</span></p>
<table border="0">
<tr>
<td width="10"></td>
<td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
<td width="30"><a href="distinct.html"><img src="theme/l_arr.gif" border="0"></a></td>
<td width="30"><a href="trees.html"><img src="theme/r_arr.gif" border="0"></a></td>
</tr>
</table>
<br>
<hr size="1">
<p class="copyright">Copyright © 1998-2003 Joel de Guzman<br>
<br>
<font size="2">Use, modification and distribution is subject to the Boost Software
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt)</font></p>
</body>
</html>
