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

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-05-28 19:57:14

Vladimir Prus wrote:

> >It can be shown that RTN's can recognize all context free
> >languages. This is much more powerful than regular,
> >LL(1), or RD.
 
> Interesting. What is average/worst case complexity?

        Don't know, but I guess the same as RD.

 Can you give a link to
> some paper that discusses RTN?

        I read a paper 20 years ago, I don't have it
anymore.  The best 'link' I can mention is to Python,
where there are links to the tool used to generate
the automata from the meta-grammar. I have a vague
memory that the Python parser was the subject of
Guido van Rossum's PhD thesis.

        I note that I once built a regular expression
analyser using templates (so char was replaced by T).
You have to use an STL map instead of an array,
so the result is not so good for an ordinary
grammar where chars are integers. But it should be
possible to use an object and virtual functions
and then instantiate it so that virtual dispatch
is used to do the recursion. [If the RD fails,
return NULL, otherwise return a pointer to the
parse tree for the non-terminal the object
represents .. you are left with the problem 
of building the parse tree for the automaton,
which is probably just a list. On failure,
you try the next case, if there isn't one,
return NULL]

        Finally: you can just build an NFA
to get it working. The conversion to a DFA
will eliminate duplicate recusions, but unlike
a 'real' DFA, you still have to 'recurse' to see
if a branch can be taken: you can't select the
branch by indexing, the way you can with a DFA
with indexable inputs.

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