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

Subject: Re: [boost] [spirit] alert when backtracking?
From: Joel de Guzman (joel_at_[hidden])
Date: 2011-03-07 20:51:05

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