<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content=
"HTML Tidy for Windows (vers 1st February 2003), see www.w3.org"
name="generator">
<title>
Basic Concepts
</title>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<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>Basic
Concepts</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="quick_start.html"><img src="theme/l_arr.gif" border="0"></a>
</td>
<td width="30">
<a href="organization.html"><img src="theme/r_arr.gif" border="0">
</a>
</td>
</tr>
</table>
<p>
There are a few fundamental concepts that need to be understood well: 1)
The <strong>Parser</strong>, 2) <strong>Match</strong>, 3) The
<strong>Scanner</strong>, and 4) <strong>Semantic Actions</strong>. These
basic concepts interact with one another, and the functionalities of each
interweave throughout the framework to make it one coherent whole.
</p>
<table width="48%" border="0" align="center">
<tr>
<td height="211">
<img src="theme/intro1.png">
</td>
</tr>
</table>
<h2>
The Parser
</h2>
<p>
Central to the framework is the parser. The parser does the actual work
of recognizing a linear input stream of data read sequentially from start
to end by the scanner. The parser attempts to match the input following a
well-defined set of specifications known as grammar rules. The parser
reports the success or failure to its client through a match object. When
successful, the parser calls a client-supplied semantic action. Finally,
the semantic action extracts structural information depending on the data
passed by the parser and the hierarchical context of the parser it is
attached to.
</p>
<p>
Parsers come in different flavors. The Spirit framework comes bundled
with an extensive set of pre-defined parsers that perform various parsing
tasks from the trivial to the complex. The parser, as a concept, has a
public conceptual interface contract. Following the contract, anyone can
write a conforming parser that will play along well with the framework's
predefined components. We shall provide a blueprint detailing the
conceptual interface of the parser later.
</p>
<p>
Clients of the framework generally do not need to write their own
hand-coded parsers at all. Spirit has an immense repertoire of
pre-defined parsers covering all aspects of syntax and semantic analysis.
We shall examine this repertoire of parsers in the following sections. In
the rare case where a specific functionality is not available, it is
extremely easy to write a user-defined parser. The ease in writing a
parser entity is the main reason for Spirit's extensibility.
</p>
<h2>
Primitives and Composites
</h2>
<p>
Spirit parsers fall into two categories: <b>primitives</b> and
<b>composites</b>. These two categories are more or less synonymous to
terminals and non-terminals in parsing lingo. Primitives are
non-decomposable atomic units. Composites on the other hand are parsers
that are composed of other parsers which can in turn be a primitive or
another composite. To illustrate, consider the Spirit expression:
</p>
<pre><code><font color="#000000"> </font></code><code><span class="identifier">real_p</span> <span class=
"special">>></span> <span class="special">*(</span><span class=
"literal">','</span> <span class="special">>></span> <span class=
"identifier">real_p</span><span class="special">)</span></code>
</pre>
<p>
<tt><tt>real_p</tt></tt> is a primitive parser that can parse real
numbers. The quoted comma <tt class="quotes">','</tt> in the expression
is a shortcut and is equivalent to <tt>ch_p<span class=
"operators">(</span><span class="quotes">','</span><span class=
"operators">)</span></tt>, which is another primitive parser that
recognizes single characters.
</p>
<p>
The expression above corresponds to the following parse tree:
</p>
<table width="29%" border="0" align="center">
<tr>
<td>
<img src="theme/intro7.png">
</td>
</tr>
</table>
<p>
The expression:
</p>
<pre><code><font color="#000000"> </font></code><span class=
"literal">','</span> <span class="special">>></span> <span class=
"identifier">real_p</span>
</pre>
<p>
composes a <b>sequence</b> parser. The <tt>sequence</tt> parser is a
composite parser comprising two parsers: the one on its left hand side
(lhs), <tt>ch_p<span class="operators">(</span><span class=
"quotes">','</span><span class="operators">)</span></tt> ; and the other
on its right hand side (rhs), <tt>real_p</tt>. This composite parser,
when called, calls its lhs and rhs in sequence and reports a successful
match only if both are successful.
</p>
<table width="14%" border="0" align="center">
<tr>
<td>
<img src="theme/intro2.png">
</td>
</tr>
</table>
<p>
The <tt>sequence</tt> parser is a binary composite. It is composed of two
parsers. There are unary composites as well. Unary composites hold only a
single subject. Like the binary composite, the unary composite may change
the behavior of its embedded subject. One particular example is the
<b>Kleene star</b>. The Kleene star, when called to parse, calls its sole
subject zero or more times. "Zero or more" implies that the Kleene star
always returns a successful match, possibly matching the null string: "".
</p>
<p>
The expression:
</p>
<pre><code><font color="#000000"> </font></code><code><span class=
"special">*(</span><span class="literal">','</span> <span class=
"special">>></span> <span class=
"identifier">real_p</span><span class="special">)</span></code>
</pre>
<p>
wraps the whole sequence composite above inside a <tt>kleene_star</tt>.
</p>
<table width="17%" border="0" align="center">
<tr>
<td>
<img src="theme/intro3.png">
</td>
</tr>
</table>
<p>
Finally, the full expression composes a <tt>real_p</tt> primitive parser
and the <tt>kleene_star</tt> we have above into another higher level
<tt>sequence</tt> parser composite.
</p>
<table width="34%" border="0" align="center">
<tr>
<td>
<img src="theme/intro4.png">
</td>
</tr>
</table>
<p>
A few simple classes, when composed and structured in a hierarchy, form a
very powerful object-oriented recursive-descent parsing engine. These
classes provide the infrastructure needed for the construction of
more-complex parsers. The final parser composite is a non-deterministic
recursive-descent parser with infinite look-ahead.
</p>
<p>
Top-down descent traverses the hierarchy. The outer <tt>sequence</tt>
calls the leftmost <tt>real_p</tt> parser. If successful, the
<tt>kleene_star</tt> is called next. The <tt>kleene_star</tt> calls the
inner <tt>sequence</tt> repeatedly in a loop until it fails to match, or
the input is exhausted. Inside, <tt>ch_p(',')</tt> and then
<tt>real_p</tt> are called in sequence. The following diagram illustrates
what is happening, somewhat reminiscent of Pascal syntax diagrams.
</p>
<table width="37%" border="0" align="center">
<tr>
<td>
<img src="theme/intro5.png">
</td>
</tr>
</table>
<p>
The flexibility of object embedding and composition combined with
recursion opens up a unique approach to parsing. Subclasses are free to
form aggregates and algorithms of arbitrary complexity. Complex parsers
can be created with the composition of only a few primitive classes.
</p>
<p>
The framework is designed to be fully open-ended and extensible. New
primitives or composites, from the trivial to the complex, may be added
any time. Composition happens (statically) at compile time. This is
possible through the expressive flexibility of C++ expression templates
and template meta-programming.
</p>
<p>
The result is a composite composed of primitives and smaller composites.
This embedding strategy gives us the ability to build hierarchical
structures that fully model EBNF expressions of arbitrary complexity.
Later on, we shall see more primitive and composite building blocks.
</p>
<h2>
The Scanner
</h2>
<p>
Like the parser, the scanner is also an abstract concept. The task of the
scanner is to feed the sequential input data stream to the parser. The
scanner is composed of two STL conforming forward iterators, first and
last, where first is held by reference and last, by value. The first
iterator is held by reference to allow re-positioning by the parser. A
set of policies governs how the scanner behaves. Parsers extract data
from the scanner and position the iterator appropriately through its
member functions.
</p>
<p>
Knowledge of the intricacies of these policies is not required at all in
most cases. However, knowledge of the scanner's basic API is required to
write fully-conforming Spirit parsers. The scanner's API will be outlined
in a separate section. In addition, for the power users and the
adventurous among us, a full section will be devoted to covering the
scanner policies. The scanner policies make Spirit very flexible and
extensible. For instance, some of the policies may be modified to filter
data. A practical example is a scanner policy that does not distinguish
upper and lower case whereby making it useful for parsing case
insensitive input. Another example is a scanner policy that strips white
spaces from the input.
</p>
<h2>
The Match
</h2>
<p>
The parser has a conceptual parse member function taking in a scanner and
returning a match object. The primary function of the match object is to
report parsing success (or failure) back to the parser's caller; i.e., it
evaluates to true if the parse function is successful, false otherwise.
If the parse is successful, the match object may also be queried to
report the number of characters matched (using <tt>match.length()</tt>).
The length is non-negative if the match is successful, and the typical
length of a parse failure is -1. A zero length is perfectly valid and
still represents a successful match.
</p>
<p>
Parsers may have attribute data associated with it. For example, the
real_p parser has a numeric datum associated with it. This attribute is
the parsed number. This attribute is passed on to the returned match
object. The match object may be queried to get this attribute. This datum
is valid only when the match is successful.
</p>
<h2>
Semantic Actions
</h2>
<p>
A composite parser forms a hierarchy. Parsing proceeds from the topmost
parent parser which delegates and apportions the parsing task to its
children recursively to its children's children and so on until a
primitive is reached. By attaching semantic actions to various points in
this hierarchy, in effect we can transform the flat linear input stream
into a structured representation. This is essentially what parsers do.
</p>
<p>
Recall our example above:
</p>
<pre><code><font color="#000000"> </font></code><code><span class=
"identifier">real_p</span> <span class=
"special">>></span> <span class="special">*(</span><span class=
"literal">','</span> <span class="special">>></span> <span class=
"identifier">real_p</span><span class="special">)</span></code>
</pre>
<p>
By hooking a function (or functor) into the real_p parsers, we can
extract the numbers from the input:
</p>
<pre><code><font color="#000000"> </font></code><span class=
"identifier">real_p</span><span class="special">[&</span><span class=
"identifier">f</span><span class="special">]</span> <span class=
"special">>></span> <span class="special">*(</span><span class=
"literal">','</span> <span class="special">>></span> <span class=
"identifier">real_p</span><span class="special">[&</span><span class=
"identifier">f</span><span class="special">])</span>
</pre>
<table width="41%" border="0" align="center">
<tr>
<td>
<img src="theme/intro6.png">
</td>
</tr>
</table>
<p> where <tt>f</tt> is a function that takes in a single argument. The <tt><span class="operators">[&</span>f<span class=
"operators">]</span></tt> hooks the parser with the function such that when
<tt>real_p</tt> recognizes a valid number, the function <tt>f</tt> is called.
It is up to the function then to do what is appropriate. For example, it can
stuff the numbers in a vector. Or perhaps, if the grammar is changed slightly
by replacing <tt class="quotes">','</tt> with <tt class="quotes">'+'</tt>, then
we have a primitive calculator that computes sums. The function <tt>f</tt> then
can then be made to add all incoming numbers.<br>
</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="quick_start.html"><img src="theme/l_arr.gif" border="0"></a>
</td>
<td width="30">
<a href="organization.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>
<p>
</p>
</body>
</html>
