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

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2001-05-23 19:51:55

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 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"?