https://github.com/djowel/spirit_x3
https://github.com/djowel/spirit_x3.git
git@github.com:djowel/spirit_x3.git

The full attribute mechanism works + basic C++lambda support. I’ve ported one example (calc4.cpp) which parses to an AST. The AST remains the same. Only the way the grammars are written had to change.

For a teaser: here’s GCC times:

SpiritX3: TOTAL :   4.27 secs
Spirit2:  TOTAL :  10.00 secs

Even faster at CT than the first Spirit3 attempt. Runtime speed? I expect it to be faster than Spirit-2. The rules have changed (pun intentional). Now, there’s no longer the need for virtual functions and auto is used extensively. I expect code size to be smaller too because the compiler can generate more efficient code.

Here’s the calculator grammar (based on calc3.cpp):

///////////////////////////////////////////////////////////////////////////////
//  The calculator grammar
///////////////////////////////////////////////////////////////////////////////
namespace calculator_grammar
{
    using x3::uint_;
    using x3::char_;

    x3::rule<class expression, ast::program> const expression;
    x3::rule<class term, ast::program> const term;
    x3::rule<class factor, ast::operand> const factor;

    auto const expression_def =
        term
        >> *(   (char_('+') >> term)
            |   (char_('-') >> term)
            )
        ;

    auto const term_def =
        factor
        >> *(   (char_('*') >> factor)
            |   (char_('/') >> factor)
            )
        ;

    auto const factor_def =
            uint_
        |   '(' >> expression >> ')'
        |   (char_('-') >> factor)
        |   (char_('+') >> factor)
        ;

    auto const calculator = x3::grammar(
            expression = expression_def,
            term = term_def,
            factor = factor_def
        );
}

using calculator_grammar::calculator;

Here’s the abstract:

Inside Spirit X3.Redesigning Boost.Spirit for C++11
Joel de Guzman, 2013

The hugely successful BoostCon ’07 ’08, ’09 and ’10 Spirit talks provided walk-through presentations and tutorials on how to use Spirit. This, time, I propose a presentation that will focus on the design and implementation of Spirit. But to add more to the thrill, I will present a major redesign of Spirit from the ground up, taking advantage of the new C++11 features. One important goal of this experimental version of Spirit (named X3) is to bring back the elegant simplicity of “Classic” Spirit, which was somehow lost with the complexity of Spirit-2 primarily due to the lack of important language features that are just starting to appear in C++ compilers. In this 90-minute presentation, I would like to get down and dirty with Modern C++11 code, and along the way, share my experience as well as expose some of C++11′s shortcomings and my wishes for C++1y.

Hope to see you there!

See you there!

It’s hard to pinpoint exactly the birthday of Spirit. Looking back, Spirit 1.0 which was uploaded to SourceForge in July 27, 2001 contains this comment in its main header file:

8/28/1999    Original Implementation [ run time polymorphic version ] (JDG)
4/30/2001    Template meta-programming implementation (JDG)
5/13/2001    Major redesign using iterators (JDG)
5/26/2001    Port to G++3.0 and BCC 5.5.1 thanks to Vladimir Prus
5/27/2001    Bug fixes in Difference and Xor classes (JDG)
5/30/2001    Added Iterators (JDG)

And then, there’s the original post to Boost developer’s list dated May 21, 2001:

Hello there,

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++. 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.

The documentation and source code can be found at http://isis-tech.n3.net. I would appreciate feedback and comments.

Joel de Guzman

Let me declare that the July 27, 2001 SF upload should mark Spirit’s birthday. That’ll be 3 days from now.

Happy 10 years, Spirit!

He writes:

This code illustrates several advanced techniques for parsing large inputs with complex Spirit grammars:

• Deferred construction and minimal copying of attribute values
• Lexical analysis for faster backtracking
• A special directive for using qi::symbols alongside a lexer
• Linear allocators for faster AST node allocation
• Intrusive reference counting for even faster AST node allocation/copying
• Grammar transformations for general optimality
• Abuse of the &-predicate for skipping expensive productions
• Dividing grammars into multiple implementation files for minimal recompilation times

Thanks Mike for sharing your work! I’m sure many Spirit developers will find it very enlightening and encouraging to read about your work. Keep up the excellent work!

Generally, all changes are supposed to be fully backwards compatible. If you run into problems with your existing code, please tell us by leaving a comment or by sending a message to the Spirit mailing list (as described on our Support page).

http://blip.tv/boostcon/ast-construction-with-the-universal-tree-5266608

