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

Subject: Re: [boost] [spirit] alert when backtracking?
From: Hartmut Kaiser (hartmut.kaiser_at_[hidden])
Date: 2011-03-09 08:59:22

> > > 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?

Indeed. Now as I think of it, more parsers do backtrack more than one
character (actually all parsers matching more than one character will do so
when failing).

> 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.

I'm not sure about compile time detection, but runtime detection should be
feasible.

Thanks!
Regards Hartmut
---------------
http://boost-spirit.com