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

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-05-26 02:38:01

joel de guzman wrote:
> 
> From: "John Max Skaller" :

> > (a|b)*abb

> Right. (a|b) will consume all 'ab's with RD.

        Yeah. Which shows just how weak RD is:
it won't even process regular expressions.

> Is my understanding correct?

        Yes.

> That's very cool! I'm learning a lot from you guys.

        Worth getting a copy of the bible here: the
infamous Dragon Book. [Aho, Sethi, Ullman
Compilers: Principles, Techniques and Tools]
 
> ... Ok so help me out. Is it ok if I take 'exhaustive'
> out from the definition? Or, would you happen to have
> a better description?

        What I had was a question: I haven't looked
at Spirit, so I don't know what class of parser it is.
If it is RD, just say that.

        'General' RD is quite slow. [Handles LL(inf) though]
However, there is useful subclass call 'predictive' parsers.
For example parsing:

        function ....
        procedure ...
        while .....
        ...
        [one other case]	

you notice that almost everything starts with a unique keyword.
So you don't need to 'recurse' into each case, execute
the match function, and fail, then go to the next case:
you can use an STL map of keywords to productions.
If you can do this at _every_ point, the grammar is LL(1),
and you can use a predictive RD parser. These things are very
fast O(n) because they never fail on correct input. If you carry
the analysis through, you find you can drive the whole parser
with a table. However, you do have to analyse the grammar.

-- 
John (Max) Skaller, mailto:skaller_at_[hidden]
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net