Preface

History

A decade and a half ago, I wrote my first calculator in Pascal. It is one of my most unforgettable coding experiences. I was amazed how a mutually recursive set of functions can model a grammar specification. In time, the skills I acquired from that academic experience became very practical. Periodically I was tasked to do some parsing. For instance, whenever I need to perform any form of I/O, even in binary, I try to approach the task somewhat formally by writing a grammar using Pascal-like syntax diagrams and then write a corresponding recursive-descent parser. This worked very well.

The arrival of the Internet and the World Wide Web magnified this thousand-fold. At one point I had to write an HTML parser for a Web browser project. I got a recursive-descent HTML parser working based on the W3C formal specifications easily. I was certainly glad that HTML had a formal grammar specification. Because of the influence of the Internet, I then had to do more parsing. RFC specifications were everywhere. SGML, HTML, XML, even email addresses and those seemingly trivial URLs were all formally specified using small EBNF-style grammar specifications. This made me wish for a tool similar to big-time parser generators such as YACC and ANTLR, where a parser is built automatically from a grammar specification. Yet, I want it to be extremely small; small enough to fit in my pocket, yet scalable.

It must be able to practically parse simple grammars such as email addresses to moderately complex grammars such as XML and perhaps some small to medium-sized scripting languages. Scalability is a prime goal. You should be able to use it for small tasks such as parsing command lines without incurring a heavy payload, as you do when you are using YACC or PCCTS. Even now that it has evolved and matured to become a multi-module library, true to its original intent, Spirit can still be used for extreme micro-parsing tasks. You only pay for features that you need. The power of Spirit comes from its modularity and extensibility. Instead of giving you a sledgehammer, it gives you the right ingredients to create a sledgehammer easily. For instance, it does not really have a lexer, but you have all the raw ingredients to write one, if you need one.

The result was Spirit. Spirit was a personal project that was conceived when I was doing R&D in Japan. Inspired by the GoF's composite and interpreter patterns, I realized that I can model a recursive-descent parser with hierarchical-object composition of primitives (terminals) and composites (productions). The original version was implemented with run-time polymorphic classes. A parser is generated at run time by feeding in production rule strings such as "prod ::= {‘A’ | ‘B’} ‘C’;"A compile function compiled the parser, dynamically creating a hierarchy of objects and linking semantic actions on the fly. A very early text can be found here.

The version that we have now is a complete rewrite of the original Spirit parser using expression templates and static polymorphism, inspired by the works of Todd Veldhuizen (" Expression Templates", C++ Report, June 1995). Initially, the static-Spirit version was meant only to replace the core of the original dynamic-Spirit. Dynamic-spirit needed a parser to implement itself anyway. The original employed a hand-coded recursive-descent parser to parse the input grammar specification strings.

After its initial "open-source" debut in May 2001, static-Spirit became a success. At around November 2001, the Spirit website had an activity percentile of 98%, making it the number one parser tool at Source Forge at the time. Not bad for such a niche project such as a parser library. The "static" portion of Spirit was forgotten and static-Spirit simply became Spirit. The framework soon evolved to acquire more dynamic features.

How to use this manual

The Spirit framework is organized in logical modules starting from the core. This documentation provides a user's guide and reference for each module in the framework. A simple and clear code example is worth a hundred lines of documentation; therefore, the user's guide is presented with abundant examples annotated and explained in step-wise manner. The user's guide is based on examples -lots of them.

As much as possible, forward information (i.e. citing a specific piece of information that has not yet been discussed) is avoided in the user's manual portion of each module. In many cases, though, it is unavoidable that advanced but related topics are interspersed with the normal flow of discussion. To alleviate this problem, topics categorized as "advanced" may be skipped at first reading.

Some icons are used to mark certain topics indicative of their relevance. These icons precede some text to indicate:

Icons Note Information provided is moderately important and should be noted by the reader. Alert Information provided is of utmost importance. Detail Information provided is auxiliary but will give the reader a deeper insight into a specific topic. May be skipped. Tip A potentially useful and helpful piece of information.

Support

Please direct all questions to Spirit's mailing list. You can subscribe to the mailing list here. The mailing list has a searchable archive. A search link to this archive is provided in Spirit's home page. You may also read and post messages to the mailing list through an NNTP news portal (thanks to www.gmane.org). The news group mirrors the mailing list. Here are two links to the archives: via gmane, via geocrawler.

Copyright © 1998-2003 Joel de Guzman

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)

Introduction

Spirit is an object-oriented recursive-descent parser generator framework implemented using template meta-programming techniques. Expression templates allow us to approximate the syntax of Extended Backus-Normal Form (EBNF) completely in C++.

The Spirit framework enables a target grammar to be written exclusively in C++. Inline EBNF grammar specifications can mix freely with other C++ code and, thanks to the generative power of C++ templates, are immediately executable. In retrospect, conventional compiler-compilers or parser-generators have to perform an additional translation step from the source EBNF code to C or C++ code.

A simple EBNF grammar snippet:

    group       ::= '(' expression ')'
    factor      ::= integer | group
    term        ::= factor (('*' factor) | ('/' factor))*
    expression  ::= term (('+' term) | ('-' term))*

is approximated using Spirit's facilities as seen in this code snippet:

    group       = '(' >> expression >> ')';
    factor      = integer | group;
    term        = factor >> *(('*' >> factor) | ('/' >> factor));
    expression  = term >> *(('+' >> term) | ('-' >> term));

Through the magic of expression templates, this is perfectly valid and executable C++ code. The production rule expression is in fact an object that has a member function parse that does the work given a source code written in the grammar that we have just declared. Yes, it's a calculator. We shall simplify for now by skipping the type declarations and the definition of the rule integer invoked by factor. The production rule expression in our grammar specification, traditionally called the start symbol, can recognize inputs such as:

    12345
    -12345
    +12345
    1 + 2
    1 * 2
    1/2 + 3/4
    1 + 2 + 3 + 4
    1 * 2 * 3 * 4
    (1 + 2) * (3 + 4)
    (-1 + 2) * (3 + -4)
    1 + ((6 * 200) - 20) / 6
    (1 + (2 + (3 + (4 + 5))))

Certainly we have done some modifications to the original EBNF syntax. This is done to conform to C++ syntax rules. Most notably we see the abundance of shift >> operators. Since there are no 'empty' operators in C++, it is simply not possible to write something like:

    a b

as seen in math syntax, for example, to mean multiplication or, in our case, as seen in EBNF syntax to mean sequencing (b should follow a). The framework uses the shift >> operator instead for this purpose. We take the >> operator, with arrows pointing to the right, to mean "is followed by". Thus we write:

    a >> b

The alternative operator | and the parentheses () remain as is. The assignment operator = is used in place of EBNF's ::=. Last but not least, the Kleene star * which used to be a postfix operator in EBNF becomes a prefix. Instead of:

    a* //... in EBNF syntax,

we write:

    *a //... in Spirit.

since there are no postfix stars, "*", in C/C++. Finally, we terminate each rule with the ubiquitous semi-colon, ";".

Copyright © 1998-2003 Joel de Guzman

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)

Quick Start

Why would you want to use Spirit?

Spirit is designed to be a practical parsing tool. At the very least, the ability to generate a fully-working parser from a formal EBNF specification inlined in C++ significantly reduces development time. While it may be practical to use a full-blown, stand-alone parser such as YACC or ANTLR when we want to develop a computer language such as C or Pascal, it is certainly overkill to bring in the big guns when we wish to write extremely small micro-parsers. At that end of the spectrum, programmers typically approach the job at hand not as a formal parsing task but through ad hoc hacks using primitive tools such as scanf. True, there are tools such as regular-expression libraries (such as boost regex) or scanners (such as boost tokenizer), but these tools do not scale well when we need to write more elaborate parsers. Attempting to write even a moderately-complex parser using these tools leads to code that is hard to understand and maintain.

One prime objective is to make the tool easy to use. When one thinks of a parser generator, the usual reaction is "it must be big and complex with a steep learning curve." Not so. Spirit is designed to be fully scalable. The framework is structured in layers. This permits learning on an as-needed basis, after only learning the minimal core and basic concepts.

For development simplicity and ease in deployment, the entire framework consists of only header files, with no libraries to link against or build. Just put the spirit distribution in your include path, compile and run. Code size? -very tight. In the quick start example that we shall present in a short while, the code size is dominated by the instantiation of the std::vector and std::iostream.

Trivial Example #1

Create a parser that will parse a floating-point number.

    real_p

(You've got to admit, that's trivial!) The above code actually generates a Spirit real_parser (a built-in parser) which parses a floating point number. Take note that parsers that are meant to be used directly by the user end with "_p" in their names as a Spirit convention. Spirit has many pre-defined parsers and consistent naming conventions help you keep from going insane!

Trivial Example #2

Create a parser that will accept a line consisting of two floating-point numbers.

    real_p >> real_p

Here you see the familiar floating-point numeric parser real_p used twice, once for each number. What's that >> operator doing in there? Well, they had to be separated by something, and this was chosen as the "followed by" sequence operator. The above program creates a parser from two simpler parsers, glueing them together with the sequence operator. The result is a parser that is a composition of smaller parsers. Whitespace between numbers can implicitly be consumed depending on how the parser is invoked (see below).

Note: when we combine parsers, we end up with a "bigger" parser, But it's still a parser. Parsers can get bigger and bigger, nesting more and more, but whenever you glue two parsers together, you end up with one bigger parser. This is an important concept.

Trivial Example #3

Create a parser that will accept an arbitrary number of floating-point numbers. (Arbitrary means anything from zero to infinity)

    *real_p

This is like a regular-expression Kleene Star, though the syntax might look a bit odd for a C++ programmer not used to seeing the * operator overloaded like this. Actually, if you know regular expressions it may look odd too since the star is before the expression it modifies. C'est la vie. Blame it on the fact that we must work with the syntax rules of C++.

Any expression that evaluates to a parser may be used with the Kleene Star. Keep in mind, though, that due to C++ operator precedence rules you may need to put the expression in parentheses for complex expressions. The Kleene Star is also known as a Kleene Closure, but we call it the Star in most places.

Example #4 [ A Just Slightly Less Trivial Example ]

This example will create a parser that accepts a comma-delimited list of numbers and put the numbers in a vector.

Step 1. Create the parser

    real_p >> *(ch_p(',') >> real_p)

Notice ch_p(','). It is a literal character parser that can recognize the comma ','. In this case, the Kleene Star is modifying a more complex parser, namely, the one generated by the expression:

    (ch_p(',') >> real_p)

Note that this is a case where the parentheses are necessary. The Kleene star encloses the complete expression above.

