## [Pyparsing] Algorithmic complexity of operatorPrecedence

 [Pyparsing] Algorithmic complexity of operatorPrecedence From: Stefan - 2007-09-07 07:45:06 ```Hi! I am currently trying to use pyparsing to parse a huge number of rather simple expressions. I use the operatorPrecedence functionality because it allows to describe the grammar in a simple and effective way. However, I found the the performance is very low, because some parse actions are called very often for the same object and I have no idea if it is possible to prevent this. The following example based on the simpleArith example illustrates the problem: from pyparsing import * def evaluate_int(t): value = int(t[0]) print "evaluate_int", value return value integer = Word(nums).setParseAction(evaluate_int) variable = Word(alphas,exact=1) operand = integer | variable expop = Literal('^') signop = oneOf('+ -') multop = oneOf('* /') plusop = oneOf('+ -') factop = Literal('!') expr = operatorPrecedence( operand, [ ("!", 1, opAssoc.LEFT), ("^", 2, opAssoc.RIGHT), (signop, 1, opAssoc.RIGHT), (multop, 2, opAssoc.LEFT), (plusop, 2, opAssoc.LEFT), ]) test = ["9"] for t in test: print "%s => %s" % (t, expr.parseString(t)) The evaluate_int function is executed 16 times. When I add another operator, it is executed 32 times. With one more operator it is executed 64 times and so on... It seems that pyparsing tries all possibilities. Is there a way to reduce this algorithmic complexity? Or must I use a different strategy? Would a parser based on the SimpleCalc.py example work better? Stefan. ```

 [Pyparsing] Algorithmic complexity of operatorPrecedence From: Stefan - 2007-09-07 07:45:06 ```Hi! I am currently trying to use pyparsing to parse a huge number of rather simple expressions. I use the operatorPrecedence functionality because it allows to describe the grammar in a simple and effective way. However, I found the the performance is very low, because some parse actions are called very often for the same object and I have no idea if it is possible to prevent this. The following example based on the simpleArith example illustrates the problem: from pyparsing import * def evaluate_int(t): value = int(t[0]) print "evaluate_int", value return value integer = Word(nums).setParseAction(evaluate_int) variable = Word(alphas,exact=1) operand = integer | variable expop = Literal('^') signop = oneOf('+ -') multop = oneOf('* /') plusop = oneOf('+ -') factop = Literal('!') expr = operatorPrecedence( operand, [ ("!", 1, opAssoc.LEFT), ("^", 2, opAssoc.RIGHT), (signop, 1, opAssoc.RIGHT), (multop, 2, opAssoc.LEFT), (plusop, 2, opAssoc.LEFT), ]) test = ["9"] for t in test: print "%s => %s" % (t, expr.parseString(t)) The evaluate_int function is executed 16 times. When I add another operator, it is executed 32 times. With one more operator it is executed 64 times and so on... It seems that pyparsing tries all possibilities. Is there a way to reduce this algorithmic complexity? Or must I use a different strategy? Would a parser based on the SimpleCalc.py example work better? Stefan. ```
 Re: [Pyparsing] Algorithmic complexity of operatorPrecedence From: Paul McGuire - 2007-09-07 12:07:23 ```Stefan - Thanks for doing this analysis on operatorPrecedence! I'll look into it over the weekend and see what I can dig up. It definitely looks like an opportunity for some performance enhancement. -- Paul=20 -----Original Message----- From: pyparsing-users-bounces@... [mailto:pyparsing-users-bounces@...] On Behalf Of = Stefan Reich=F6r Sent: Friday, September 07, 2007 2:39 AM To: pyparsing-users@... Subject: [Pyparsing] Algorithmic complexity of operatorPrecedence Hi! I am currently trying to use pyparsing to parse a huge number of rather simple expressions. I use the operatorPrecedence functionality because = it allows to describe the grammar in a simple and effective way. However, I found the the performance is very low, because some parse = actions are called very often for the same object and I have no idea if it is possible to prevent this. The following example based on the simpleArith example illustrates the problem: from pyparsing import * def evaluate_int(t): value =3D int(t[0]) print "evaluate_int", value return value integer =3D Word(nums).setParseAction(evaluate_int) variable =3D Word(alphas,exact=3D1) operand =3D integer | variable expop =3D Literal('^') signop =3D oneOf('+ -') multop =3D oneOf('* /') plusop =3D oneOf('+ -') factop =3D Literal('!') expr =3D operatorPrecedence( operand, [ ("!", 1, opAssoc.LEFT), ("^", 2, opAssoc.RIGHT), (signop, 1, opAssoc.RIGHT), (multop, 2, opAssoc.LEFT), (plusop, 2, opAssoc.LEFT), ]) test =3D ["9"] for t in test: print "%s =3D> %s" % (t, expr.parseString(t)) The evaluate_int function is executed 16 times. When I add another operator, it is executed 32 times. With one more operator it is executed 64 times and so on... It seems that pyparsing tries all possibilities. Is there a way to reduce this algorithmic complexity? Or must I use a different strategy? Would a parser based on the SimpleCalc.py example work better? Stefan. -------------------------------------------------------------------------= This SF.net email is sponsored by: Splunk Inc. Still grepping through log files to find problems? Stop. Now Search log events and configuration files using AJAX and a browser. Download your FREE copy of Splunk now >> http://get.splunk.com/ _______________________________________________ Pyparsing-users mailing list Pyparsing-users@... https://lists.sourceforge.net/lists/listinfo/pyparsing-users ```