utree, a recent addition to the Boost.Spirit codebase, is a generic data structure designed to represent abstract syntax trees. Bindings to Qi and Karma make utree a powerful tool for parser and generator development with Boost.Spirit. This presentation would demonstrate the usage of utree and Spirit to build and manipulate an abstract syntax tree for four parsing/generating use cases: XML, symbolic expressions, JSON, and C-like source code. The details of utree’s integration with Spirit and their implications for writing utree-centric Spirit parsers and generators would be discussed. Additionally, design patterns for compiling a utree AST to other internal representations (DOM tree for XML, function tree for a Scheme-like language for symbolic expressions, associative arrays for JSON objects, a simple VM bytecode for mini-C source code) would be covered.

Here are the slides:

https://github.com/boostcon/2011_presentations/raw/master/fri/utree_talk.pdf

http://blip.tv/boostcon/phoenix-v3-an-overview-5250984

The slides for this talk can be found here: https://github.com/boostcon/2011_presentations/blob/master/mon/phoenix_v3.pdf?raw=true.

Phoenix will be the next generation of creating unnamed, inlined polymorphic function objects. With V3 we combine the functionality of Boost.Bind and Boost.Lambda, and arranges it into a new library. By writing this new library, we were able to fix some limitations of the aforementioned libraries without breaking backwardscompatibility. The purpose of the talk will be to outline the importance and elegance of functional programming (FP) in C++. The first part of the talk will give an introduction into the Domain Specific Embedded Language (DSEL) we defined with Phoenix. A DSEL is built with the help of regular C++ function and operator overloads. For Phoenix we defined such a language that emulates C++, to give potential users a low entry into the world of FP. While a lot of existing C++ code relies on higher order functions (better known as function objects), e.g. the C++ standard library use them as a way to let users customize operations in certain algorithms. We focus the second part of the talk on examples on how to use Phoenix instead of writing regular function objects and how to enable your legacy code to be used inside Phoenix expressions. However, Phoenix is more. Phoenix is equipped with a unique (in C++) mechanism to handle the expressions discussed in the previous sections as data. This allows us to handle Phoenix not in the C++ standard way but in any way you like. An overview of these mechanisms will be given in the last part of the talk to give potential users an insight on possible future applications that might evolve around Phoenix.

http://blip.tv/boostcon/spirit-qi-in-the-real-world-5254335

You can find the slides here: https://github.com/boostcon/2011_presentations/raw/master/tue/spirit_qi_in_the_real_world.pdf

Past sessions on Spirit have focused on introducing Spirit or showing extracts of real use, intermingled with tutorial highlights. Upon writing real Spirit.Qi parsers, however, one quickly discovers that “the devil is in the details.” There are special cases, tricks, and idioms that one must discover by trial and error or, perhaps, by following the Spirit mailing list, all of which take time and may not be convenient. In this session, we’ll walk through the development of a Spirit.Qi parser for printf()-style format strings. The result will be a replacement for printf() that is typesafe and efficient.

Those of you familiar with the Nabialek trick will recognize it’s working under the hood. What you can achieve with the keywords parser can also be achieved with the Nabialek trick but not always as elegantly or as efficiently.

The two examples presented below are included in the spirit repository and can be found in the folder :

libs/spirit/repository/example/qi

Data members marked by keywords (options.cpp)

For this small introduction we’ll consider parsing a program command line.

Options are commonly passed to applications delimited by option keywords :

mySuperCompiler --include includePath --define newSymbol=10 --output output.txt --define newSymbol2=20 --source mySourceFile

The order in which the options are specified doesn’t matter at all. The task of the parser we are going to write is to extract the individual options into some internal data structure we will use to control the program.

Here are the structures we could use to hold the options passed to our command line :

// A basic preprocessor symbol</pre>
typedef std::pair<std::string, int32_t> preprocessor_symbol;

struct program_options {
   // symbol container type definition
   typedef std::vector< preprocessor_symbol > preprocessor_symbols_container;</pre>
   // include paths
   std::vector<std::string> includes;
   // preprocessor symbols
   preprocessor_symbols_container preprocessor_symbols;
   // output file name
   boost::optional<std::string> output_filename;
   // input file name
   std::string source_filename;
};

Of course  the structures are adapted to be compatible with fusion in order to get the data pulled into the structures easily.

Now lets define our options rule:

rule<const char *, program_options(), space_type> kwd_rule;

kwd_rule %= kwd("--include")[
                parse_string
            ]
          / kwd("--define") [
                parse_string
                >> (
                    (lit('=') > int_) | attr(1)
                   )
            ]
          / kwd("--output",0,1)[
                parse_string
            ]
          / kwd("--source",1)[
                parse_string
            ]
          ;