Step 2. Using a Parser (now that it's created)

Now that we have created a parser, how do we use it? Like the result of any C++ temporary object, we can either store it in a variable, or call functions directly on it.

We'll gloss over some low-level C++ details and just get to the good stuff.

If r is a rule (don't worry about what rules exactly are for now. This will be discussed later. Suffice it to say that the rule is a placeholder variable that can hold a parser), then we store the parser as a rule like this:

    r = real_p >> *(ch_p(',') >> real_p);

Not too exciting, just an assignment like any other C++ expression you've used for years. The cool thing about storing a parser in a rule is this: rules are parsers, and now you can refer to it by name. (In this case the name is r). Notice that this is now a full assignment expression, thus we terminate it with a semicolon, ";".

That's it. We're done with defining the parser. So the next step is now invoking this parser to do its work. There are a couple of ways to do this. For now, we shall use the free parse function that takes in a char const*. The function accepts three arguments:

The null-terminated const char* input
The parser object
Another parser called the skip parser

In our example, we wish to skip spaces and tabs. Another parser named space_p is included in Spirit's repertoire of predefined parsers. It is a very simple parser that simply recognizes whitespace. We shall use space_p as our skip parser. The skip parser is the one responsible for skipping characters in between parser elements such as the real_p and the ch_p.

Ok, so now let's parse!

    r = real_p >> *(ch_p(',') >> real_p);
    parse(str, r, space_p) // Not a full statement yet, patience...

The parse function returns an object (called parse_info) that holds, among other things, the result of the parse. In this example, we need to know:

Did the parser successfully recognize the input str?
Did the parser fully parse and consume the input up to its end?

To get a complete picture of what we have so far, let us also wrap this parser inside a function:

    bool
    parse_numbers(char const* str)
    {
        return parse(str, real_p >> *(',' >> real_p), space_p).full;
    }

Note in this case we dropped the named rule and inlined the parser directly in the call to parse. Upon calling parse, the expression evaluates into a temporary, unnamed parser which is passed into the parse() function, used, and then destroyed.

char and wchar_t operands The careful reader may notice that the parser expression has ',' instead of ch_p(',') as the previous examples did. This is ok due to C++ syntax rules of conversion. There are >> operators that are overloaded to accept a char or wchar_t argument on its left or right (but not both). An operator may be overloaded if at least one of its parameters is a user-defined type. In this case, the real_p is the 2nd argument to operator>>, and so the proper overload of >> is used, converting ',' into a character literal parser. The problem with omiting the ch_p call should be obvious: 'a' >> 'b' is not a spirit parser, it is a numeric expression, right-shifting the ASCII (or another encoding) value of 'a' by the ASCII value of 'b'. However, both ch_p('a') >> 'b' and 'a' >> ch_p('b') are Spirit sequence parsers for the letter 'a' followed by 'b'. You'll get used to it, sooner or later.

Take note that the object returned from the parse function has a member called full which returns true if both of our requirements above are met (i.e. the parser fully parsed the input).

Step 3. Semantic Actions

Our parser above is really nothing but a recognizer. It answers the question "did the input match our grammar?", but it does not remember any data, nor does it perform any side effects. Remember: we want to put the parsed numbers into a vector. This is done in an action that is linked to a particular parser. For example, whenever we parse a real number, we wish to store the parsed number after a successful match. We now wish to extract information from the parser. Semantic actions do this. Semantic actions may be attached to any point in the grammar specification. These actions are C++ functions or functors that are called whenever a part of the parser successfully recognizes a portion of the input. Say you have a parser P, and a C++ function F, you can make the parser call F whenever it matches an input by attaching F:

    P[&F]

Or if F is a function object (a functor):

    P[F]

The function/functor signature depends on the type of the parser to which it is attached. The parser real_p passes a single argument: the parsed number. Thus, if we were to attach a function F to real_p, we need F to be declared as:

    void F(double n);

For our example however, again, we can take advantage of some predefined semantic functors and functor generators ( A functor generator is a function that returns a functor). For our purpose, Spirit has a functor generator push_back_a(c). In brief, this semantic action, when called, appends the parsed value it receives from the parser it is attached to, to the container c.

Finally, here is our complete comma-separated list parser:

    bool
    parse_numbers(char const* str, vector<double>& v)
    {
        return parse(str,

            //  Begin grammar
            (
                real_p[push_back_a(v)] >> *(',' >> real_p[push_back_a(v)])
            )
            ,
            //  End grammar

            space_p).full;
    }

This is the same parser as above. This time with appropriate semantic actions attached to strategic places to extract the parsed numbers and stuff them in the vector v. The parse_numbers function returns true when successful.

The full source code can be viewed here. This is part of the Spirit distribution.

Copyright © 1998-2003 Joel de Guzman
Copyright © 2002 Chris Uzdavinis

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)

Basic Concepts

There are a few fundamental concepts that need to be understood well: 1) The Parser, 2) Match, 3) The Scanner, and 4) Semantic Actions. These basic concepts interact with one another, and the functionalities of each interweave throughout the framework to make it one coherent whole.

The Parser

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.

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.

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.

Primitives and Composites

Spirit parsers fall into two categories: primitives and composites. 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:

    real_p >> *(',' >> real_p)

real_p is a primitive parser that can parse real numbers. The quoted comma ',' in the expression is a shortcut and is equivalent to ch_p(','), which is another primitive parser that recognizes single characters.

The expression above corresponds to the following parse tree:

The expression:

    ',' >> real_p

composes a sequence parser. The sequence parser is a composite parser comprising two parsers: the one on its left hand side (lhs), ch_p(',') ; and the other on its right hand side (rhs), real_p. This composite parser, when called, calls its lhs and rhs in sequence and reports a successful match only if both are successful.

The sequence 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 Kleene star. 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: "".

The expression:

    *(',' >> real_p)

wraps the whole sequence composite above inside a kleene_star.

Finally, the full expression composes a real_p primitive parser and the kleene_star we have above into another higher level sequence parser composite.

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.

Top-down descent traverses the hierarchy. The outer sequence calls the leftmost real_p parser. If successful, the kleene_star is called next. The kleene_star calls the inner sequence repeatedly in a loop until it fails to match, or the input is exhausted. Inside, ch_p(',') and then real_p are called in sequence. The following diagram illustrates what is happening, somewhat reminiscent of Pascal syntax diagrams.

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.

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.

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.

The Scanner

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.

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.

The Match

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 match.length()). 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.

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.

Semantic Actions

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.

Recall our example above:

    real_p >> *(',' >> real_p)

By hooking a function (or functor) into the real_p parsers, we can extract the numbers from the input:

    real_p[&f] >> *(',' >> real_p[&f])

where f is a function that takes in a single argument. The [&f] hooks the parser with the function such that when real_p recognizes a valid number, the function f 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 ',' with '+', then we have a primitive calculator that computes sums. The function f then can then be made to add all incoming numbers.

Copyright © 1998-2003 Joel de Guzman

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)

Organization

The framework is highly modular and is organized in layers:

Spirit has four layers, plus an independent top layer. The independent layer, comprising of actor and iterator, does not rely on the other layers. The framework's architecture is completely orthogonal. The relationship among the layers is acyclic. Lower layers do not depend nor know the existence of upper layers. Modules in a layer do not depend on other modules in the same layer.

The client may use only the modules that she wants without incurring any compile time nor run time penalty. A minimalistic approach is to use only the core as is. The highly streamlined core is usable by itself. The core is sufficiently suitable for tasks such as micro parsing.

The iterator module is independent of Spirit and may be used in other non-Spirit applications. This module is a compilation of stand-alone iterators and iterator wrappers compatible with Spirit. Over time, these iterators have been found to be most useful for parsing with Spirit.

The actor module, also independent of Spirit, is a compilation of predefined semantic actions that covers the most common semantics processing tasks.

The debug module provides library wide parser debugging. This module hooks itself up transparently into the core non-intrusively and only when necessary.

The attribute module introduces advanced semantic action machinery with emphasis on extraction and passing of data up and down the parser hierarchy through inherited and synthesized attributes. Attributes may also be used to actually control the parsing. Parametric parsers are a form of dynamic parsers that changes their behavior at run time based on some attribute or data.

The dynamic module focuses on parsers with behavior that can be modified at run-time.

error_handling. The framework would not be complete without Error Handling. C++'s exception handling mechanism is a perfect match for Spirit due to its highly recursive functional nature. C++ Exceptions are used extensively by this module for handling errors.

The symbols module focuses on symbol table management. This module is rather basic now. The goal is to build a sub-framework that will be able to accommodate C++ style multiple scope mechanisms. C++ is a great model for the complexity of scoping that perhaps has no parallel in any other language. There are classes and inheritance, private, protected and public access restrictions, friends, namespaces, using declarations, using directives, Koenig lookup (Argument Dependent Lookup) and more. The symbol table functionality we have now will be the basis of a complete facility that will attempt to model this.

I wish that I could ever see, a structure as lovely as a tree...

Parse Tree and Abstract Syntax Tree (AST) generation are handled by the Tree module. There are advantages with Parse Trees and Abstract Syntax Trees over semantic actions. You can make multiple passes over the data without having to re-parse the input. You can perform transformations on the tree. You can evaluate things in any order you want, whereas with attribute schemes you have to process in a begin to end fashion. You do not have to worry about backtracking and action side effects that may occur with an ambiguous grammar.

The utility module is a set of commonly useful parsers and support classes that were found to be useful in handling common tasks such as list processing, comments, confix expressions, etc.

meta, provides metaprogramming facilities for advanced Spirit developers. This module facilitates compile-time and run-time introspection of Spirit parsers.

Copyright © 1998-2003 Joel de Guzman

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)

Primitives

The framework predefines some parser primitives. These are the most basic building blocks that the client uses to build more complex parsers. These primitive parsers are template classes, making them very flexible.

These primitive parsers can be instantiated directly or through a templatized helper function. Generally, the helper function is far simpler to deal with as it involves less typing.

We have seen the character literal parser before through the generator function ch_p which is not really a parser but, rather, a parser generator. Class chlit<CharT> is the actual template class behind the character literal parser. To instantiate a chlit object, you must explicitly provide the character type, CharT, as a template parameter which determines the type of the character. This type typically corresponds to the input type, usually char or wchar_t. The following expression creates a temporary parser object which will recognize the single letter 'X'.

    chlit<char>('X');

Using chlit's generator function ch_p simplifies the usage of the chlit<> class (this is true of most Spirit parser classes since most have corresponding generator functions). It is convenient to call the function because the compiler will deduce the template type through argument deduction for us. The example above could be expressed less verbosely using the ch_p helper function.

    ch_p('X')  // equivalent to chlit<char>('X') object

Parser generators Whenever you see an invocation of the parser generator function, it is equivalent to the parser itself. Therefore, we often call ch_p a character parser, even if, technically speaking, it is a function that generates a character parser.

The following grammar snippet shows these forms in action:

    // a rule can "store" a parser object.  They're covered
    // later, but for now just consider a rule as an opaque type
    rule<> r1, r2, r3;

    chlit<char> x('X');     // declare a parser named x

    r1 = chlit<char>('X');  //  explicit declaration
    r2 = x;                 //  using x
    r3 = ch_p('X')          //  using the generator

chlit and ch_p

Matches a single character literal. chlit has a single template type parameter which defaults to char (i.e. chlit<> is equivalent to chlit<char>). This type parameter is the character type that chlit will recognize when parsing. The function generator version deduces the template type parameters from the actual function arguments. The chlit class constructor accepts a single parameter: the character it will match the input against. Examples:

    r1 = chlit<>('X');
    r2 = chlit<wchar_t>(L'X');
    r3 = ch_p('X');

Going back to our original example:

    group = '(' >> expr >> ')';
    expr1 = integer | group;
    expr2 = expr1 >> *(('*' >> expr1) | ('/' >> expr1));
    expr  = expr2 >> *(('+' >> expr2) | ('-' >> expr2));

the character literals '(', ')', '+', '-', '*' and '/' in the grammar declaration are chlit objects that are implicitly created behind the scenes.

char operands The reason this works is from two special templatized overloads of operator>> that takes a (char, ParserT), or (ParserT, char). These functions convert the character into a chlit object.

One may prefer to declare these explicitly as:

    chlit<> plus('+');
    chlit<> minus('-');
    chlit<> times('*');
    chlit<> divide('/');
    chlit<> oppar('(');
    chlit<> clpar(')');

range and range_p

A range of characters is created from a low/high character pair. Such a parser matches a single character that is in the range, including both endpoints. Like chlit, range has a single template type parameter which defaults to char. The range class constructor accepts two parameters: the character range (from and to, inclusive) it will match the input against. The function generator version is range_p. Examples:

    range<>('A','Z')    // matches 'A'..'Z'
    range_p('a','z')    // matches 'a'..'z'

Note, the first character must be "before" the second, according to the underlying character encoding characters. The range, like chlit is a single character parser.

Character mapping Character mapping to is inherently platform dependent. It is not guaranteed in the standard for example that 'A' < 'Z', however, in many occasions, we are well aware of the character set we are using such as ASCII, ISO-8859-1 or Unicode. Take care though when porting to another platform.

strlit and str_p

This parser matches a string literal. strlit has a single template type parameter: an iterator type. Internally, strlit holds a begin/end iterator pair pointing to a string or a container of characters. The strlit attempts to match the current input stream with this string. The template type parameter defaults to char const*. strlit has two constructors. The first accepts a null-terminated character pointer. This constructor may be used to build strlits from quoted string literals. The second constructor takes in a first/last iterator pair. The function generator version is str_p. Examples:

    strlit<>("Hello World")
    str_p("Hello World")

    std::string msg("Hello World");
    strlit<std::string::const_iterator>(msg.begin(), msg.end());

Character and phrase level parsing Typical parsers regard the processing of characters (symbols that form words or lexemes) and phrases (words that form sentences) as separate domains. Entities such as reserved words, operators, literal strings, numerical constants, etc., which constitute the terminals of a grammar are usually extracted first in a separate lexical analysis stage. At this point, as evident in the examples we have so far, it is important to note that, contrary to standard practice, the Spirit framework handles parsing tasks at both the character level as well as the phrase level. One may consider that a lexical analyzer is seamlessly integrated in the Spirit framework. Although the Spirit parser library does not need a separate lexical analyzer, there is no reason why we cannot have one. One can always have as many parser layers as needed. In theory, one may create a preprocessor, a lexical analyzer and a parser proper, all using the same framework.

chseq and chseq_p

Matches a character sequence. chseq has the same template type parameters and constructor parameters as strlit. The function generator version is chseq_p. Examples:

    chseq<>("ABCDEFG")
    chseq_p("ABCDEFG")

