On 3/8/2011 9:31 AM, Larry Evans wrote:
On 03/07/11 17:45, Hartmut Kaiser 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.
Does spirit backtrack at *every* alternative even if the grammar is LL(1)? IOW, spirit does *not* look ahead 1 token (as an LL(1) parser would) to decide which alternative has to be chosen. Instead, it just keeps trying the alternatives until 1 succeeds, and if none succeed then it backtracks to the last alternative that has not been exhaustively tried. Is that about right?
Yep, Spirit is PEG: http://en.wikipedia.org/wiki/Parsing_expression_grammar alternatives, to be pedantic, are more accurately called "Ordered choice". Some PEG parsers use tricks such as memoization to minimize the potential quadratic worst case performance, but in Spirit, we did not find the need. Spirit beats ANTLR/PCCTS speed, for example, which is an LL(k) parser. Techniques such as the Nabialek trick and use of syntactic and semantic predicates are enough. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com