The first thing to notice here is that we used the %= operator. This means that the parsing construct we just wrote has an attribute type compatible with the attribute type of our adapted structure!

This is one spot were the keyword parsing construct surpasses the Nabialek trick. The Nabialek trick just can’t do that.

On the next lines we define our keyword parsing constructs. Writing

kwd("--include")[ parse_string ] 

is equivalent to writing:

lit("--inlude") > parse_string

The word “–include” must be followed by a string.

The kwd directive has the ability to be combined by using the / operator. The kwd directive and the operator / work tightly together to achive the goal of attribute compatibility while using the Nabialek trick.

One last thing to notice is the occurrence constraints which can be associated with a kwd directive. It works like the repeat directive and enables to add additional validation checks inside the keyword parsing loop.

Writing

kwd("--output",0,1)[ parse_string ] 

means that the keyword “–output” may occur 0 or 1 times at most. If it occurs more than once the parser will fail.

Writing

kwd("--source",1)[ parse_string ] 

means that the keyword “–source” must occur once and only once. This works just like the repeat directive.

Using occurrence constraints doesn’t cost much on the runtime performance and gives the ability to easily enforce constraints which would be otherwise way much more difficult to formulate.

The kwd directive also exists in a case insentive variant : ikwd. You can combine the kwd and ikwd freely inside the same keyword block at the cost of a small runtime overhead.

Derived structures (derived.cpp)

A recent post in the mailing list gave me the idea to provide an example of how the keyword parser can be used to produce different derived structures depending on keywords placed in the input.

Here’s the problem as described by MM:

“I have a case where I have a prefix string that will distinguish what will follow it.

prefix string - struct members

this is what is read from the input stream. I have a base struct and 5 derived D1..D5, each derived has a different prefix as a static const std::string member. Parsing the prefix string tells me which struct D1..D5 I should parse after. All these derived structs are fusion adapted. There is a rule for each of the derived.”

To keep the example simple here are the classes we could consider:

struct base_type {
    base_type(const std::string &name) : name(name)  {}

    std::string name;
    virtual std::ostream &output(std::ostream &os) const {
        os<<"Base : "<<name;        return os;
    }
};

struct derived1 : public base_type {
    derived1(const std::string &name, unsigned int data1) :
        base_type(name)
      , data1(data1)  {}

    unsigned int data1;
    virtual std::ostream &output(std::ostream &os) const {
        base_type::output(os);
        os<<", "<<data1;
        return os;
    }
};

struct derived2 : public base_type {
    derived2(const std::string &name, unsigned int data2) :
        base_type(name), data2(data2)  {}

    unsigned int data2;
    virtual std::ostream &output(std::ostream &os) const    {
        base_type::output(os);
        os<<", "<<data2;
        return os;
    }
};

struct derived3 : public derived2 {
    derived3(const std::string &name, unsigned int data2, double data3) :
      derived2(name,data2)
    , data3(data3)
    {}

    double data3;
    virtual std::ostream &output(std::ostream &os) const    {
        derived2::output(os);
        os<<", "<<data3;
        return os;
    }
};

Our parse result must be a vector of pointers to our base class:

std::vector<base_type*>

To get that done, we’ll use semantic actions inside the kwd directive:

kwd_rule = kwd("derived1")[
              ('=' > parse_string > int_ )
              [phx::push_back(_val,phx::new_<derived1>(_1,_2))]
           ]
         / kwd("derived2")[
              ('=' > parse_string > int_ )
              [phx::push_back(_val,phx::new_<derived2>(_1,_2))]
           ]
         / kwd("derived3")[
              ('=' > parse_string > int_ > double_)
              [phx::push_back(_val,phx::new_<derived3>(_1,_2,_3))]
           ]
           ;

This rule will construct new derived classes and append them to our result vector during parsing. The input parsed by this construct is of the form:

 derived2 = "object1" 10 derived3= "object2" 40 20.0 

Keywords vs Nabialek trick

Here’s a small table to compare the features of the keyword parsing constructs and the Nabialek trick to help you decide which solution better suits your needs.

The keywords parsing construct can save a lot of typing over the Nabialek trick and has in many cases even better performance. It also makes retrieving the parsed data into the program usable structures much easier as it supports attribute propagation. The main limitation of the keyword parser is the number of keywords a keyword block may contain ( limited by the maximum size of the variant type BOOST_VARIANT_LIMIT_TYPES).