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

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-05-27 11:29:19

joel de guzman wrote:

> I believe there's more we can squeeze from RD. 

        What you need is a Recursive Transition Network.
This is what Python uses. It is a very powerful blend
of recursive descent and finite state machines.

        The basic idea is that you have a finite state
automaton, in which a transition along an edge recursively
invokes another automaton. The automata are built from
a meta-grammar. Consider:

        X = (A|B)*ABB
        A = "a" | "A"
        B = "b" | "B

You build three finite state machines, one for each 
non-terminal: you can make Deterministic Automata,
and they're correctly recognize X, while RD will not.

It can be shown that RTN's can recognize all context free
languages. This is much more powerful than regular,
LL(1), or RD.

-- 
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