David Abrahams wrote:
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 :)
Using first-follow makes a parser deterministic, it can't be both. An LL(1) parser, for instance, doesn't do backtracking. It always has one and only one choice when faced with alternatives. It's roughly like the switch (deterministic) versus the cascading ifs (non-deterministic). However... (see below)
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. ;^)
Classic LL(1) does not have the "dynamic failure conditions" that you mention. LL(1) grammars cannot have ambiguity. If the grammar is ambiguous, first follow computation will fail (first follow conflicts). I'm developing a scheme where you can mix both predictive LL(1) with classic spirit's non-determinism. The scheme involves using a predictive front, backed up by a non-predictive fall-back step when ambiguity arises. It's roughly like combining the switch with cascading-ifs. It's still too early if such a scheme will hold water. AFAIK, no one has done it yet. An alternative scheme is to let the user switch strategies (possibly using spirit directives). Another scheme, used by PCCTS, is to make the parser predictive by default, and allow the user to use syntactic and semantic predicates with arbitrary lookahead on specific points in the grammar. Cheers, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net