Re: [boost] [spirit] alert when backtracking?

Subject: Re: [boost] [spirit] alert when backtracking?
From: Larry Evans (cppljevans_at_[hidden])
Date: 2011-03-07 16:42:59

On 03/07/11 10:53, Arno Schödl wrote:
> Hello,
> 
>  
> 
> is there any way to detect at runtime or compile time whether Boost.Spirit needs backtracking? 
> It would be nice to be alerted to the fact that the grammar is not
LL(1) and thus has potential
> for optimization.
> 
> Regards,
> 
> Arno
[snip]
I'm not that familiar with spirit; however, I just can't imagine
how it would be practical (i.e. doesn't take sooo long) to calculate
this information at compile time.  I base this conclusion on the
outline for calculating just the lookahead sets for a simple gramar.
This outline is located in the boost vault directory:

http://www.boostpro.com/vault/index.php?&directory=Strings%20-%20Text%20Processing

in zip file:

  LewiLL1.lhs_rhs.zip

According to that file, it requires converging 3 times
over a complete traversal of the grammar.  Obviously,
to do that at compile time, based on reports of the
difficulty of doing subrules, it would take much too
much time.

OTOH, you could calculate the information offline
using the code (or rather an updated version of the
code) in this other zip file:

  cfg_lookahead_extends.zip

Of course that still wouldn't give you the final answer.
You'd finally have to, again, traverse the grammar
tree, testing each alternative to see if the lookahead
sets intersect for any pair of elements in an alternative.

Of course someone may have thought of alternative, but
that's how discouraging it looks to me ATM.

-Larry