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