parsing arithmetic expressions with log, exp

Anonymous
2012-06-19
2013-05-14
  • 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.

     

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