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