[boost] Re: Interest in a Recursive Descent Parsing Library

From: Joel de Guzman (joel_at_[hidden])
Date: 2004-12-25 18:36:33

David Abrahams wrote:
> Joel de Guzman wrote:
> 
>>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. 
> 
> 
> Yes, but LL(1) is not synonymous with "recursive descent with first/follow."

Hmmm... I don't recall mentioning that. Did I?

>>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. 
> 
> 
> Yes, I know that.  But then, LL(1) is not synonymous with "recursive
> descent with first/follow."

Sure. But I don't see the point. What am I missing?

>>NLL(1) grammars cannot have ambiguity. If the grammar
>>is ambiguous, first follow computation will fail (first follow
>>conflicts).
> 
> 
> Hum?  The algorithm for computing the first and follow sets of a symbol
> don't have an "otherwise the computation fails" branch, and the
> definitions of these sets are simple:
> 
>   first(a) = the set of tokens that can begin strings derived from a.
>   follow(N) = the set of tokens that can follow N in grammatical sequences
> 
> You can use this information to eliminate hopeless branches of a parse
> and avoid wasting effort backtracking without requiring the grammar to
> be LL(1) or LL(2) or... even to be unambiguous at all.

Yes. In theory.

>>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.
> 
> 
> Maybe we're talking about the same thing.

Yes! That was what I was trying to point out from the start.
However, it's not as simple as it seems.

>>It's still too early if such a scheme will hold water. AFAIK, no one
>>has done it yet. 
> 
> 
> If you're talking about what I'm describing, I don't think there's
> anything particularly radical about it, and I'd be very surprised if it
> hadn't been done before.

AFAIK, no. Correct me if I'm wrong.

>>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.
> 
> 
> Eewww, I smell a kludge ;-)

Not really. There's a big problem with backtracking in general:
backtracking and semantic actions do not mix well (e.g. false
triggering). In a syntactic and semantic predicate, all actions
are intentionally inhibited.

Regards,
-- 
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net