Re: [boost] [ANN] xpressive 0.9.3 in boost-sandbox

From: Eric Niebler (eric_at_[hidden])
Date: 2005-07-04 15:00:16

Andreas Pokorny wrote:
> On Thu, Jun 30, 2005 at 12:02:18AM -0700, Eric Niebler <eric_at_[hidden]> wrote:
> 
>>   << Background >>
>>xpressive is a TR1 regex work-alike that also accepts regexes as 
>>expression templates and lets regexes nest and call each other recursively.
> 
> 
> How does xpressive implement recursive/nested regexes?
> The nested regexes look like context-free grammars. Is expressive
> able to handle LL-1 grammars only, or even RL grammars?
> 
> Regards 
> Andreas Pokorny
> 
> PS: I have not found enough time to implement some conveniece structures for
> spirit scanner generation based upon xpressive :(. 
> 

That's right, when using nested regexes with xpressive, you have the 
full power of context-free grammars. Its usefulness for creating parsers 
is limitted right now by the lack of semantic actions. Actions are a 
post-1.0 feature.

xpressive is an exhaustive backtracking NFA, like Perl's regex. A nested 
regex is treated like any other matching primitive -- a tail parser. If 
the tail parser fails at a given point, back up and try something 
different. Keep trying until you succeed or until all possibilities are 
exhausted.

It can be expensive, but there is a construct for turning off exhaustive 
backtracking for parts of your pattern that don't need it.

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