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

From: joel de guzman (joel_at_[hidden])
Date: 2001-05-22 19:51:23

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.

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.

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