[boost] dynamic regex grammars (was: [Ann] Boost and Google Summer of Code 2007)

From: Eric Niebler (eric_at_[hidden])
Date: 2007-03-04 22:12:16

John Maddock wrote:
> Mathias Gaunard wrote:
>> What's the point of recursive regexes since we have xpressive?
> 
> xpressive can do that with static regexes, but not dynamic ones (interpreted
> strings).

This was on my TODO list for a long time, so I just implemented it. You 
can now build grammars with dynamic regexes, parsed at runtime. Here is 
a regex that matches infix algebraic expressions:

using namespace boost::xpressive;
using namespace regex_constants;

sregex expr;

{
     sregex_compiler compiler;
     syntax_option_type x = ignore_white_space;

     compiler.compile(
         "(? $group  = ) \\( (? $expr ) \\) ", x);
     compiler.compile(
         "(? $factor = ) \\d+ | (? $group ) ", x);
     compiler.compile(
         "(? $term   = ) (? $factor ) "
             " ( \\* (? $factor ) | / (? $factor ) )* ", x);
     expr = compiler.compile(
         "(? $expr   = ) (? $term )   "
             " ( \\+ (? $term )   | - (? $term )   )* ", x);
}

std::string str("foo 9*(10+3) bar");
smatch what;

if(regex_search(str, what, expr))
{
     // This prints "9*(10+3)":
     std::cout << what[0] << std::endl;
}

After the match, match results object contains the complete parse tree, 
where each invocation of a named regex creates a nested match results 
object.

It's a runtime configurable recursive descent parser (w/o semantic 
actions), with exhaustive backtracking semantics.

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com