Joel de Guzman wrote:
David Abrahams wrote:
Joel de Guzman wrote:
FYI, Spirit-2, being developed now, will focus on performance. A limited test case shows a significant increase in speed. And, yes, a deterministic parsing scheme (first/follow) is part of the plan. Actually, you can already take advantage of deterministic parsing using the current switch_p parsers or a technique we call the "Nabialek trick". Surely, more deterministic schemes will be in place.
Is first/follow really linked to determinism? It seems to me that you can use first/follow sets to prune unproductive searches in a nondeterministic parse, too (?)
Right. First-follow makes a parser predictive and thus deterministic,
Okay, either I'm "right" and first-follow can be used to prune unproductive parses in a nondeterministic parse *or* using first-follow makes a parser deterministic. It can't be both :) As I understand "nondeterministic" it just means you're doing backtracking when a parse gets into trouble, unlike in an NFA where you're conceptually moving along all viable paths in parallel. I don't see why the use of first/follow should preclude backtracking. You can always define ambiguous grammars with dynamic failure conditions.
typically with one symbol lookahead (LL(1)). A strictly predictive parser is a lot more restrictive in the grammars that one can use, however. There's no way to make it parse adhoc grammars like the C pre-processor or, ahem, c++. What I am inclined to do is to mix determinism with classic spirit's non-determinism. Exactly the recipe that you are alluding to.
I'm not sure if it is or not -- I'm just getting more confuseder. ;^) -- Dave Abrahams Boost Consulting http://www.boost-consulting.com