parsing arithmetic expressions with log, exp

  • Anonymous - 2012-06-19

    I have wrote the following piece of code to parse arithmetic expressions containing logarithms and exponentials like;

        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
    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 
    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.


Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.

No, thanks