strlit is an implicit lexeme. That is, it works solely on the character level. chseq, strlit's twin, on the other hand, can work on both the character and phrase levels. What this simply means is that it can ignore white spaces in between the string characters. For example:

    chseq<>("ABCDEFG")

can parse:

    ABCDEFG
    A B C D E F G
    AB CD EFG

More character parsers

The framework also predefines the full repertoire of single character parsers:

negation ~

Single character parsers such as the chlit, range, anychar_p, alnum_p etc. can be negated. For example:

    ~ch_p('x')

matches any character except 'x'. Double negation of a character parser cancels out the negation. ~~alpha_p is equivalent to alpha_p.

eol_p

Matches the end of line (CR/LF and combinations thereof).

nothing_p

Never matches anything and always fails.

end_p

Matches the end of input (returns a sucessful match with 0 length when the input is exhausted)

Copyright © 1998-2003 Joel de Guzman
Copyright © 2003 Martin Wille

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)

Operators

Operators are used as a means for object composition and embedding. Simple parsers may be composed to form composites through operator overloading, crafted to approximate the syntax of an Extended Backus-Normal Form (EBNF) variant. An expression such as:

    a | b

actually yields a new parser type which is a composite of its operands, a and b. Taking this example further, if a and b were of type chlit<>, the result would have the composite type:

    alternative<chlit<>, chlit<> >

In general, for any binary operator, it will take its two arguments, parser1 and parser2, and create a new composed parser of the form

    op<parser1, parser2>

where parser1 and parser2 can be arbitrarily complex parsers themselves, with the only limitations being what your compiler imposes.

Set Operators

Short-circuiting

Alternative operands are tried one by one on a first come first served basis starting from the leftmost operand. After a successfully matched alternative is found, the parser concludes its search, essentially short-circuiting the search for other potentially viable candidates. This short-circuiting implicitly gives the highest priority to the leftmost alternative.

Short-circuiting is done in the same manner as C or C++'s logical expressions; e.g. if (x < 3 || y < 2) where, if x evaluates to be less than 3, the y < 2 test is not done at all. In addition to providing an implicit priority rule for alternatives which is necessary, given the non-deterministic nature of the Spirit parser compiler, short-circuiting improves the execution time. If the order of your alternatives is logically irrelevant, strive to put the (expected) most common choice first for maximum efficiency.

Intersections Some researchers assert that the intersections (e.g. a & b) let us define context sensitive languages ("XBNF" [citing Leu-Weiner, 1973]). "The theory of defining a language as the intersection of a finite number of context free languages was developed by Leu and Weiner in 1973". ~ Operator The complement operator ~ was originally put into consideration. Further understanding of its value and meaning leads us to uncertainty. The basic problem stems from the fact that ~a will yield U-a, where U is the universal set of all strings. However, where it makes sense, some parsers can be complemented (see the primitive character parsers for examples).

Sequencing Operators

The sequencing operator >> can alternatively be thought of as the sequential-and operator. The expression a && b reads as match a and b in sequence. Continuing this logic, we can also have a sequential-or operator where the expression a || b reads as match a or b and in sequence. That is, if both a and b match, it must be in sequence; this is equivalent to a >> !b | b.

Optional and Loops

If we look more closely, take note that we generalized the optional expression of the form !a in the same category as loops. This is logical, considering that the optional matches the expression following it zero (0) or one (1) time.

Primitive type operands

For binary operators, one of the operands but not both may be a char, wchar_t, char const* or wchar_t const*. Where P is a parser object, here are some examples:

    P | 'x'
    P - L"Hello World"
    'x' >> P
    "bebop" >> P

It is important to emphasize that C++ mandates that operators may only be overloaded if at least one argument is a user-defined type. Typically, in an expression involving multiple operators, explicitly typing the leftmost operand as a parser is enough to cause propagation to all the rest of the operands to its right to be regarded as parsers. Examples:

    r = 'a' | 'b' | 'c' | 'd';          // ill formed
    r = ch_p('a')  | 'b' | 'c' | 'd';   // OK

The second case is parsed as follows:

    r  (((chlit<char> | char) | char) | char)

    a  (chlit<char> | char)
    r  (((a) | char) | char)

    b  (a | char)
    r  (((b)) | char)

    c  (b | char)
    r  (((c)))

Operator precedence and grouping

Since we are defining our meta-language in C++, we follow C/C++'s operator precedence rules. Grouping expressions inside the parentheses override this (e.g., *(a | b) reads: match a or b zero (0) or more times).

Copyright © 1998-2003 Joel de Guzman

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)

Numerics

Similar to chlit, strlit etc. numeric parsers are also primitives. Numeric parsers are placed on a section of their own to give this important building block better focus. The framework includes a couple of predefined objects for parsing signed and unsigned integers and real numbers. These parsers are fully parametric. Most of the important aspects of numeric parsing can be finely adjusted to suit. This includes the radix base, the minimum and maximum number of allowable digits, the exponent, the fraction etc. Policies control the real number parsers' behavior. There are some predefined policies covering the most common real number formats but the user can supply her own when needed.

uint_parser

This class is the simplest among the members of the numerics package. The uint_parser can parse unsigned integers of arbitrary length and size. The uint_parser parser can be used to parse ordinary primitive C/C++ integers or even user defined scalars such as bigints (unlimited precision integers). Like most of the classes in Spirit, the uint_parser is a template class. Template parameters fine tune its behavior. The uint_parser is so flexible that the other numeric parsers are implemented using it as the backbone.

    template <
        typename T = unsigned,
        int Radix = 10,
        unsigned MinDigits = 1,
        int MaxDigits = -1>
    struct uint_parser { /*...*/ };

The following example shows how the uint_parser can be used to parse thousand separated numbers. The example can correctly parse numbers such as 1,234,567,890.

    uint_parser<unsigned, 10, 1, 3> uint3_p;        //  1..3 digits
    uint_parser<unsigned, 10, 3, 3> uint3_3_p;      //  exactly 3 digits
    ts_num_p = (uint3_p >> *(',' >> uint3_3_p));    //  our thousand separated number parser

bin_p, oct_p, uint_p and hex_p are parser generator objects designed to be used within expressions. Here's an example of a rule that parses comma delimited list of numbers (We've seen this before):

    list_of_numbers = real_p >> *(',' >> real_p);

Later, we shall see how we can extract the actual numbers parsed by the numeric parsers. We shall deal with this when we get to the section on specialized actions.

int_parser

The int_parser can parse signed integers of arbitrary length and size. This is almost the same as the uint_parser. The only difference is the additional task of parsing the '+' or '-' sign preceding the number. The class interface is the same as that of the uint_parser.

real_parser

The real_parser can parse real numbers of arbitrary length and size limited by its parametric type T. The real_parser is a template class with 2 template parameters. Here's the real_parser template interface:

    template<
        typename T = double,
        typename RealPoliciesT = ureal_parser_policies<T> >
    struct real_parser;

The first template parameter is its numeric base type T. This defaults to double.

Parsing special numeric types Notice that the numeric base type T can be specified by the user. This means that we can use the numeric parsers to parse user defined numeric types such as fixed_point (fixed point reals) and bigint (unlimited precision integers).

The second template parameter is a class that groups all the policies and defaults to ureal_parser_policies<T>. Policies control the real number parsers' behavior. The default policies provided are designed to parse C/C++ style real numbers of the form nnn.fff.Eeee where nnn is the whole number part, fff is the fractional part, E is 'e' or 'E' and eee is the exponent optionally preceded by '-' or '+'. This corresponds to the following grammar, with the exception that plain integers without the decimal point are also accepted by default.

    floatingliteral
        =   fractionalconstant >> !exponentpart
        |  +digit_p >> exponentpart
        ;

    fractionalconstant
        =  *digit_p >> '.' >> +digit_p
        |  +digit_p >> '.'
        ;

    exponentpart
        =   ('e' | 'E') >> !('+' | '-') >> +digit_p
        ;

The default policies are provided to take care of the most common case (there are many ways to represent, and hence parse, real numbers). In most cases, the default setting of the real_parser is sufficient and can be used straight out of the box. Actually, there are four real_parsers pre-defined for immediate use:

We've seen real_p before. ureal_p is its unsigned variant.

Strict Reals

Integer numbers are considered a subset of real numbers, so real_p and ureal_p recognize integer numbers (without a dot) as real numbers. strict_real_p and strict_ureal_p are the equivalent parsers that require a dot to be present for a number to be considered a successful match.

Advanced: real_parser policies

The parser policies break down real number parsing into 6 steps:

And the interaction of these sub-parsing tasks is further controlled by these 3 policies:

[ From here on, required reading: The Scanner, In-depth The Parser and In-depth The Scanner ]

sign_parser and sign_p

Before we move on, a small utility parser is included here to ease the parsing of the '-' or '+' sign. While it is easy to write one:

    sign_p = (ch_p('+') | '-');

it is not possible to extract the actual sign (positive or negative) without resorting to semantic actions. The sign_p parser has a bool attribute returned to the caller through the match object which, after parsing, is set to true if the parsed sign is negative. This attribute detects if the negative sign has been parsed. Examples:

    bool is_negative;
    r = sign_p[assign_a(is_negative)];

or simply...

    // directly extract the result from the match result's value
    bool is_negative = sign_p.parse(scan).value(); 

The sign_p parser expects attached semantic actions to have a signature (see Specialized Actions for further detail) compatible with:

Signature for functions:

    void func(bool is_negative);

Signature for functors:

    struct ftor
    {
        void operator()(bool is_negative) const;
    };

ureal_parser_policies

    template <typename T>
    struct ureal_parser_policies
    {
        typedef uint_parser<T, 10, 1, -1>   uint_parser_t;
        typedef int_parser<T, 10, 1, -1>    int_parser_t;

        static const bool allow_leading_dot  = true;
        static const bool allow_trailing_dot = true;
        static const bool expect_dot         = false;

        template <typename ScannerT>
        static typename match_result<ScannerT, nil_t>::type
        parse_sign(ScannerT& scan)
        { return scan.no_match(); }

        template <typename ScannerT>
        static typename parser_result<uint_parser_t, ScannerT>::type
        parse_n(ScannerT& scan)
        { return uint_parser_t().parse(scan); }

        template <typename ScannerT>
        static typename parser_result<chlit<>, ScannerT>::type
        parse_dot(ScannerT& scan)
        { return ch_p('.').parse(scan); }

        template <typename ScannerT>
        static typename parser_result<uint_parser_t, ScannerT>::type
        parse_frac_n(ScannerT& scan)
        { return uint_parser_t().parse(scan); }

        template <typename ScannerT>
        static typename parser_result<chlit<>, ScannerT>::type
        parse_exp(ScannerT& scan)
        { return as_lower_d['e'].parse(scan); }

        template <typename ScannerT>
        static typename parser_result<int_parser_t, ScannerT>::type
        parse_exp_n(ScannerT& scan)
        { return int_parser_t().parse(scan); }
    };

The default ureal_parser_policies uses the lower level integer numeric parsers to do its job.

real_parser_policies

    template <typename T>
    struct real_parser_policies : public ureal_parser_policies<T>
    {
        template <typename ScannerT>
        static typename parser_result<sign_parser, ScannerT>::type
        parse_sign(ScannerT& scan)
        { return sign_p.parse(scan); }
    };

Notice how the real_parser_policies replaced parse_sign of the ureal_parser_policies from which it is subclassed. The default real_parser_policies simply uses a sign_p instead of scan.no_match() in the parse_sign step.

strict_ureal_parser_policies and strict_real_parser_policies

    template <typename T>
    struct strict_ureal_parser_policies : public ureal_parser_policies<T>
    {
        static const bool expect_dot = true;
    };

    template <typename T>
    struct strict_real_parser_policies : public real_parser_policies<T>
    {
        static const bool expect_dot = true;
    };

Again, these policies replaced just the policies they wanted different from their superclasses.

Specialized real parser policies can reuse some of the defaults while replacing a few. For example, the following is a real number parser policy that parses thousands separated numbers with at most two decimal places and no exponent.

