Re: [Pyparsing] Getting "maximum recursion depth exceeded" when using Forward

[Paul M. <pt...@au...>]

There is a standard approach to parsing this kind of expression, called
"infix notation", which will take into account the precedence of operations
so that the final evaluation will be performed properly. In your simplified
case, you have two operations, AND and OR - by mathematical convention, OR
has higher precedence than AND. So if I wanted to evaluate:
    
    color = RED and size = XXL or cost > $50

This would be equivalent to:

    color = RED and (size = XXL or cost > $50)

And so we would want our parser to return a nested structure that helps us
evaluate these expressions properly.

The standard recursive approach to defining an infix notation parser follows
the pattern (where all operators are left-associative):

    level1term = level2term [ level1op level2term ]...
    level2term = level3term [ level2op level3term ]...
    level3term = level4term [ level3op level4term ]...
    ...
    levelNterm = simplest_operand | '(' level1term ')'

For 4-function arithmetic, where multiplication and division take precedence
over addition and subtraction, this looks like (using the arithmetic names
'term' and 'factor' that we all learned in high school algebra):

    expr = term [ ('+' or '-') term ]...
    term = factor [ ('*' or '/') factor ]...
    factor = numeric_value | variable_name | '(' expr ')'
    
and with these 3 lines, you can parse "4*a + 5*b + c - d/10", and get a
resulting structure where all the operators respect their proper
precedences.

(I think it was the elegance of this algorithm which first sparked my
interest in parsers, over 30 years ago.)

There is a nice wikipedia page that covers this too:
https://en.wikipedia.org/wiki/Operator-precedence_parser.

So here is your application implemented following this pattern, using
pyparsing:

    from pyparsing import *
    """
    BNF:

    bool_expr = and_term
    and_term = or_term [AND or_term]...
    or_term = operand [OR operand]...
    operand = boolcomparison | '(' bool_expr ')'
    boolcomparison = ('env' | 'name') '=' rvalue
    rvalue = word composed of alpha chars
    """

    AND,OR = map(CaselessKeyword, "AND OR".split())
    LPAR,RPAR = map(Suppress,'()')
    key = oneOf(['env', 'name'])
    val = Word(alphas)
    keyEqVal = key + '=' + val
    keyEqVal = key + oneOf('= < > != >= <=') + val
    boolcomparison = Group(keyEqVal)

    # implement BNF, bottom-up
    boolExpr = Forward()
    operand = boolcomparison | LPAR + boolExpr + RPAR
    or_term = Group(operand + ZeroOrMore(OR + operand))
    and_term = Group(or_term + ZeroOrMore(AND + or_term))
    boolExpr << and_term

    # enclosed = Forward()
    # nestedParens = nestedExpr('(', ')', content=enclosed) 
    # boolExpr = enclosed + oneOf(["and", "or"]) + enclosed 
    # enclosed << (boolExpr | nestedParens | keyEqVal)

    data = 'env=prod'
    # OR should take precedence over AND
    data = 'name=Bob and env=test or env=prototype'
    print boolExpr.parseString(data)


The result is:

    [[[['name', '=', 'Bob']], 'AND', [['env', '=', 'test'], 'OR', ['env',
'=', 'prototype']]]]
    
Note that the grouping will case the OR to be evaluated before the AND.

The common occurrence of these kinds of expressions led me to write the
'operatorPrecedence' parser helper, now renamed to 'infixNotation'.
Converting this sample to use 'infixNotation' is left as an exercise.

HTH,
-- Paul


-----Original Message-----
From: mayamatakeshi [mailto:may...@gm...] 
Sent: Tuesday, September 01, 2015 10:06 PM
To: pyp...@li...
Subject: [Pyparsing] Getting "maximum recursion depth exceeded" when using
Forward

Hello, I am getting "maximum recursion depth exceeded" with the below:

#####################################
from pyparsing import *

key = oneOf(['env', 'name'])
val = Word(alphas)
keyEqVal = key + '=' + val
enclosed = Forward()
nestedParens = nestedExpr('(', ')', content=enclosed) boolExpr = enclosed +
oneOf(["and", "or"]) + enclosed enclosed << (boolExpr | nestedParens |
keyEqVal)

data = 'e=prod'
print enclosed.parseString(data)
#####################################

I know it is due my definition of boolExpr, but I could not figure out how
to correct it.

R,
Takeshi



---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus