|
|
Boost : |
Subject: Re: [boost] [spirit] alert when backtracking?
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2011-03-08 08:07:30
> > 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
-- Dr. Arno Schödl | aschoedl_at_[hidden] Technical Director think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany http://www.think-cell.com | phone +49 30 666473-10 | US phone +1 800 891 8091 Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk