Is pyparsing really a recursive descent parser?

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

On 2007-11-04, Just Another Victim of the Ambient Morality
<ihatespam at> wrote:
> "Neil Cerutti" <horpner at> wrote in message 
> news:nPnXi.39845$G23.30920 at
>> 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:

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')
>>> goal.parse(0, 'ba')
>>> goal.parse(0, 'b')
>>> goal.parse(0, 'aaab')
>>> goal.parse(0, 'abc')

So far so good. :)

Neil Cerutti

More information about the Python-list mailing list