Re: [boost] Re: [ANN] Spirit C++ parser framework.

From: Greg Colvin (gcolvin_at_[hidden])
Date: 2001-05-22 22:10:54

From: joel de guzman <joel_at_[hidden]>
> From: "Douglas Gregor" :
> 
> > Earley parsers aren't LL(k) but can parse any context-free language and
> are
> > worst-case O(n^3).
> 
> If I am not mistaken. The original (there are variants) Earley parser
> is bottom up.

Earley (1970) says "... our algorithm is in effect a top-down parser
in which we carry along all possible parses simultaneously in such a
way that we can often combine like subparses.  This cuts down on
duplication of effort and also avoids the left-recursion problem."

> I'm more of a craftsman than a theorist. I don't know where the
> spirit parser falls into. The similarities between Spirit and the
> one Greg Colvin mentioned is purely coincidental.

Fair enough, but beware that there is an enormous literature and
lots of existing practice, and thus a high danger of either
reinventing the wheel or rolling blithely into well-known
bottomless pits ;->

> I wrote Spirit because I found a tremendous gap between simple regular
> expressions and full blown compiler-compilers. It has the un-restricted
> and non-deterministic flavor of REs with the ability to define rules and
> heirarchy of rules as compiler-compilers. Sure a C++ grammar would
> most probably choke the parser. But then again, because of its open-
> ended nature, I wouldn't know in the future. And I haven't really pushed
> the envolope yet. And of course, in the mean time this "lear-jet" might have
> uses that might be considered overkill for "747s".
> 
> I'm sure :-)
> 
> >
> > I think the Spirit C++ parser framework has a clean, readable syntax and
> that
> > it could form the basis for a great parsing library. I can envision using
> > Spirit C++ syntax and having several back-ends that can generate more
> > efficient parsers, but in-place. For instance, you create your grammar
> using
> > Spirit C++ syntax, but then you call a "compile" routine that generates an
> > efficient parser (probably an Earley parser, but one could tag it as
> LALR(k),
> > LL(k), etc. to get a more efficient but restricted parser).
> >
> 
> Thanks.
> 
> Yes, definitely that's possible. In fact the Longest[]  directive rewrites
> the parser composition hierarchy already.
> 
> One reason why I choose not to do optimisations is that I want the code
> to be very transparent-clear to facilitate its open-ended goal. Also, true
> to C++'s goal, I don't want the user to pay for things he might not need.
> Instead, I opted for extensibility.
> 
> At the very least, the generated parser can be thought of as an abstract
> EBNF syntax tree. I envision, as motivated by Douglas, something
> like:
> 
>    lalr = CompileToLALR(spirit);
> 
> ....Sure there are obstacles but this is interesting, George.
> 
> Joel de Guzman
> 
> 
> 
> 
> To unsubscribe, send email to: <mailto:boost-unsubscribe_at_[hidden]>
>  
> 
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
> 
> 
>