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