Boost C++ Libraries

Stop and think about it... We've come very close to generating an AST (abstract syntax tree) in our last example. We parsed a single structure and generated an in-memory representation of it in the form of a struct: the struct employee. If we changed the implementation to parse one or more employees, the result would be a std::vector<employee>. We can go on and add more hierarchy: teams, departments, corporations. Then we'll have an AST representation of it all.

In this example (actually two examples), we'll now explore how to create ASTs. We will parse a minimalistic XML-like language and compile the results into our data structures in the form of a tree.

Along the way, we'll see new features:

The full cpp files for these examples can be found here: ../../example/qi/mini_xml1.cpp and here: ../../example/qi/mini_xml2.cpp

There are a couple of sample toy-xml files in the mini_xml_samples subdirectory: ../../example/qi/mini_xml_samples/1.toyxml, ../../example/qi/mini_xml_samples/2.toyxml, and ../../example/qi/mini_xml_samples/3.toyxml for testing purposes. The example ../../example/qi/mini_xml_samples/4.toyxml has an error in it.

First Cut

Without further delay, here's the first version of the XML grammar:

template <typename Iterator>
struct mini_xml_grammar : qi::grammar<Iterator, mini_xml(), ascii::space_type>
{
    mini_xml_grammar() : mini_xml_grammar::base_type(xml)
    {
        using qi::lit;
        using qi::lexeme;
        using ascii::char_;
        using ascii::string;
        using namespace qi::labels;

        using phoenix::at_c;
        using phoenix::push_back;

        text = lexeme[+(char_ - '<')        [_val += _1]];
        node = (xml | text)                 [_val = _1];

        start_tag =
                '<'
            >>  !lit('/')
            >>  lexeme[+(char_ - '>')       [_val += _1]]
            >>  '>'
        ;

        end_tag =
                "</"
            >>  string(_r1)
            >>  '>'
        ;

        xml =
                start_tag                   [at_c<0>(_val) = _1]
            >>  *node                       [push_back(at_c<1>(_val), _1)]
            >>  end_tag(at_c<0>(_val))
        ;
    }

    qi::rule<Iterator, mini_xml(), ascii::space_type> xml;
    qi::rule<Iterator, mini_xml_node(), ascii::space_type> node;
    qi::rule<Iterator, std::string(), ascii::space_type> text;
    qi::rule<Iterator, std::string(), ascii::space_type> start_tag;
    qi::rule<Iterator, void(std::string), ascii::space_type> end_tag;
};

Going bottom up, let's examine the text rule:

rule<Iterator, std::string(), space_type> text;

and its definition:

text = lexeme[+(char_ - '<')        [_val += _1]];

The semantic action collects the chars and appends them (via +=) to the std::string attribute of the rule (represented by the placeholder _val).

Alternates

rule<Iterator, mini_xml_node(), space_type> node;

and its definition:

node = (xml | text)                 [_val = _1];

We'll see a mini_xml_node structure later. Looking at the rule definition, we see some alternation going on here. An xml node is either an xml OR text. Hmmm... hold on to that thought...

rule<Iterator, std::string(), space_type> start_tag;

Again, with an attribute of std::string. Then, it's definition:

start_tag =
        '<'
    >>  !char_('/')
    >>  lexeme[+(char_ - '>')       [_val += _1]]
    >>  '>'
;

Not Predicate

start_tag is similar to the text rule apart from the added '<' and '>'. But wait, to make sure that the start_tag does not parse end_tags too, we add: !char_('/'). This is a "Not Predicate":

!p

It will try the parser, p. If it is successful, fail; otherwise, pass. In other words, it negates the result of p. Like the eps, it does not consume any input though. It will always rewind the iterator position to where it was upon entry. So, the expression:

!char_('/')

basically says: we should not have a '/' at this point.

Inherited Attribute

The end_tag:

rule<Iterator, void(std::string), space_type> end_tag;

Ohh! Now we see an inherited attribute there: std::string. The end_tag does not have a synthesized attribute. Let's see its definition:

end_tag =
        "</"
    >>  lit(_r1)
    >>  '>'
;

_r1 is yet another Boost.Phoenix placeholder for the first inherited attribute (we have only one, use _r2, _r3, etc. if you have more).

