Python parsing module

As Gre7g L already posted, enabling packrat parsing can be a big boost
(~1000X) to performance when using operatorPrecedence.

I just uploaded an example of parsing RE's
(http://pyparsing.wikispaces.com/space/showimage/invRegex.py) that I thought
was already on the Pyparsing wiki, so I'm sorry for not posting this sooner.
This particular example is an RE inverter, returning a generator of all
strings that would match the given RE (note: does not allow arbitrary
repetition operators such as '*' or '+', otherwise it would just blow up),
but it also uses opPrec.  Parsing "(foo(bar))" takes about 1/4 of a second -
still a long time, but I hope not ridiculously so.  Maybe this example might
shed some light on some alternative approaches to this problem.

-- Paul


-----Original Message-----
From: pyparsing-users-bounces@...
[mailto:pyparsing-users-bounces@...] On Behalf Of Andrew
Warkentin
Sent: Friday, July 04, 2008 10:43 PM
To: pyparsing-users@...
Subject: [Pyparsing] parsing an operator-precedence-based grammar
withreasonable performance?

I am trying to write a parser for a regexp-like matching language using
pyparsing. It can be implemented in terms of operator precedence. I tried
using the operatorPrecedence function, but the performance is unacceptable
for expressions containing nested parentheses.

Parsing time appears to increase exponentially with the number of nested
parentheses, and the parsing time for each set of nested parentheses appears
to increase exponentially with the number of operators in the grammar.

Even parsing something as simple as "(foo(bar))" with a grammar of 4 binary
and 2 unary operators takes ridiculously long (about 2 minutes).

Is there any way to parse operator-precedence-based grammars using pypasing
that doesn't increase exponentially in run time with the number of nested
parentheses?

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project, along
with a healthy diet, reduces your potential for chronic lameness and
boredom. Vote Now at http://www.sourceforge.net/community/cca08
_______________________________________________
Pyparsing-users mailing list
Pyparsing-users@...
https://lists.sourceforge.net/lists/listinfo/pyparsing-users

Paul McGuire wrote:
> As Gre7g L already posted, enabling packrat parsing can be a big boost
> (~1000X) to performance when using operatorPrecedence.
> 
> I just uploaded an example of parsing RE's
> (http://pyparsing.wikispaces.com/space/showimage/invRegex.py) that I thought
> was already on the Pyparsing wiki, so I'm sorry for not posting this sooner.
> This particular example is an RE inverter, returning a generator of all
> strings that would match the given RE (note: does not allow arbitrary
> repetition operators such as '*' or '+', otherwise it would just blow up),
> but it also uses opPrec.  Parsing "(foo(bar))" takes about 1/4 of a second -
> still a long time, but I hope not ridiculously so.  Maybe this example might
> shed some light on some alternative approaches to this problem.
> 
That is what I used as a base for my parser (it needed a lot of 
modifcation, since this matching language is more like a hybrid of globs 
and regexps). It was already on the wiki.

Using a newer version of Python fixes the problem. I had actually tried 
enabled packrat parsing before, and it didn't seem to do anything. There 
seems to be some kind of bug that causes packrat parsing to break on 
Python 2.3 (it actually takes longer if it is enabled on 2.3). 2.4 and 
later don't seem to be affected.