Is pyparsing really a recursive descent parser?

Neil Cerutti horpner at yahoo.com
Mon Nov 5 00:27:18 CET 2007


On 2007-11-04, Just Another Victim of the Ambient Morality
<ihatespam at hotmail.com> wrote:
> "Neil Cerutti" <horpner at yahoo.com> wrote in message 
> news:nPnXi.39845$G23.30920 at newsreading01.news.tds.net...
>> I believe there's no cure for the confusion you're having except
>> for implementing a parser for your proposed grammar.
>> Alternatively, try implementing your grammar in one of your other
>> favorite parser generators.
>
>     I believe there is a cure and it's called recursive descent
> parsing. It's slow, obviously, but it's correct and, sometimes
> (arguably, often), that's more important the execution speed.
>
>     I spent this morning whipping up a proof of concept parser
> whose interface greatly resembles pyparsing but, baring unknown
> bugs, works and works as I'd expect a recursive descent parser
> to work.  I don't know Python very well so the parser is pretty
> simple.  It only lexes single characters as tokens.  It only
> supports And, Or, Optional, OneOrMore and ZeroOrMore rules but
> I already think this is a rich set of rules.  I'm sure others
> can be added.  Finally, I'm not sure it's safely copying all
> its parameter input the same way pyparsing does but surely
> those bugs can be worked out.  It's merely a proof of concept
> to demonstrate a point.
>     Everyone, please look it over and tell me what you think. 
> Unfortunately, my news client is kind of poor, so I can't
> simply cut and paste the code into here.  All the tabs get
> turned into single spacing, so I will post this link, instead:
>
> http://theorem.ca/~dlkong/new_pyparsing.zip

Your program doesn't necessarily address the ambiguity in the
grammar in question, since right now it is only a recognizer.
Will it be hard to get it to return a parse tree?

The grammar in your implementation is:

>>> goal = OneOrMore(RuleAnd('a') | RuleAnd('b')) + RuleAnd('b')
>>> goal.parse(0, 'ab')
True
>>> goal.parse(0, 'ba')
False
>>> goal.parse(0, 'b')
False
>>> goal.parse(0, 'aaab')
True
>>> goal.parse(0, 'abc')
True

So far so good. :)

-- 
Neil Cerutti



More information about the Python-list mailing list