The full source code can be viewed here.

    template <typename T>
    struct ts_real_parser_policies : public ureal_parser_policies<T>
    {
        //  These policies can be used to parse thousand separated
        //  numbers with at most 2 decimal digits after the decimal
        //  point. e.g. 123,456,789.01

        typedef uint_parser<int, 10, 1, 2>  uint2_t;
        typedef uint_parser<T, 10, 1, -1>   uint_parser_t;
        typedef int_parser<int, 10, 1, -1>  int_parser_t;

        //////////////////////////////////  2 decimal places Max
        template <typename ScannerT>
        static typename parser_result<uint2_t, ScannerT>::type
        parse_frac_n(ScannerT& scan)
        { return uint2_t().parse(scan); }

        //////////////////////////////////  No exponent
        template <typename ScannerT>
        static typename parser_result<chlit<>, ScannerT>::type
        parse_exp(ScannerT& scan)
        { return scan.no_match(); }

        //////////////////////////////////  No exponent
        template <typename ScannerT>
        static typename parser_result<int_parser_t, ScannerT>::type
        parse_exp_n(ScannerT& scan)
        { return scan.no_match(); }

        //////////////////////////////////  Thousands separated numbers
        template <typename ScannerT>
        static typename parser_result<uint_parser_t, ScannerT>::type
        parse_n(ScannerT& scan)
        {
            typedef typename parser_result<uint_parser_t, ScannerT>::type RT;
            static uint_parser<unsigned, 10, 1, 3> uint3_p;
            static uint_parser<unsigned, 10, 3, 3> uint3_3_p;

            if (RT hit = uint3_p.parse(scan))
            {
                T n;
                typedef typename ScannerT::iterator_t iterator_t;
                iterator_t save = scan.first;
                while (match<> next = (',' >> uint3_3_p[assign_a(n)]).parse(scan))
                {
                    hit.value() *= 1000;
                    hit.value() += n;
                    scan.concat_match(hit, next);
                    save = scan.first;
                }
                scan.first = save;
                return hit;

                // Note: On erroneous input such as "123,45", the result should
                // be a partial match "123". 'save' is used to makes sure that
                // the scanner position is placed at the last *valid* parse
                // position.
            }
            return scan.no_match();
        }
    };

Copyright © 1998-2002 Joel de Guzman

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)

The Rule

The rule is a polymorphic parser that acts as a named place-holder capturing the behavior of an EBNF expression assigned to it. Naming an EBNF expression allows it to be referenced later. The rule is a template class parameterized by the type of the scanner (ScannerT), the rule's context and its tag. Default template parameters are provided to make it easy to use the rule.

    template<
        typename ScannerT = scanner<>,
        typename ContextT = parser_context<>,
        typename TagT = parser_address_tag>
    class rule;

Default template parameters are supplied to handle the most common case. ScannerT defaults to scanner<>, a plain vanilla scanner that acts on char const* iterators and does nothing special at all other than iterate through all the chars in the null terminated input a character at a time. The rule tag, TagT, typically used with ASTs, is used to identify a rule; it is explained here. In trivial cases, declaring a rule as rule<> is enough. You need not be concerned at all with the ContextT template parameter unless you wish to tweak the low level behavior of the rule. Detailed information on the ContextT template parameter is provided elsewhere.

Order of parameters

As of v1.8.0, the ScannerT, ContextT and TagT can be specified in any order. If a template parameter is missing, it will assume the defaults. Examples:

    rule<> rx1;
    rule<scanner<> > rx2;
    rule<parser_context<> > rx3;
    rule<parser_context<>, parser_address_tag> rx4;
    rule<parser_address_tag> rx5;
    rule<parser_address_tag, scanner<>, parser_context<> > rx6;
    rule<parser_context<>, scanner<>, parser_address_tag> rx7;

Multiple scanners

As of v1.8.0, rules can use one or more scanner types. There are cases, for instance, where we need a rule that can work on the phrase and character levels. Rule/scanner mismatch has been a source of confusion and is the no. 1 FAQ. To address this issue, we now have multiple scanner support. Example:

    typedef scanner_list<scanner<>, phrase_scanner_t> scanners;

    rule<scanners>  r = +anychar_p;
    assert(parse("abcdefghijk", r).full);
    assert(parse("a b c d e f g h i j k", r, space_p).full);

Notice how rule r is used in both the phrase and character levels.

By default support for multiple scanners is disabled. The macro BOOST_SPIRIT_RULE_SCANNERTYPE_LIMIT must be defined to the maximum number of scanners allowed in a scanner_list. The value must be greater than 1 to enable multiple scanners. Given the example above, to define a limit of two scanners for the list, the following line must be inserted into the source file before the inclusion of Spirit headers:

    #define BOOST_SPIRIT_RULE_SCANNERTYPE_LIMIT 2

See the techniques section for an example of a grammar using a multiple scanner enabled rule, lexeme_scanner and as_lower_scanner.

Rule Declarations

The rule class models EBNF's production rule. Example:

    rule<> a_rule = *(a | b) & +(c | d | e);

The type and behavior of the right-hand (rhs) EBNF expression, which may be arbitrarily complex, is encoded in the rule named a_rule. a_rule may now be referenced elsewhere in the grammar:

    rule<> another_rule = f >> g >> h >> a_rule;

Referencing rules When a rule is referenced anywhere in the right hand side of an EBNF expression, the rule is held by the expression by reference. It is the responsibility of the client to ensure that the referenced rule stays in scope and does not get destructed while it is being referenced.

    a = int_p;
    b = a;
    c = int_p >> b;

Copying Rules

The rule is a weird C++ citizen, unlike any other C++ object. It does not have the proper copy and assignment semantics and cannot be stored and passed around by value. If you need to copy a rule you have to explicitly call its member function copy():

    r.copy();

However, be warned that copying a rule will not deep copy other referenced rules of the source rule being copied. This might lead to dangling references. Again, it is the responsibility of the client to ensure that all referenced rules stay in scope and does not get destructed while it is being referenced. Caveat emptor.

If you copy a rule, then you'll want to place it in a storage somewhere. The problem is how? The storage can't be another rule:

    rule<> r2 = r.copy(); // BAD!

because rules are weird and does not have the expected C++ copy-constructor and assignment semantics! As a general rule: Don't put a copied rule into another rule! Instead, use the stored_rule for that purpose.

Forward declarations

A rule may be declared before being defined to allow cyclic structures typically found in BNF declarations. Example:

    rule<> a, b, c;

    a = b | a;
    b = c | a;

Recursion

The right-hand side of a rule may reference other rules, including itself. The limitation is that direct or indirect left recursion is not allowed (this is an unchecked run-time error that results in an infinite loop). This is typical of top-down parsers. Example:

    a = a | b; // infinite loop!

What is left recursion? Left recursion happens when you have a rule that calls itself before anything else. A top-down parser will go into an infinite loop when this happens. See the FAQ for details on how to eliminate left recursion.

Undefined rules

An undefined rule matches nothing and is semantically equivalent to nothing_p.

Redeclarations

Like any other C++ assignment, a second assignment to a rule is destructive and will redefine it. The old definition is lost. Rules are dynamic. A rule can change its definition anytime:

    r = a_definition;
    r = another_definition;

Rule r loses the old definition when the second assignment is made. As mentioned, an undefined rule matches nothing and is semantically equivalent to nothing_p.

Dynamic Parsers

Hosting declarative EBNF in imperative C++ yields an interesting blend. We have the best of both worlds. We have the ability to conveniently modify the grammar at run time using imperative constructs such as if, else statements. Example:

    if (feature_is_available)
        r = add_this_feature;

Rules are essentially dynamic parsers. A dynamic parser is characterized by its ability to modify its behavior at run time. Initially, an undefined rule matches nothing. At any time, the rule may be defined and redefined, thus, dynamically altering its behavior.

No start rule

Typically, parsers have what is called a start symbol, chosen to be the root of the grammar where parsing starts. The Spirit parser framework has no notion of a start symbol. Any rule can be a start symbol. This feature promotes step-wise creation of parsers. We can build parsers from the bottom up while fully testing each level or module up untill we get to the top-most level.

Parser Tags

Rules may be tagged for identification purposes. This is necessary, especially when dealing with parse trees and ASTs to see which rule created a specific AST/parse tree node. Each rule has an ID of type parser_id. This ID can be obtained through the rule's id() member function:

    my_rule.id(); //  get my_rule's id

The parser_id class is declared as:

    class parser_id
    {
    public:
                    parser_id();
        explicit    parser_id(void const* p);
                    parser_id(std::size_t l);
    
        bool        operator==(parser_id const& x) const;
        bool        operator!=(parser_id const& x) const;
        bool        operator<(parser_id const& x) const;
        std::size_t to_long() const;
    };

parser_address_tag

The rule's TagT template parameter supplies this ID. This defaults to parser_address_tag. The parser_address_tag uses the address of the rule as its ID. This is often not the most convenient, since it is not always possible to get the address of a rule to compare against.

parser_tag

It is possible to have specific constant integers to identify a rule. For this purpose, we can use the parser_tag<N>, where N is a constant integer:

    rule<parser_tag<123> > my_rule; //  set my_rule's id to 123

dynamic_parser_tag

The parser_tag<N> can only specifiy a static ID, which is defined at compile time. If you need the ID to be dynamic (changeable at runtime), you can use the dynamic_parser_tag class as the TagT template parameter. This template parameter enables the set_id() function, which may be used to set the required id at runtime:

    rule<dynamic_parser_tag> my_dynrule;
    my_dynrule.set_id(1234);    // set my_dynrule's id to 1234

If the set_id() function isn't called, the parser id defaults to the address of the rule as its ID, just like the parser_address_tag template parameter would do.

Copyright © 1998-2003 Joel de Guzman

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)

Epsilon

The Epsilon (epsilon_p and eps_p) is a multi-purpose parser that returns a zero length match.

Simple Form

In its simplest form, epsilon_p matches the null string and always returns a match of zero length:

    epsilon_p // always returns a zero-length match

This form is usually used to trigger a semantic action unconditionally. For example, it is useful in triggering error messages when a set of alternatives fail:

    r = A | B | C | eps_p[error]; // error if A, B, or C fails to match

Semantic Predicate

Semantic predicates allow you to attach a function anywhere in the grammar. In this role, the epsilon takes a 0-ary (nullary) function/functor. The run-time function/functor is typically a test that is called upon to resolve ambiguity in the grammar. A parse failure will be reported when the function/functor result evaluates to false. Otherwise an empty match will be reported. The general form is:

    eps_p(f) >> rest;

The nullary function f is called to do a semantic test (say, checking if a symbol is in the symbol table). If test returns true, rest will be evaluated. Otherwise, the production will return early with a no-match without ever touching rest.

Syntactic Predicate

Similar to Semantic predicates, Syntactic predicates assert a certain conditional syntax to be satisfied before evaluating another production. This time, epsilon_p accepts a (conditional) parser. The general form is:

    eps_p(p) >> rest;

If p is matched on the input stream then attempt to recognize rest. The parser p is called to do a syntax check. Regardless of p's success, eps_p(p) will always return a zero length match (i.e. the input is not consumed). If test returns true, rest will be evaluated. Otherwise, the production will return early with a no-match without ever touching rest.

Example:

    eps_p('0') >> oct_p // note that '0' is actually a ch_p('0') 

Epsilon here is used as a syntactic predicate. oct_p (see numerics) is parsed only if we see a leading '0'. Wrapping the leading '0' inside an epsilon makes the parser not consume anything from the input. If a '0' is seen, epsilon_p reports a successful match with zero length.

Primitive arguments Epsilon allows primitive type arguments such as char, int, wchar_t, char const*, wchar_t const* and so on. Examples: eps_p("hello") // same as eps_p(str_p("hello")) eps_p('x') // same as eps_p(ch_p('x'))

Inhibiting Semantic Actions

In a syntactic predicate eps_p(p), any semantic action directly or indirectly attached to the conditional parser p will not be called. However, semantic actions attached to epsilon itself will always be called. The following code snippets illustrates the behavior:

    eps_p(c[f])  // f not called
    eps_p(c)[f]  // f is called
    eps_p[f]     // f is called

Actually, the conditional parser p is implicitly wrapped in a no_actions_d directive:

    no_actions_d[p]

The conditional parser is required to be free from side-effects (semantic actions). The conditional parser's purpose is to resolve ambiguity by looking ahead in the input stream for a certain pattern. Ambiguity and semantic actions do not mix well. On an ambiguous grammar, backtracking happens. And when it happens, we cannot undo the effects of triggered semantic actions.

Negation

Operator ~ is defined for parsers constructed by epsilon_p/eps_p. It performs negation by complementing the results reported. ~~eps_p(x) is identical to eps_p(x).

Copyright © 1998-2003 Joel de Guzman
Copyright © 2003 Martin Wille

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)

Directives

Parser directives have the form: directive[expression]

A directive modifies the behavior of its enclosed expression, essentially decorating it. The framework pre-defines a few directives. Clients of the framework are free to define their own directives as needed. Information on how this is done will be provided later. For now, we shall deal only with predefined directives.

lexeme_d

