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

From: David Abrahams (dave_at_[hidden])
Date: 2004-12-24 18:44:31

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