parsing arithmetic expressions with log, exp

[Anonymous]

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]

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.