| <!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> |
