Re: [Pyparsing] parsing an operator-precedence-based grammar withreasonable performance?

[Paul M. <pt...@au...>]

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: pyp...@li...
[mailto:pyp...@li...] On Behalf Of Andrew
Warkentin
Sent: Friday, July 04, 2008 10:43 PM
To: pyp...@li...
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
Pyp...@li...
https://lists.sourceforge.net/lists/listinfo/pyparsing-users