Is pyparsing really a recursive descent parser?

[Neil Cerutti]

On 2007-11-05, Just Another Victim of the Ambient Morality
<ihatespam at hotmail.com> wrote:
> "Kay Schluehr" <kay.schluehr at gmx.net> wrote in message 
> news:1194223837.104424.242360 at o3g2000hsb.googlegroups.com...
>> I'm not sure one needs to start again with a naive approach
>> just to avoid any parser theory. For a user of a parser it is
>> quite important whether she has to wait 50 seconds for a parse
>> to run or 50 milliseconds. I don't like to compromise speed
>> for implementation simplicity here.
>
>     This attitude is all too prevalent among computer
> professionals...  Of course it's a useful thing to shield users
> from the intricacies of parser theory!  Just as much as it is
> useful to shield drivers from needing automotive engineering or
> software users from programing.  How many people have come to
> this newsgroup asking about anomalous pyparsing behaviour,
> despite their grammars being mathematically correct.

You might be interested in the Early parsing algorithm. It is
more efficient than the naive approach used in your prototype,
and still handles ambiguous grammars.

There is a Python module SPARK that provides generic classes for
building small language compilers using an Early parser, and I
was able to get it to parse your ambiguous grammar without
trouble. It is not as convenient or as well documented as
PyParsing, but the parsing algorithm provides the power you're
looking for. It might serve as a backend for the library you're
currently working on.

http://www.cpsc.ucalgary.ca/~aycock/spark/

-- 
Neil Cerutti