Is pyparsing really a recursive descent parser?

Just Another Victim of the Ambient Morality ihatespam at hotmail.com
Mon Nov 5 01:38:25 CET 2007


"Neil Cerutti" <horpner at yahoo.com> wrote in message 
news:qzsXi.39852$G23.9814 at newsreading01.news.tds.net...
> 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?

    Hey, it's only a proof of concept.  If you can parse the tree, surely 
you can record what you parsed, right?
    Did you notice that the parse() functions have the rather serious bug of 
not returning how much of the string they could parse?  It just so happens 
that the contstructions that I made only ever had to increment the matches 
by one, so they just happen to work.  That's an easy bug to fix but a pretty 
major one to have overlooked.  Hence, my enthusiasm for input...


> 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. :)

    Good!  Keep hammering at it!
    More importantly, study it to understand the idea I'm trying to convey. 
This is what I thought a recursive descent parser would do...






More information about the Python-list mailing list