Turns off white space skipping. At the phrase level, the parser ignores white spaces, possibly including comments. Use lexeme_d in situations where we want to work at the character level instead of the phrase level. Parsers can be made to work at the character level by enclosing the pertinent parts inside the lexeme_d directive. For example, let us complete the example presented in the Introduction. There, we skipped the definition of the integer rule. Here's how it is actually defined:

    integer = lexeme_d[ !(ch_p('+') | '-') >> +digit ];

The lexeme_d directive instructs the parser to work on the character level. Without it, the integer rule would have allowed erroneous embedded white spaces in inputs such as "1 2 345" which will be parsed as "12345".

as_lower_d

There are times when we want to inhibit case sensitivity. The as_lower_d directive converts all characters from the input to lower-case.

as_lower_d behavior It is important to note that only the input is converted to lower case. Parsers enclosed inside the as_lower_d expecting upper case characters will fail to parse. Example: as_lower_d['X'] will never succeed because it expects an upper case 'X' that the as_lower_d directive will never supply.

For example, in Pascal, keywords and identifiers are case insensitive. Pascal ignores the case of letters in identifiers and keywords. Identifiers Id, ID and id are indistinguishable in Pascal. Without the as_lower_d directive, it would be awkward to define a rule that recognizes this. Here's a possibility:

    r = str_p("id") | "Id" | "iD" | "ID";

Now, try doing that with the case insensitive Pascal keyword "BEGIN". The as_lower_d directive makes this simple:

    r = as_lower_d["begin"];

Primitive arguments The astute reader will notice that we did not explicitly wrap "begin" inside an str_p. Whenever appropriate, directives should be able to allow primitive types such as char, int, wchar_t, char const*, wchar_t const* and so on. Examples: as_lower_d["hello"] // same as as_lower_d[str_p("hello")] as_lower_d['x'] // same as as_lower_d[ch_p('x')]

no_actions_d

There are cases where you want semantic actions not to be triggered. By enclosing a parser in the no_actions_d directive, all semantic actions directly or indirectly attached to the parser will not fire.

    no_actions_d[expression]

Tweaking the Scanner Type

How does lexeme_d, as_lower_d and no_actions_d work? These directives do their magic by tweaking the scanner policies. Well, you don't need to know what that means for now. Scanner policies are discussed later. However, it is important to note that when the scanner policy is tweaked, the result is a different scanner. Why is this important to note? The rule is tied to a particular scanner (one or more scanners, to be precise). If you wrap a rule inside a lexeme_d, as_lower_d or no_actions_d,the compiler will complain about scanner mismatch unless you associate the required scanner with the rule.

lexeme_scanner, as_lower_scanner and no_actions_scanner are your friends if the need to wrap a rule inside these directives arise. Learn bout these beasts in the next chapter on The Scanner and Parsing.

longest_d

Alternatives in the Spirit parser compiler are short-circuited (see Operators). Sometimes, this is not what is desired. The longest_d directive instructs the parser not to short-circuit alternatives enclosed inside this directive, but instead makes the parser try all possible alternatives and choose the one matching the longest portion of the input stream.

Consider the parsing of integers and real numbers:

    number = real | integer;

A number can be a real or an integer. This grammar is ambiguous. An input "1234" should potentially match both real and integer. Recall though that alternatives are short-circuited . Thus, for inputs such as above, the real alternative always wins. However, if we swap the alternatives:

    number = integer | real;

we still have a problem. Now, an input "123.456" will be partially matched by integer until the decimal point. This is not what we want. The solution here is either to fix the ambiguity by factoring out the common prefixes of real and integer or, if that is not possible nor desired, use the longest_d directive:

    number = longest_d[ integer | real ];

shortest_d

Opposite of the longest_d directive.

Multiple alternatives The longest_d and shortest_d directives can accept two or more alternatives. Examples: longest[ a | b | c ]; shortest[ a | b | c | d ];

limit_d

Ensures that the result of a parser is constrained to a given min..max range (inclusive). If not, then the parser fails and returns a no-match.

Usage:

    limit_d(min, max)[expression]

This directive is particularly useful in conjunction with parsers that parse specific scalar ranges (for example, numeric parsers). Here's a practical example. Although the numeric parsers can be configured to accept only a limited number of digits (say, 0..2), there is no way to limit the result to a range (say -1.0..1.0). This design is deliberate. Doing so would have undermined Spirit's design rule that "the client should not pay for features that she does not use". We would have stored the min, max values in the numeric parser itself, used or unused. Well, we could get by by using static constants configured by a non-type template parameter, but that is not acceptable because that way, we can only accommodate integers. What about real numbers or user defined numbers such as big-ints?

Example, parse time of the form HH:MM:SS:

    uint_parser<int, 10, 2, 2> uint2_p;

    r = lexeme_d
        [
                limit_d(0u, 23u)[uint2_p] >> ':'    //  Hours 00..23
            >>  limit_d(0u, 59u)[uint2_p] >> ':'    //  Minutes 00..59
            >>  limit_d(0u, 59u)[uint2_p]           //  Seconds 00..59
        ];

min_limit_d

Sometimes, it is useful to unconstrain just the maximum limit. This will allow for an interval that's unbounded in one direction. The directive min_limit_d ensures that the result of a parser is not less than minimun. If not, then the parser fails and returns a no-match.

Usage:

    min_limit_d(min)[expression]

Example, ensure that a date is not less than 1900

    min_limit_d(1900u)[uint_p]

max_limit_d

Opposite of min_limit_d. Take note that limit_d[p] is equivalent to:

    min_limit_d(min)[max_limit_d(max)[p]]

Copyright © 1998-2003 Joel de Guzman

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)

The Scanner and Parsing

The scanner's task is to feed the sequential input data stream to the parser. The scanner extracts data from the input, parceling, potentially modifying or filtering, and then finally relegating the result to individual parser elements on demand until the input is exhausted. 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 it to be re-positioned. The following diagram illustrates what's happening:

The scanner manages various aspects of the parsing process through a set of policies. There are three sets of policies that govern:

Iteration and filtering
Recognition and matching
Handling semantic actions

These policies are mostly hidden from view and users generally need not know about them. Advanced users might however provide their own policies that override the ones that are already in place to fine tune the parsing process to fit their own needs. We shall see how this can be done. This will be covered in further detail later.

The scanner is a template class expecting two parameters: IteratorT, the iterator type and PoliciesT, its set of policies. IteratorT defaults to char const* while PoliciesT defaults to scanner_policies<>, a predefined set of scanner policies that we can use straight out of the box.

    template<
        typename IteratorT  = char const*,
        typename PoliciesT  = scanner_policies<> >
    class scanner;

Spirit uses the same iterator concepts and interface formally defined by the C++ Standard Template Library (STL). We can use iterators supplied by STL's containers (e.g. list, vector, string, etc.) as is, or perhaps write our own. Iterators can be as simple as a pointer (e.g. char const*). At the other end of the spectrum, iterators can be quite complex; for instance, an iterator adapter that wraps a lexer such as LEX.

The Free Parse Functions

The framework provides a couple of free functions to make parsing a snap. These parser functions have two forms. The first form works on the character level. The second works on the phrase level and asks for a skip parser.

The skip parser is just about any parser primitive or composite. Its purpose is to move the scanner's first iterator to valid tokens by skipping white spaces. In C for instance, the tab '\t', the newline '\n', return '\r', space ' ' and characters inside comments /*...*/ are considered as white spaces.

Character level parsing

    template <typename IteratorT, typename DerivedT>
    parse_info<IteratorT>
    parse
    (
        IteratorT const&        first,
        IteratorT const&        last,
        parser<DerivedT> const& p
    );

    template <typename CharT, typename DerivedT>
    parse_info<CharT const*>
    parse
    (
        CharT const*            str,
        parser<DerivedT> const& p
    );

There are two variants. The first variant accepts a first, last iterator pair like you do STL algorithms. The second variant accepts a null terminated string. The last argument is a parser p which will be used to parse the input.

Phrase level parsing

    template <typename IteratorT, typename ParserT, typename SkipT>
    parse_info<IteratorT>
    parse
    (
        IteratorT const&        first,
        IteratorT const&        last,
        parser<ParserT> const&  p,
        parser<SkipT> const&    skip
    );

    template <typename CharT, typename ParserT, typename SkipT>
    parse_info<CharT const*>
    parse
    (
        CharT const*            str,
        parser<ParserT> const&  p,
        parser<SkipT> const&    skip
    );

Like above, there are two variants. The first variant accepts a first, last iterator pair like you do STL algorithms. The second variant accepts a null terminated string. The argument p is the parser which will be used to parse the input. The last argument skip is the skip parser.

The parse_info structure

The functions above return a parse_info structure parameterized by the iterator type passed in. The parse_info struct has these members:

The phrase_scanner_t and wide_phrase_scanner_t

For convenience, Spirit declares these typedefs:

    typedef scanner<char const*, unspecified> phrase_scanner_t;
    typedef scanner<wchar_t const*, unspecified> wide_phrase_scanner_t;

These are the exact scanner types used by Spirit on calls to the parse function passing in a char const* (C string) or a wchar_t const* (wide string) as the first parameter and a space_p as skip-parser (the third parameter). For instance, we can use these typedefs to declare some rules. Example:

    rule<phrase_scanner_t> my_rule;
    parse("abrakadabra", my_rule, space_p);

Direct parsing with Iterators

The free parse functions make it easy for us. By using them, we need not bother with the scanner intricacies. The free parse functions hide the dirty details. However, sometime in the future, we will need to get under the hood. It's nice that we know what we are dealing with when that need comes. We will need to go low-level and call the parser's parse member function directly.

If we wish to work on the character level, the procedure is quite simple:

    scanner<IteratorT> scan(first, last);

    if (p.parse(scan))
    {
        //  Parsed successfully. If first == last, then we have
        //  a full parse, the parser recognized the input in whole.
    }
    else
    {
        //  Parsing failure. The parser failed to recognize the input
    }

The scanner position on an unsucessful match On a successful match, the input is advanced accordingly. But what happens on an unsuccessful match? Be warned. It might be intuitive to think that the scanner position is reset to its initial position prior to parsing. No, the position is not reset. On an unsuccessful match, the position of the scanner is undefined! Usually, it is positioned at the farthest point where the error was found somewhere down the recursive descent. If this behavior is not desired, you may need to position the scanner yourself. The example in the numerics chapter illustrates how the scanner position can be saved and later restored.

Where p is the parser we want to use, and first/last are the iterator pairs referring to the input. We just create a scanner given the iterators. The scanner type we will use here uses the default scanner_policies<>.

The situation is a bit more complex when we wish to work on the phrase level:

    typedef skip_parser_iteration_policy<SkipT> iter_policy_t;
    typedef scanner_policies<iter_policy_t> scanner_policies_t;
    typedef scanner<IteratorT, scanner_policies_t> scanner_t;

    iter_policy_t iter_policy(skip);
    scanner_policies_t policies(iter_policy);
    scanner_t scan(first, last, policies);

    if (p.parse(scan))
    {
        //  Parsed successfully. If first == last, then we have
        //  a full parse, the parser recognized the input in whole.
    }
    else
    {
        //  Parsing failure. The parser failed to recognize the input
    }

Where SkipT is the type of the skip-parser, skip. Again, p is the parser we want to use, and first/last are the iterator pairs referring to the input. Given a skip-parser type SkipT, skip_parser_iteration_policy creates a scanner iteration policy that skips over portions that are recognized by the skip-parser. This may then be used to create a scanner. The scanner_policies class wraps all scanner related policies including the iteration policies.

lexeme_scanner

When switching from phrase level to character level parsing, the lexeme_d (see directives.html) does its magic by disabling the skipping of white spaces. This is done by tweaking the scanner. However, when we do this, all parsers inside the lexeme gets a transformed scanner type. This should not be a problem in most cases. However, when rules are called inside the lexeme_d, the compiler will choke if the rule does not have the proper scanner type. If a rule must be used inside a lexeme_d, the rule's type must be:

    rule<lexeme_scanner<ScannerT>::type> r;

where ScannerT is the actual type of the scanner used. Take note that lexeme_scanner will only work for phrase level scanners.

as_lower_scanner

Similarly, the as_lower_d does its work by filtering and converting all characters received from the scanner to lower case. This is also done by tweaking the scanner. Then again, all parsers inside the as_lower_d gets a transformed scanner type. If a rule must be used inside a as_lower_d, the rule's type must be:

    rule<as_lower_scanner<ScannerT>::type> r;

where ScannerT is the actual type of the scanner used.

See the techniques section for an example of a grammar using a multiple scanner enabled rule, lexeme_scanner and as_lower_scanner.

no_actions_scanner

