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

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-05-22 02:57:20

"Vladimir Prus" <ghost_at_[hidden]>

[argh...] Obviously I wrote the pseudo code too quickly, because it had
multiple pseudo bugs.

    istream& operator>>(istream& s, complex& a)
    {
        Terminal<double> re, im(0); // Don't forget initialization!

        // Generates the parser from the grammar expression
        Parser parser = re
                      | '(' + re + ')'
                      | '(' + re + ',' + im + ')'
                      ;

        if (s >> parser) // This may change the stream state!
        {
            // Assign only if parsing completes succesfully
            a = complex(re,im);
        }

        return s;
    }

> Well, this is nice. However, it seems like the grammar here is not LL(1).
Am
> I wrong? If I right, how this is supposed to work.

[Seems like I have to order a copy of the dragon book to the office as well.
Books are never there when you need them.]

Anyway, you are right that the above grammar is not LL(1). However, it is
possible to transform it to LL(1) by using left factoring:

    C   -> f
    C   -> ( f C'
    C'  -> )
    C'  -> , f )

This transformation could perhaps be done by a metaprogram that generates
the parser from the grammar specification.

There is at least one problem. The terminals '(', ',' and ')' have to be
typified. For instance (loaning a few names from Spirit):

    Parser parser = re
                  | oppar + re + clpar
                  | oppar + re + comma + im + clpar
                  ;

Where oppar, comma and clpar are defined something like this:

    Ch<'('> oppar;
    Ch<')'> clpar;
    Ch<','> comma;

(This would be different from Spirit.)

I think that the above syntax would be implementable, although not trivial,
using expression templates and metaprogramming.

An alternative to transforming the grammar to LL(1) by a metaprogram would
be to implement back tracking as is done by Spirit. Even with the slower
parsing implied by back tracking, I think that such a framework would be
quite useful for implementing micro parsers.

> > > Template metaprograms are very hard to write, debug and use.
>
> > True, but the problems are solvable and the benefits are clear.
>
> I would like to see working implementation that can handle syntax that
you've
> given a few lines above.

Me, too!