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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk