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