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

Subject: Re: [boost] [spirit] alert when backtracking?
From: Larry Evans (cppljevans_at_[hidden])
Date: 2011-03-09 08:48:35

On 03/08/11 07:07, Arno Schödl wrote:
>>> 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.
>
>> Spirit.Qi backtracks only when using alternatives. That's easy enough to
>> spot by looking at the granmmar.
>
> Kleene Stars can also backtrack, right? It tries the rule, and
> aborts the loop when the rule fails, where failure of the rule may
> involve backtracking?
>
> I know that Spirit.Qi does not build lookahead tables, but simply
> executes the rule and backtracks. But as long as this backtrack
> happens after a single character, I'd expect a performance similar
> to LL(1) parsers like ANTLR - they are effectively doing the same
> thing. What I'd like to know is if there is more backtracking than
> one character. Maybe I could write an instrumented iterator that
> does the check at runtime. Compile time would be nice and possible,
> but more difficult.
>
> Regards,
>
> Arno
>
[snip]

I'd guess that most characters have no semantic actions associated
with them, and that, consequently, when semantic actions have to be
undone, that this involves backing up the lexer by more than 1
character.  Thus, I'd guess the problem reported in this thread:

  http://sourceforge.net/mailarchive/message.php?msg_id=27132247

would be an example of 'more backtracking than one character'.