Again, no_actions_d directive tweaks the scanner to disable firing semantic actions. Like before, all parsers inside the no_actions_d gets a transformed scanner type. If a rule must be used inside a no_actions_d, the rule's type must be:

    rule<no_actions_scanner<ScannerT>::type> r;

where ScannerT is the actual type of the scanner used.

Be sure to add "typename" before lexeme_scanner, as_lower_scanner and no_actions_scanner when these are used inside a template class or function.

See no_actions.cpp. This is part of the Spirit distribution.

Copyright © 1998-2003 Joel de Guzman

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)

The Grammar

The grammar encapsulates a set of rules. The grammar class is a protocol base class. It is essentially an interface contract. The grammar is a template class that is parameterized by its derived class, DerivedT, and its context, ContextT. The template parameter ContextT defaults to parser_context, a predefined context.

You need not be concerned at all with the ContextT template parameter unless you wish to tweak the low level behavior of the grammar. Detailed information on the ContextT template parameter is provided elsewhere. The grammar relies on the template parameter DerivedT, a grammar subclass to define the actual rules.

Presented below is the public API. There may actually be more template parameters after ContextT. Everything after the ContextT parameter should not be of concern to the client and are strictly for internal use only.

    template<
        typename DerivedT,
        typename ContextT = parser_context<> >
    struct grammar;

Grammar definition

A concrete sub-class inheriting from grammar is expected to have a nested template class (or struct) named definition:

It is a nested template class with a typename ScannerT parameter.
Its constructor defines the grammar rules.
Its constructor is passed in a reference to the actual grammar self.
It has a member function named start that returns a reference to the start rule.

Grammar skeleton

    struct my_grammar : public grammar<my_grammar>
    {
        template <typename ScannerT>
        struct definition
        {
            rule<ScannerT>  r;
            definition(my_grammar const& self)  { r = /*..define here..*/; }
            rule<ScannerT> const& start() const { return r; }
        };
    };

Decoupling the scanner type from the rules that form a grammar allows the grammar to be used in different contexts possibly using different scanners. We do not care what scanner we are dealing with. The user-defined my_grammar can be used with any type of scanner. Unlike the rule, the grammar is not tied to a specific scanner type. See "Scanner Business" to see why this is important and to gain further understanding on this scanner-rule coupling problem.

Instantiating and using my_grammar

Our grammar above may be instantiated and put into action:

    my_grammar g;

    if (parse(first, last, g, space_p).full)
        cout << "parsing succeeded\n";
    else
        cout << "parsing failed\n";

my_grammar IS-A parser and can be used anywhere a parser is expected, even referenced by another rule:

    rule<>  r = g >> str_p("cool huh?");

Referencing grammars Like the rule, the grammar is also held by reference when it is placed in the right hand side of an EBNF expression. It is the responsibility of the client to ensure that the referenced grammar stays in scope and does not get destructed while it is being referenced.

Full Grammar Example

Recalling our original calculator example, here it is now rewritten using a grammar:

    struct calculator : public grammar<calculator>
    {
        template <typename ScannerT>
        struct definition
        {
            definition(calculator const& self)
            {
                group       = '(' >> expression >> ')';
                factor      = integer | group;
                term        = factor >> *(('*' >> factor) | ('/' >> factor));
                expression  = term >> *(('+' >> term) | ('-' >> term));
            }

            rule<ScannerT> expression, term, factor, group;

            rule<ScannerT> const&
            start() const { return expression; }
        };
    };

A fully working example with semantic actions can be viewed here. This is part of the Spirit distribution.

self You might notice that the definition of the grammar has a constructor that accepts a const reference to the outer grammar. In the example above, notice that calculator::definition takes in a calculator const& self. While this is unused in the example above, in many cases, this is very useful. The self argument is the definition's window to the outside world. For example, the calculator class might have a reference to some state information that the definition can update while parsing proceeds through semantic actions.

Grammar Capsules

As a grammar becomes complicated, it is a good idea to group parts into logical modules. For instance, when writing a language, it might be wise to put expressions and statements into separate grammar capsules. The grammar takes advantage of the encapsulation properties of C++ classes. The declarative nature of classes makes it a perfect fit for the definition of grammars. Since the grammar is nothing more than a class declaration, we can conveniently publish it in header files. The idea is that once written and fully tested, a grammar can be reused in many contexts. We now have the notion of grammar libraries.

Reentrancy and multithreading

An instance of a grammar may be used in different places multiple times without any problem. The implementation is tuned to allow this at the expense of some overhead. However, we can save considerable cycles and bytes if we are certain that a grammar will only have a single instance. If this is desired, simply define BOOST_SPIRIT_SINGLE_GRAMMAR_INSTANCE before including any spirit header files.

    #define BOOST_SPIRIT_SINGLE_GRAMMAR_INSTANCE

On the other hand, if a grammar is intended to be used in multithreaded code, we should then define BOOST_SPIRIT_THREADSAFE before including any spirit header files. In this case it will also be required to link against Boost.Threads

    #define BOOST_SPIRIT_THREADSAFE

Using more than one grammar start rule

Sometimes it is desirable to have more than one visible entry point to a grammar (apart from the start rule). To allow additional start points, Spirit provides a helper template grammar_def, which may be used as a base class for the definition subclass of your grammar. Here's an example:

    // this header has to be explicitly included
    #include <boost/spirit/utility/grammar_def.hpp> 

    struct calculator2 : public grammar<calculator2>
    {
        enum 
        {
            expression = 0,
            term = 1,
            factor = 2,
        };

        template <typename ScannerT>
        struct definition
        : public grammar_def<rule<ScannerT>, same, same>
        {
            definition(calculator2 const& self)
            {
                group       = '(' >> expression >> ')';
                factor      = integer | group;
                term        = factor >> *(('*' >> factor) | ('/' >> factor));
                expression  = term >> *(('+' >> term) | ('-' >> term));

                this->start_parsers(expression, term, factor); 
            }

            rule<ScannerT> expression, term, factor, group;
        };
    };

The grammar_def template has to be instantiated with the types of all the rules you wish to make visible from outside the grammar:

    grammar_def<rule<ScannerT>, same, same> 

The shorthand notation same is used to indicate that the same type be used as specified by the previous template parameter (e.g. rule<ScannerT>). Obviously, same may not be used as the first template parameter.

grammar_def start types It may not be obvious, but it is interesting to note that aside from rule<>s, any parser type may be specified (e.g. chlit<>, strlit<>, int_parser<>, etc.).

Using the grammar_def class, there is no need to provide a start()member function anymore. Instead, you'll have to insert a call to the this->start_parsers() (which is a member function of the grammar_def template) to define the start symbols for your grammar. Note that the number and the sequence of the rules used as the parameters to the start_parsers() function should match the types specified in the grammar_def template:

    this->start_parsers(expression, term, factor);

The grammar entry point may be specified using the following syntax:

    g.use_parser<N>() // Where g is your grammar and N is the Nth entry.

This sample shows how to use the term rule from the calculator2 grammar above:

    calculator2 g;

    if (parse(
            first, last, 
            g.use_parser<calculator2::term>(),
            space_p
        ).full)
    {
        cout << "parsing succeeded\n";
    }
    else {
        cout << "parsing failed\n";
    }

The template parameter for the use_parser<> template type should be the zero based index into the list of rules specified in the start_parsers() function call.

use_parser<0> Note, that using 0 (zero) as the template parameter to use_parser is equivalent to using the start rule, exported by conventional means through the start() function, as shown in the first calculator sample above. So this notation may be used even for grammars exporting one rule through its start() function only. On the other hand, calling a grammar without the use_parser notation will execute the rule specified as the first parameter to the start_parsers() function.

The maximum number of usable start rules is limited by the preprocessor constant:

    BOOST_SPIRIT_GRAMMAR_STARTRULE_TYPE_LIMIT // defaults to 3

Copyright © 1998-2003 Joel de Guzman
Copyright © 2003-2004 Hartmut Kaiser

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)

Subrules

Spirit is implemented using expression templates. This is a very powerful technique. Along with its power comes some complications. We almost take for granted that when we write i | j >> k where i, j and k are all integers the result is still an integer. Yet, with expression templates, the same expression i | j >> k where i, j and k are of type T, the result is a complex composite type [see Basic Concepts]. Spirit expressions, which are combinations of primitives and composites yield an infinite set of new types. One problem is that C++ offers no easy facility to deduce the type of an arbitrarily complex expression that yields a complex type. Thus, while it is easy to write:

    int r = i | j >> k; // where i, j, and k are ints

Expression templates yield an endless supply of types. Without the rule, there is no easy way to do this in C++ if i, j and k are Spirit parsers:

    <what_type???> r = i | j >> k; // where i, j, and k are Spirit parsers

If i, j and k are all chlit<> objects, the type that we want is:

    typedef
        alternative<
            chlit<>      //  i
          , sequence<
                chlit<>  //  j
              , chlit<>  //  k
            >
        >
    rule_t;

    rule_t r = i | j >> k; // where i, j, and k are chlit<> objects

We deliberately formatted the type declaration nicely to make it understandable. Try that with a more complex expression. While it can be done, explicitly spelling out the type of a Spirit expression template is tedious and error prone. The right hand side (rhs) has to mirror the type of the left hand side (lhs). ( Yet, if you still wish to do it, see this link for a technique).

Fortunately, rules come to the rescue. Rules can capture the type of the expression assigned to it. Thus:

    rule<> r = i | j >> k;  // where i, j, and k are chlit<> objects

It might not be apparent but behind the scenes, plain rules are actually implemented using a pointer to a runtime polymorphic abstract class that holds the dynamic type of the parser assigned to it. When a Spirit expression is assigned to a rule, its type is encapsulated in a concrete subclass of the abstract class. A virtual parse function delegates the parsing to the encapsulated object.

Rules have drawbacks though:

It is coupled to a specific scanner type. The rule is tied to a specific scanner [see The Scanner Business].
The rule's parse member function has a virtual function call overhead that cannot be inlined.

Static rules: subrules

The subrule is a fully static version of the rule. The subrule does not have the drawbacks listed above.

The subrule is not tied to a specific scanner so just about any scanner type may be used
The subrule also allows aggressive inlining since there are no virtual function calls

    template<int ID, typename ContextT = parser_context<> >
    class subrule;

The first template parameter gives the subrule an identification tag. Like the rule, there is a ContextT template parameter that defaults to parser_context. You need not be concerned at all with the ContextT template parameter unless you wish to tweak the low level behavior of the subrule. Detailed information on the ContextT template parameter is provided elsewhere.

Presented above is the public API. There may actually be more template parameters after ContextT. Everything after the ContextT parameter should not be of concern to the client and are strictly for internal use only.

Apart from a few minor differences, the subrule follows the usage and syntax of the rule closely. Here's the calculator grammar using subrules:

    struct calculator : public grammar<calculator>
    {
        template <typename ScannerT>
        struct definition
        {
            definition(calculator const& self)
            {
                first =
                (
                    expression  = term >> *(('+' >> term) | ('-' >> term)),
                    term        = factor >> *(('*' >> factor) | ('/' >> factor)),
                    factor      = integer | group,
                    group       = '(' >> expression >> ')'
                );
            }

            subrule<0>  expression;
            subrule<1>  term;
            subrule<2>  factor;
            subrule<3>  group;

            rule<ScannerT> first;
            rule<ScannerT> const&
            start() const { return first; }
        };
    };

A fully working example with semantic actions can be viewed here. This is part of the Spirit distribution.

The subrule as an efficient version of the rule. Compiler optimizations such as aggressive inlining help reduce the code size and increase performance significantly.

The subrule is not a panacea however. Subrules push the C++ compiler hard to its knees. For example, current compilers have a limit on recursion depth that may not be exceeded. Don't even think about writing a full pascal grammar using subrules alone. A grammar using subrules is a single C++ expression. Current C++ compilers cannot handle very complex expressions very well. Finally, a plain rule is still needed to act as place holder for subrules.

The code above is a good example of the recommended way to use subrules. Notice the hierarchy. We have a grammar that encapsulates the whole calculator. The start rule is a plain rule that holds the set of subrules. The subrules in turn defines the actual details of the grammar.

Template instantiation depth Spirit pushes the C++ compiler hard. Current C++ compilers cannot handle very complex heavily nested expressions very well. One restricting factor is the typical compiler's limit on template recursion depth. Some, but not all, compilers allow this limit to be configured. g++'s maximum can be set using a compiler flag: -ftemplate-depth. Set this appropriately if you have a relatively complex grammar. Microsoft Visual C++ can take greater than 1000 for both template class and function instantiation depths. However, the linker chokes with deep template function instantiation unless inline recursion depth is set using these pragmas: #pragma inline_depth(255) #pragma inline_recursion(on) Perhaps this limitations no longer applies to more current versions of these compilers. Be sure to check your compiler documentation.

