Anonymous
2012-06-19
I have wrote the following piece of code to parse arithmetic expressions containing logarithms and exponentials like;
(log2(exp10(x)+log10(x)-y)/expe(y)^(log2(exp10(x)+log10(x)-y)/expe(y)))^log2(exp10(x)+log10(x)-y)/expe(y)^(log2(exp10(x)+log10(x)-y)/expe(z)) log(x+exp(y)/z)*x+4 log(x)+log(y)/exp(z) log(log(exp(x)))/exp(log(x)) x+y-z x+log(y)-exp(z) x+y-log(z) arith_expr = pp.Forward() powop = pp.oneOf("^") divop = pp.oneOf("/ * %") addop = pp.oneOf("+ -") exp_funcs = (pp.Keyword("log10") | pp.Keyword("loge") | pp.Keyword("log") | pp.Keyword("log2") | pp.Keyword("exp10") | pp.Keyword("exp") | pp.Keyword("expe") | pp.Keyword("exp2")) operand = Common.indexed_field | Common.fnumber func_atom = operand ^ (exp_funcs + "(" + arith_expr + ")") comp_expr = pp.operatorPrecedence(func_atom, [ (powop, 2, pp.opAssoc.LEFT), (divop, 2, pp.opAssoc.LEFT), (addop, 2, pp.opAssoc.LEFT)]) arith_expr << comp_expr return arith_expr
but the grammar validation time is substantially large and as the arithmetic expression grows in size, time to parse the expression also grows exponentially. Any help would be appreciated. :)
Anonymous
2012-06-19
I think the situation is described http://en.wikipedia.org/wiki/Parsing_expression_grammar#Implementing_parsers_from_parsing_expression_grammars.
I wasn't sure how you had defined Common, so I made mine simply match any letter or number, which is enough for the examples you gave.
operand = pp.oneOf([i for i in pp.alphanums]) # Common.indexed_field | Common.fnumber
I confirmed the dramatic increase in processing time.
The Wikipedia article says that using a packrat parser can trade time for space, and pyparsing does support packrat parsing. I haven't experimented with it much, so I just added "arith_expr.enablePackrat()" to the end.
arith_expr << comp_expr arith_expr.enablePackrat() return arith_expr
Unfortunately, when I tried arith_expr.parseString("x+y+z") or even something simpler, after enabling packrat parsing, it raised an exception with about a 500 line traceback.
I'm sorry that doesn't help you, and doesn't give any insight into the reason pyparsing crashed with packrat enabled.