A Lazy Lit

Check out how we used lit here, this time, not with a literal string, but with the value of the first inherited attribute, which is specified as std::string in our rule declaration.

Finally, our xml rule:

rule<Iterator, mini_xml(), space_type> xml;

mini_xml is our attribute here. We'll see later what it is. Let's see its definition:

xml =
        start_tag                   [at_c<0>(_val) = _1]
    >>  *node                       [push_back(at_c<1>(_val), _1)]
    >>  end_tag(at_c<0>(_val))
;

Those who know Boost.Fusion now will notice at_c<0> and at_c<1>. This gives us a hint that mini_xml is a sort of a tuple - a fusion sequence. at_c<N> here is a lazy version of the tuple accessors, provided by Boost.Phoenix.

How it all works

So, what's happening?

To give the last item some more light, what happens is this:

end_tag(at_c<0>(_val))

calls:

end_tag =
        "</"
    >>  lit(_r1)
    >>  '>'
;

passing in at_c<0>(_val), the string from start tag. This is referred to in the end_tag body as _r1.

The Structures

Let's see our structures. It will definitely be hierarchical: xml is hierarchical. It will also be recursive: xml is recursive.

struct mini_xml;

typedef
    boost::variant<
        boost::recursive_wrapper<mini_xml>
      , std::string
    >
mini_xml_node;

struct mini_xml
{
    std::string name;                           // tag name
    std::vector<mini_xml_node> children;        // children
};

Of Alternates and Variants

So that's what a mini_xml_node looks like. We had a hint that it is either a string or a mini_xml. For this, we use Boost.Variant. boost::recursive_wrapper wraps mini_xml, making it a recursive data structure.

Yep, you got that right: the attribute of an alternate:

a | b

is a

boost::variant<A, B>

where A is the attribute of a and B is the attribute of b.

Adapting structs again

mini_xml is no brainier. It is a plain ol' struct. But as we've seen in our employee example, we can adapt that to be a Boost.Fusion sequence:

BOOST_FUSION_ADAPT_STRUCT(
    client::mini_xml,
    (std::string, name)
    (std::vector<client::mini_xml_node>, children)
)

One More Take

Here's another version. The AST structure remains the same, but this time, you'll see that we make use of auto-rules making the grammar semantic-action-less. Here it is:

template <typename Iterator>
struct mini_xml_grammar
  : qi::grammar<Iterator, mini_xml(), qi::locals<std::string>, ascii::space_type>
{
    mini_xml_grammar()
      : mini_xml_grammar::base_type(xml)
    {
        using qi::lit;
        using qi::lexeme;
        using ascii::char_;
        using ascii::string;
        using namespace qi::labels;

        text %= lexeme[+(char_ - '<')];
        node %= xml | text;

        start_tag %=
                '<'
            >>  !lit('/')
            >>  lexeme[+(char_ - '>')]
            >>  '>'
        ;

        end_tag =
                "</"
            >>  string(_r1)
            >>  '>'
        ;

        xml %=
                start_tag[_a = _1]
            >>  *node
            >>  end_tag(_a)
        ;
    }

    qi::rule<Iterator, mini_xml(), qi::locals<std::string>, ascii::space_type> xml;
    qi::rule<Iterator, mini_xml_node(), ascii::space_type> node;
    qi::rule<Iterator, std::string(), ascii::space_type> text;
    qi::rule<Iterator, std::string(), ascii::space_type> start_tag;
    qi::rule<Iterator, void(std::string), ascii::space_type> end_tag;
};

This one shouldn't be any more difficult to understand after going through the first xml parser example. The rules are almost the same, except that, we got rid of semantic actions and used auto-rules (see the employee example if you missed that). There is some new stuff though. It's all in the xml rule:

Local Variables

rule<Iterator, mini_xml(), locals<std::string>, space_type> xml;

Wow, we have four template parameters now. What's that locals guy doing there? Well, it declares that the rule xml will have one local variable: a string. Let's see how this is used in action:

xml %=
        start_tag[_a = _1]
    >>  *node
    >>  end_tag(_a)
;

There are no actions involved in stuffing data into our xml attribute. It's all taken care of thanks to the auto-rule.