This setup gives a good balance. The subrules do all the work. Each grammar will have only one rule: first. The rule is used just to hold the subrules and make them visible to the grammar.

The subrule definition

Like the rule, the expression after assignment operator = defines the subrule:

    identifier = expression

Unlike rules, subrules may be defined only once. Redefining a subrule is illegal and will result to a compile time assertion.

Separators [ , ]

While rules are terminated by the semicollon ';'. Subrules are not terminated but are separated by the comma: ','. Like Pascal statements, the last subrule in a group may not have a trailing comma.

    a = ch_p('a'),
    b = ch_p('b'),
    c = ch_p('c'), // BAD, trailing comma

    a = ch_p('a'),
    b = ch_p('b'),
    c = ch_p('c')  // OK

The start subrule

Unlike rules, parsing proceeds from the start subrule. The first (topmost) subrule in a group of subrules is called the start subrule. In our example above, expression is the start subrule. When a group of subrules is called forth, the start subrule expression is called first.

IDs

Each subrule has a corresponding ID; an integral constant that uniquely specifies the subrule. Our example above has four subrules. They are declared as:

    subrule<0>  expression;
    subrule<1>  term;
    subrule<2>  factor;
    subrule<3>  group;

Aliases

It is possible to have subrules with similar IDs. A subrule with a similar ID to will be an alias of the other. Both subrules may be used interchangeably.

    subrule<0>  a;
    subrule<0>  alias;  // alias of a

Groups: scope and nesting

The scope of a subrule and its definition is the enclosing group, typically (and by convention) enclosed inside the parentheses. IDs outside a scope are not directly visible. Inner subrule groups can be nested by enclosing each sub-group inside another set of parentheses. Each group is unique and acts independently. Consequently, while it may not be advisable to do so, a subrule in a group may share the same ID as a subrule in another group since both groups are independent of each other.

    subrule<0> a;
    subrule<1> b;
    subrule<0> c;
    subrule<1> d;

    (                       // outer subrule group, scope of a and b
        a = ch_p('a'),
        b =
        (                   // inner subrule group, scope of b and c
            c = ch_p('c'),
            d = ch_p('d')
        )
    )

Subrule IDs need to be unique only within a group. A grammar is an implicit group. Furthermore, even subrules in a grammar may have the same IDs without clashing if they are inside a group. Subrules may be explicitly grouped using the parentheses. Parenthesized groups have unique scopes. In the code above, the outer subrule group defines the subrules a and b while the inner subrule group defines the subrules c and d. Notice that the definition of b is the inner subrule.

Copyright © 1998-2003 Joel de Guzman

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)

Semantic Actions

Semantic actions have the form: expression[action]

Ultimately, after having defined our grammar and having generated a corresponding parser, we will need to produce some output and do some work besides syntax analysis; unless, of course, what we want is merely to check for the conformance of an input with our grammar, which is very seldom the case. Semantic actions may be attached to any expression at any level within the parser hierarchy. An action is a C/C++ function or function object that will be called if a match is found in the particular context where it is attached. The action function serves as a hook into the parser and may be used to, for example:

Generate output from the parser (ASTs, for example)
Report warnings or errors
Manage symbol tables

Generic Semantic Actions (Transduction Interface)

A generic semantic action can be any free function or function object that is compatible with the interface:

    void f(IteratorT first, IteratorT last);

where IteratorT is the type of iterator used, first points to the current input and last points to one after the end of the input (identical to STL iterator ranges). A function object (functor) should have a member operator() with the same signature as above:

    struct my_functor
    {
        void operator()(IteratorT first, IteratorT last) const;
    };

Iterators pointing to the matching portion of the input are passed into the function/functor.

In general, semantic actions accept the first-last iterator pair. This is the transduction interface. The action functions or functors receive the unprocessed data representing the matching production directly from the input. In many cases, this is sufficient. Examples are source to source translation, pre-processing, etc.

Example:

    void
    my_action(char const* first, char const* last)
    {
        std::string str(first, last);
        std::cout << str << std::endl;
    }

    rule<> myrule = (a | b | *(c >> d))[&my_action];

The function my_action will be called whenever the expression (a | b | *(c >> d) matches a portion of the input stream while parsing. Two iterators, first and last, are passed into the function. These iterators point to the start and end, respectively, of the portion of input stream where the match is found.

Const-ness:

With functors, take note that the operator() should be const. This implies that functors are immutable. One may wish to have some member variables that are modified when the action gets called. This is not a good idea. First of all, functors are preferably lightweight. Functors are passed around a lot and it would incur a lot of overhead if the functors are heavily laden. Second, functors are passed by value. Thus, the actual functor object that finally attaches to the parser, will surely not be the original instance supplied by the client. What this means is that changes to a functor's state will not affect the original functor that the client passed in since they are distinct copies. If a functor needs to update some state variables, which is often the case, it is better to use references to external data. The following example shows how this can be done:

    struct my_functor
    {
        my_functor(std::string& str_)
        : str(str_) {}

        void
        operator()(IteratorT first, IteratorT last) const
        {
            str.assign_a(first, last);
        }

        std::string& str;
    };

Full Example:

Here now is our calculator enhanced with semantic actions:

    namespace
    {
        void    do_int(char const* str, char const* end)
        {
            string  s(str, end);
            cout << "PUSH(" << s << ')' << endl;
        }

        void    do_add(char const*, char const*)    { cout << "ADD\n"; }
        void    do_subt(char const*, char const*)   { cout << "SUBTRACT\n"; }
        void    do_mult(char const*, char const*)   { cout << "MULTIPLY\n"; }
        void    do_div(char const*, char const*)    { cout << "DIVIDE\n"; }
        void    do_neg(char const*, char const*)    { cout << "NEGATE\n"; }
    }

We augment our grammar with semantic actions:

    struct calculator : public grammar<calculator>
    {
        template <typename ScannerT>
        struct definition
        {
            definition(calculator const& self)
            {
                expression
                    =   term
                        >> *(   ('+' >> term)[&do_add]
                            |   ('-' >> term)[&do_subt]
                            )
                    ;

                term =
                    factor
                        >> *(   ('*' >> factor)[&do_mult]
                            |   ('/' >> factor)[&do_div]
                            )
                        ;

                factor
                    =   lexeme_d[(+digit_p)[&do_int]]
                    |   '(' >> expression >> ')'
                    |   ('-' >> factor)[&do_neg]
                    |   ('+' >> factor)
                    ;
            }

            rule<ScannerT> expression, term, factor;

            rule<ScannerT> const&
            start() const { return expression; }
        };
    };

Feeding in the expression (-1 + 2) * (3 + -4), for example, to the rule expression will produce the expected output:

-1
2
ADD
3
-4
ADD
MULT

which, by the way, is the Reverse Polish Notation (RPN) of the given expression, reminiscent of some primitive calculators and the language Forth.

View the complete source code here. This is part of the Spirit distribution.

Specialized Actions

In general, semantic actions accept the first-last iterator pair. There are situations though where we might want to pass data in its processed form. A concrete example is the numeric parser. It is unwise to pass unprocessed data to a semantic action attached to a numeric parser and just throw away what has been parsed by the parser. We want to pass the actual parsed number.

The function and functor signature of a semantic action varies depending on the parser where it is attached to. The following table lists the parsers that accept unique signatures.

Unless explicitly stated in the documentation of a specific parser type, parsers not included in the list by default expect the generic signature as explained above.

Numeric Actions

Applies to:

uint_p
int_p
ureal_p
real_p

Signature for functions:

    void func(NumT val);

Signature for functors:

    struct ftor
    {
        void operator()(NumT val) const;
    };

Where NumT is any primitive numeric type such as int, long, float, double, etc., or a user defined numeric type such as big_int. NumT is the same type used as template parameter to uint_p, int_p, ureal_p or real_p. The parsed number is passed into the function/functor.

Character Actions

Applies to:

chlit, ch_p
range, range_p
anychar
alnum, alpha
cntrl, digit
graph, lower
print, punct
space, upper
xdigit

Signature for functions:

    void func(CharT ch);

Signature for functors:

    struct ftor
    {
        void operator()(CharT ch) const;
    };

Where CharT is the value_type of the iterator used in parsing. A char const* iterator for example has a value_type of char. The matching character is passed into the function/functor.

Cascading Actions

Actions can be cascaded. Cascaded actions also inherit the function/functor interface of the original. For example:

    uint_p[fa][fb][fc]

Here, the functors fa, fb and fc all expect the signature void operator()(unsigned n) const.

Directives and Actions

Directives inherit the the function/functor interface of the subject it is enclosing. Example:

    as_lower_d[ch_p('x')][f]

Here, the functor f expects the signature void operator()(char ch) const, assuming that the iterator used is a char const*.

Copyright © 1998-2003 Joel de Guzman

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)

In-depth: The Parser

What makes Spirit tick? Now on to some details... The parser class is the most fundamental entity in the framework. A parser accepts a scanner comprised of a first-last iterator pair and returns a match object as its result. The iterators delimit the data currently being parsed. The match object evaluates to true if the parse succeeds, in which case the input is advanced accordingly. Each parser can represent a specific pattern or algorithm, or it can be a more complex parser formed as a composition of other parsers.

All parsers inherit from the base template class, parser:

template <typename DerivedT>
struct parser
{
    /*...*/

    DerivedT& derived();
    DerivedT const& derived() const;
};

This class is a protocol base class for all parsers. The parser class does not really know how to parse anything but instead relies on the template parameter DerivedT to do the actual parsing. This technique is known as the "Curiously Recurring Template Pattern" in template meta-programming circles. This inheritance strategy gives us the power of polymorphism without the virtual function overhead. In essence this is a way to implement compile time polymorphism.

parser_category_t

Each derived parser has a typedef parser_category_t that defines its category. By default, if one is not specified, it will inherit from the base parser class which typedefs its parser_category_t as plain_parser_category. Some template classes are provided to distinguish different types of parsers. The following categories are the most generic. More specific types may inherit from these.

    struct plain_parser_category {};
    struct binary_parser_category       : plain_parser_category {};
    struct unary_parser_category        : plain_parser_category {};
    struct action_parser_category       : unary_parser_category {};

embed_t

Each parser has a typedef embed_t. This typedef specifies how a parser is embedded in a composite. By default, if one is not specified, the parser will be embedded by value. That is, a copy of the parser is placed as a member variable of the composite. Most parsers are embedded by value. In certain situations however, this is not desirable or possible. One particular example is the rule. The rule, unlike other parsers is embedded by reference.

The match

The match holds the result of a parser. A match object evaluates to true when a succesful match is found, otherwise false. The length of the match is the number of characters (or tokens) that is successfully matched. This can be queried through its length() member function. A negative value means that the match is unsucessful.

Each parser may have an associated attribute. This attribute is also returned back to the client on a successful parse through the match object. We can get this attribute via the match's value() member function. Be warned though that the match's attribute may be invalid, in which case, getting the attribute will result in an exception. The member function has_valid_attribute() can be queried to know if it is safe to get the match's attribute. The attribute may be set anytime through the member function value(v)where v is the new attribute value.

A match attribute is valid:

• on a successful match
• when its value is set through the value(val) member function
• if it is assigned or copied from a compatible match object (e.g. match<double> from match<int>) with a valid attribute. A match object A is compatible with another match object B if the attribute type of A can be assigned from the attribute type of B (i.e. a = b; must compile).

The match attribute is undefined:

• on an unsuccessful match
• when an attempt to copy or assign from another match object with an incompatible attribute type (e.g. match<std::string> from match<int>).

The match class:

    template <typename T>
    class match
    {
    public:

        /*...*/

        typedef T attr_t;

                    operator safe_bool() const; // convertible to a bool
        int         length() const;
        bool        has_valid_attribute() const;
        void        value(T const&) const;
        T const&    value();
    };

match_result

It has been mentioned repeatedly that the parser returns a match object as its result. This is a simplification. Actually, for the sake of genericity, parsers are really not hard-coded to return a match object. More accurately, a parser returns an object that adheres to a conceptual interface, of which the match is an example. Nevertheless, we shall call the result type of a parser a match object regardless if it is actually a match class, a derivative or a totally unrelated type.

