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

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-05-24 08:39:11

On Wednesday 23 May 2001 20:51, you wrote:
> Douglas Gregor wrote:
> > On Monday 21 May 2001 21:09, you wrote:
> > > joel de guzman wrote:
> > > > Spirit reflects more the top-down parser we build by hand. Albeit
> > > > automated. The non-deterministic nature minimises the restrictions
> > > > on the grammar. One exception is left recursion which is a no-no
> > > > on LL(N) parsers.
> > >
> > >       Sounds like an Early parser?
> >
> > Earley parsers aren't LL(k) but can parse any context-free language and
> > are worst-case O(n^3).
> >
> > 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).
>
> There's a link on my webpage at 
> http://sites.netscape.net/cppljevansusa/homepage to a ps description of a
> similar idea, but it creates a comiler for LL(1) grammars. All the
> productions were placed in a container of some sort and each non-terminal
> had a FIRST and FOLLOW and NULLIBLE member variable.  So, one problem with
> maintaining SPIRIT as is but allowing more efficient implementation  would
> be that there would have to be a parallel heirarchy of classes augmented
> with these member variables or attributes.  Anyway, the above ps

Well, it doesn't necessarily need a parallel hierarchy in practice - just 
allow mixins or even just an 'any' which contains the data.

> description has most or all of the source code; so, it may be a starting
> point for this "compile" idea.  However, it wasn't in-place.  It generated
> c++ code for the compiler.  To make this in-place would involve some sort
> of internal rep for c++ classes which could then be interpreted by some
> "virtual compiler?" Or am I misunderstanding what you mean by "in-place"?

"In-place" as in dyanmically at run-time, but without requiring another 
compilation stuff. For instance, it would be possible with Spirit to have the 
user input a set of EBNF rules and then immediately try to parse input, 
without resorting to dirty tricks.

        Doug