C++ Blog

Boost.Spirit : Complete Parser Design

Posted in boost, templates by Umesh Sirsiwal on December 25, 2009

Note that this post applies to Spirit.Classic or 2.0.

In the last post we discussed how to write a simple parser using Spirit. Most real life parsers are a lot more complex requiring several rules and combining them to create a full grammar. Spirit provides support to declare a full grammar. Let us create a parser which looks for all mailto: tag with associated e-mail address in an input. All Spirit grammar are derived from grammar class. The following is definition of grammar:

 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; }
        };
    };

The my_grammar is derived from grammar class using curiously recurring template pattern (CRTP). For those who are new to CRTP, it was introduced by Jim Copelien and Wikipedia has some details on it. Using CRTP it is possible to achieve effect of dynamic polymorphism without taking cost of virtual function. More on CRTP another day.

Each grammar class must define another nested structure called definition. The definition must have a function called start which returns starting parser rule. So let us start writing rules for e-mail address parser. The mailto rule can be written as:

     mailTo = "mailto:" >> emailAddress;

From our previous post, emailAddress can be written as:

     emailAddress =  lexeme_d[ +alnum_p >> '@' >> +alnum_p >> *('.' >> +alnum_p)];

Of course the full input has things other than the mailto: tags. So we must skip other characters. You do that as follows:

       r = mailTo | anychar_p;

The above rule is saying that try matching the input with mailTo and if it does not match mailTo rule, match it against any character parser.

So combining these two the grammar constructor now can be written as:

      definition(my_grammar const& self)  { 
            r = mailTo | anychar_p;
            mailTo = "mailTo:" >> emailAddress;
            emailAddress = lexeme_d[ +alnum_p >> '@' >> +alnum_p >> *('.' >> +alnum_p)];
      }

First thing one notices is that the rule “r” refers to rules “emailAddress” and “mailTo” before they are initialized. It works because the rules are held by reference and not by value. The referred rule can be initialized anytime. This does complicate programming a little bit. It means that it is user’s responsibility to make sure that the referred rules never go out of scope. So emailAddress cannot be local to definition. Typically, one declares all rules as part of the definition call definition. The full grammar now becomes:

 struct my_grammar : public grammar<my_grammar>
    {
        template <typename ScannerT>
        struct definition
        {
            rule<ScannerT>  r;
            rule<ScannerT>  emailAddress mailTo;
            definition(my_grammar const& self)  { 
                r = mailTo | anychar_p;
                mailTo = "mailTo:" >> emailAddress;
                emailAddress = lexeme_d[ +alnum_p >> '@' >> +alnum_p >> *('.' >> +alnum_p)];
            }
            rule<ScannerT> const& start() const { return r; }
        };
    };

OK! now we have the grammar. Let us use it.

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

Here first and last are iterators pointing to first and the last characters in the input.

Note that the above grammar matches exactly one e-mail address or any other character. This can be easily be modified to match all e-mail addresses.

The new rule will be:

r = *(mailTo | anychar_p);


Advertisements

Boost.Spirit – Easy to use Parser

Posted in boost by Umesh Sirsiwal on December 20, 2009

Note that this post applies to Spirit.Classic or 2.0.

I recently had write a parser in C++ and decided to give Boost.Spirit a chance. I was delighted with ease of use of the parser itself. It was a steep learning curve to get started. However, once I got started, it made life significantly simple.

Boost.Spirit provides a very simple way to create a parser using EBNF grammar. Let us consider an e-mail address parser as an example.
+alnum_p >> '@' >> +alnum_p >> *('.' >> +alnum_p);
Simple! Let us understand the above statement. In Boost.Spirit rule<> template defines basic grammar rule. A rule is made up of parsers and other rules. In Boost.Spirit built-in parser all have _p as suffix. The alnum_p parser matches any character or number. ‘+’ represents operator which matches one more more instances of the enclosed parser.

‘>>’ is an overloaded operator which simply says followed by.’@’ is short form of parser which matches character ‘@’.

So the above statement says any alphanumeric string followed by ‘@’ followed by any other alpha numeric string. This can than be followed by any number of “.<alphanumber>”.

By default the >> includes white space skipping. This implies the above parser will match (a@b as well as a @ b).

We don’t want white space skipping for e-mail address. So we need to modify the above rule such that >> does not skip white space. For this and other purposes, the Spirit allows directives. These are special instructions which can be applied to a part of the rule. No white space skipping is achieved by using lexeme_d.
lexeme_d[ +alnum_p >> '@' >> +alnum_p >> *('.' >> +alnum_p);];

I have no clue why the name. But the suffix is _d for all directives.OK! we got a rule. Now let us check if this rule matches a specified string:

bool isEmailAddress(const std::string& str){
return parse(str, lexeme_d[ +alnum_p >> '@' >> +alnum_p >> *('.' >> +alnum_p);], space_p).full;
}

The above statement will check if the supplied string is an e-mail address or not.

In the next post we will discuss how to create more complex examples as well as deal with parse actions.