Meta-functions What are meta-functions? We all know how functions look like. In simplest terms, a function accepts some arguments and returns a result. Here is the function we all love so much: int identity_func(int arg) { return arg; } // return the argument arg Meta-functions are essentially the same. These beasts also accept arguments and return a result. However, while functions work at runtime on values, meta-functions work at compile time on types (or constants, but we shall deal only with types). The meta-function is a template class (or struct). The template parameters are the arguments to the meta-function and a typedef within the class is the meta-function's return type. Here is the corresponding meta-function: template <typename ArgT> struct identity_meta_func { typedef ArgT type; } // return the argument ArgT The meta-function above is invoked as: typename identity_meta_func<ArgT>::type By convention, meta-functions return the result through the typedef type. Take note that typename is only required within templates.

The actual match type used by the parser depends on two types: the parser's attribute type and the scanner type. match_result is the meta-function that returns the desired match type given an attribute type and a scanner type.

Usage:

    typename match_result<ScannerT, T>::type

The meta-function basically answers the question "given a scanner type ScannerT and an attribute type T, what is the desired match type?" [ typename is only required within templates ].

The parse member function

Concrete sub-classes inheriting from parser must have a corresponding member function parse(...) compatible with the conceptual Interface:

    template <typename ScannerT>
    RT
    parse(ScannerT const& scan) const;

where RT is the desired return type of the parser.

The parser result

Concrete sub-classes inheriting from parser in most cases need to have a nested meta-function result that returns the result type of the parser's parse member function, given a scanner type. The meta-function has the form:

    template <typename ScannerT>
    struct result
    {
        typedef RT type;
    };

where RT is the desired return type of the parser. This is usually, but not always, dependent on the template parameter ScannerT. For example, given an attribute type int, we can use the match_result metafunction:

    template <typename ScannerT>
    struct result
    {
        typedef typename match_result<ScannerT, int>::type type;
    };

If a parser does not supply a result metafunction, a default is provided by the base parser class. The default is declared as:

    template <typename ScannerT>
    struct result
    {
        typedef typename match_result<ScannerT, nil_t>::type type;
    };

Without a result metafunction, notice that the parser's default attribute is nil_t (i.e. the parser has no attribute).

parser_result

Given a a scanner type ScannerT and a parser type ParserT, what will be the actual result of the parser? The answer to this question is provided to by the parser_result meta-function.

Usage:

    typename parser_result<ParserT, ScannerT>::type

In general, the meta-function just forwards the invocation to the parser's result meta-function:

    template <typename ParserT, typename ScannerT>
    struct parser_result
    {
        typedef typename ParserT::template result<ScannerT>::type type;
    };

This is similar to a global function calling a member function. Most of the time, the usage above is equivalent to:

    typename ParserT::template result<ScannerT>::type

Yet, this should not be relied upon to be true all the time because the parser_result metafunction might be specialized for specific parser and/or scanner types.

The parser_result metafunction makes the signature of the required parse member function almost canonical:

    template <typename ScannerT>
    typename parser_result<self_t, ScannerT>::type
    parse(ScannerT const& scan) const;

where self_t is a typedef to the parser.

parser class declaration

    template <typename DerivedT>
    struct parser
    {
        typedef DerivedT                embed_t;
        typedef DerivedT                derived_t;
        typedef plain_parser_category   parser_category_t;

        template <typename ScannerT>
        struct result
        {
            typedef typename match_result<ScannerT, nil_t>::type type;
        };

        DerivedT& derived();
        DerivedT const& derived() const;

        template <typename ActionT>
        action<DerivedT, ActionT>
        operator[](ActionT const& actor) const;
    };

Copyright © 1998-2003 Joel de Guzman

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)

In-depth: The Scanner

Basic Scanner API

The basic behavior of the scanner is handled by policies. The actual execution of the scanner's public member functions listed in the table above is implemented by the scanner policies.

Three sets of policies govern the behavior of the scanner. These policies make it possible to extend Spirit non-intrusively. The scanner policies allow the core-functionality to be extended without requiring any potentially destabilizing changes to the code. A library writer might provide her own policies that override the ones that are already in place to fine tune the parsing process to fit her own needs. Layers above the core might also want to take advantage of this policy based machanism. Abstract syntax tree generation, debuggers and lexers come to mind.

There are three sets of policies that govern:

• Iteration and filtering
• Recognition and matching
• Handling semantic actions

iteration_policy

Here are the default policies that govern iteration and filtering:

    struct iteration_policy
    {
        template <typename ScannerT>
        void
        advance(ScannerT const& scan) const
        { ++scan.first; }

        template <typename ScannerT>
        bool at_end(ScannerT const& scan) const
        { return scan.first == scan.last; }

        template <typename T>
        T filter(T ch) const
        { return ch; }

        template <typename ScannerT>
        typename ScannerT::ref_t
        get(ScannerT const& scan) const
        { return *scan.first; }
    };

The following code snippet demonstrates a simple policy that converts all characters to lower case:

    struct inhibit_case_iteration_policy : public iteration_policy
    {
        template <typename CharT>
        CharT filter(CharT ch) const
        { 
            return std::tolower(ch); 
        }
    };

match_policy

Here are the default policies that govern recognition and matching:

    struct match_policy
    {
        template <typename T>
        struct result 
        { 
            typedef match<T> type; 
        };

        const match<nil_t>
        no_match() const
        { 
            return match<nil_t>(); 
        }

        const match<nil_t>
        empty_match() const
        { 
            return match<nil_t>(0, nil_t()); 
        }

        template <typename AttrT, typename IteratorT>
        match<AttrT>
        create_match(
            std::size_t         length,
            AttrT const&        val,
            IteratorT const&    /*first*/,
            IteratorT const&    /*last*/) const
        { 
            return match<AttrT>(length, val); 
        }

        template <typename MatchT, typename IteratorT>
        void
        group_match(
            MatchT&             /*m*/,
            parser_id const&    /*id*/,
            IteratorT const&    /*first*/,
            IteratorT const&    /*last*/) const {}

        template <typename Match1T, typename Match2T>
        void
        concat_match(Match1T& l, Match2T const& r) const
        { 
            l.concat(r); 
        }
    };

action_policy

The action policy has only one function for handling semantic actions:

    struct action_policy
    {
        template <typename ActorT, typename AttrT, typename IteratorT>
        void
        do_action(
            ActorT const&       actor,
            AttrT const&        val,
            IteratorT const&    first,
            IteratorT const&    last) const;
    };

The default action policy forwards to:

    actor(first, last);

If the attribute val is of type nil_t. Otherwise:

    actor(val);

scanner_policies mixer

The class scanner_policies combines the three scanner policy classes above into one:

    template <
        typename IterationPolicyT   = iteration_policy,
        typename MatchPolicyT       = match_policy,
        typename ActionPolicyT      = action_policy>
    struct scanner_policies;

This mixer class inherits from all the three policies. This scanner_policies class is then used to parameterize the scanner:

    template <
        typename IteratorT = char const*,
        typename PoliciesT = scanner_policies<> >
    class scanner;

The scanner in turn inherits from the PoliciesT.

Rebinding Policies

The scanner can be made to rebind to a different set of policies anytime. It has a member function change_policies(new_policies). Given a new set of policies, this member function creates a new scanner with the new set of policies. The result type of the rebound scanner can be can be obtained by calling the metafunction:

    rebind_scanner_policies<ScannerT, PoliciesT>::type

Rebinding Iterators

The scanner can also be made to rebind to a different iterator type anytime. It has a member function change_iterator(first, last). Given a new pair of iterator of type different from the ones held by the scanner, this member function creates a new scanner with the new pair of iterators. The result type of the rebound scanner can be can be obtained by calling the metafunction:

    rebind_scanner_iterator<ScannerT, IteratorT>::type

Copyright © 1998-2003 Joel de Guzman

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)

In-depth: The Parser Context

Overview

The parser's context is yet another concept. An instance (object) of the context class is created before a non-terminal starts parsing and is destructed after parsing has concluded. A non-terminal is either a rule, a subrule, or a grammar. Non-terminals have a ContextT template parameter. The following pseudo code depicts what's happening when a non-terminal is invoked:

    return_type
    a_non_terminal::parse(ScannerT const& scan)
    {
        context_t ctx(/**/);
        ctx.pre_parse(/**/);

        //  main parse code of the non-terminal here...

        return ctx.post_parse(/**/);
    }

The context is provided for extensibility. Its main purpose is to expose the start and end of the non-terminal's parse member function to accommodate external hooks. We can extend the non-terminal in a multitude of ways by writing specialized context classes, without modifying the class itself. For example, we can make the non-terminal emit debug diagnostics information by writing a context class that prints out the current state of the scanner at each point in the parse traversal where the non-terminal is invoked.

Example of a parser context that prints out debug information:

    pre_parse:      non-terminal XXX is entered. The current state of the input
                    is "hello world, this is a test"

    post_parse:     non-terminal XXX has concluded, the non-terminal matched "hello world".
                    The current state of the input is ", this is a test"

Most of the time, the context will be invisible from the user's view. In general, clients of the framework need not deal directly nor even know about contexts. Power users, however, might find some use of contexts. Thus, this is part of the public API. Other parts of the framework in other layers above the core take advantage of the context to extend non-terminals.

Class declaration

The parser_context class is the default context class that the non-terminal uses.

    template <typename AttrT = nil_t>
    struct parser_context
    {
        typedef AttrT attr_t;
        typedef implementation_defined base_t;
        typedef parser_context_linker<parser_context<AttrT> > context_linker_t;

        template <typename ParserT>
        parser_context(ParserT const& p) {}

        template <typename ParserT, typename ScannerT>
        void
        pre_parse(ParserT const& p, ScannerT const& scan) {}

        template <typename ResultT, typename ParserT, typename ScannerT>
        ResultT&
        post_parse(ResultT& hit, ParserT const& p, ScannerT const& scan)
        { return hit; }
    };

The non-terminal's ContextT template parameter is a concept. The parser_context class above is the simplest model of this concept. The default parser_context's pre_parse and post_parse member functions are simply no-ops. You can think of the non-terminal's ContextT template parameter as the policy that governs how the non-terminal will behave before and after parsing. The client can supply her own context policy by passing a user defined context template parameter to a particular non-terminal.

The base_t deserves further explanation. Here goes... The context is strictly a stack based class. It is created before parsing and destructed after the non-terminal's parse member function exits. Sometimes, we need auxiliary data that exists throughout the full lifetime of the non-terminal host. Since the non-terminal inherits from the context's base_t, the context itself, when created, gets access to this upon construction when the non-terminal is passed as an argument to the constructor. Ditto on pre_parse and post_parse.

The non-terminal inherits from the context's base_t typedef. The sole requirement is that it is a class that is default constructible. The copy-construction and assignment requirements depends on the host. If the host requires it, so does the context's base_t. In general, it wouldn't hurt to provide these basic requirements.

Non-default Attribute Type

Right out of the box, the parser_context class may be paramaterized with a type other than the default nil_t. The following code demonstrates the usage of the parser_context template with an explicit argument to declare rules with match results different from nil_t:

    rule<parser_context<int> > int_rule = int_p;

    parse(
        "123",
        // Using a returned value in the semantic action
        int_rule[cout << arg1 << endl] 
    ); 

In this example, int_rule is declared with int attribute type. Hence, the int_rule variable can hold any parser which returns an int value (for example int_p or bin_p). The important thing to note is that we can use the returned value in the semantic action bound to the int_rule.

See parser_context.cpp in the examples. This is part of the Spirit distribution.

An Example

As an example let's have a look at the Spirit parser context, which inserts some debug output to the parsing process:

    template<typename ContextT>
    struct parser_context_linker : public ContextT
    {
        typedef ContextT base_t;

        template <typename ParserT>
        parser_context_linker(ParserT const& p)
        : ContextT(p) {}
        
    // This is called just before parsing of this non-terminal
        template <typename ParserT, typename ScannerT>
        void pre_parse(ParserT const& p, ScannerT &scan)
        {
        // call the pre_parse function of the base class
            this->base_t::pre_parse(p, scan);

#if BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES
            if (trace_parser(p.derived())) {
            // print out pre parse info
                impl::print_node_info(
                false, scan.get_level(), false,
                parser_name(p.derived()),
                scan.first, scan.last);
            }
            scan.get_level()++;  // increase nesting level
#endif 
        }
    // This is called just after parsing of the current non-terminal
        template <typename ResultT, typename ParserT, typename ScannerT>
        ResultT& post_parse(
            ResultT& hit, ParserT const& p, ScannerT& scan)
        {

#if BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES
            --scan.get_level();  // decrease nesting level
            if (trace_parser(p.derived())) {
                impl::print_node_info(
                    hit, scan.get_level(), true,
                    parser_name(p.derived()),
                    scan.first, scan.last);
            }
#endif
        // call the post_parse function of the base class
            return this->base_t::post_parse(hit, p, scan);
        }
    };