...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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.
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 qi::raw; using ascii::char_; using ascii::string; using namespace qi::labels; using phoenix::at_c; using phoenix::push_back; text %= lexeme[+(char_ - '<') ] ; // [_val = phoenix::construct<std::string>(begin(_1),end(_1))]; node = (xml | text) [_val = _1]; start_tag %= '<' >> !lit('/') >> raw[lexeme[+(char_ - '>')]] >> '>' ; 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
).
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]] >> '>' ;
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_tag
s 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.
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 Phoenix placeholder for
the first inherited attribute (we have only one, use _r2
,
_r3
, etc. if you have more).
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 Phoenix.
So, what's happening?
start_tag
,
the parsed start-tag string is placed in at_c<0>(_val)
.
node
s.
At each step, we push_back
the result into at_c<1>(_val)
.
end_tag
giving it an inherited attribute: at_c<0>(_val)
. This is the string we obtained from
the start_tag
. Investigate
end_tag
above. It will
fail to parse if it gets something different from what we got from
the start_tag
. This
ensures that our tags are balanced.
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
.
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 };
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
.
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) )
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:
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) ;
start_tag
,
the parsed start-tag string is placed in the local variable specified
by (yet another) Phoenix
placeholder: _a
. We
have only one local variable. If we had more, these are designated
by _b
.._z
.
node
s.
end_tag
giving it an inherited attribute: _a
,
our local variable.
There are no actions involved in stuffing data into our xml
attribute. It's all taken care of thanks to the auto-rule.