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

Brought to you by: ptmcg

pyparsing-users

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

From: mayamatakeshi <may...@gm...> - 2015-09-02 03:06:25

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

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

From: Paul M. <pt...@au...> - 2015-09-02 04:22:02

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

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

From: mayamatakeshi <may...@gm...> - 2015-09-02 04:48:20

Paul,
it was exactly what I wanted to achieve!
Thanks a lot.
R,
Takeshi

On Wed, Sep 2, 2015 at 1:22 PM, Paul McGuire <pt...@au...> wrote:

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

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

From: Paul M. <pt...@au...> - 2015-09-02 07:58:44

Sorry, I'm always getting these backwards if I don't look them up!

AND takes precedence over OR. I had this backwards.  The bool_expr part of
the program should be:

    boolExpr = Forward()
    operand = boolcomparison | LPAR + boolExpr + RPAR
    and_term = Group(operand + ZeroOrMore(AND + operand))
    or_term = Group(and_term + ZeroOrMore(OR + and_term))
    boolExpr << or_term

I'll add in NOT processing for you (NOT is highest precedence):

    NOT,AND,OR = map(CaselessKeyword, "NOT AND OR".split())

And change:

    operand = boolcomparison | LPAR + boolExpr + RPAR

to:

    operand = Optional(NOT) + (boolcomparison | LPAR + boolExpr + RPAR)

Sorry for the confusion!

-- Paul


-----Original Message-----
From: mayamatakeshi [mailto:may...@gm...] 
Sent: Tuesday, September 01, 2015 11:48 PM
To: Paul McGuire <pt...@au...>
Cc: pyp...@li...
Subject: Re: [Pyparsing] Getting "maximum recursion depth exceeded" when
using Forward

Paul,
it was exactly what I wanted to achieve!
Thanks a lot.
R,
Takeshi


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

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

From: mayamatakeshi <may...@gm...> - 2015-09-02 08:11:32

Thanks Paul.
I have just corrected my script.
R,
Takeshi.

On Wed, Sep 2, 2015 at 4:58 PM, Paul McGuire <pt...@au...> wrote:

> Sorry, I'm always getting these backwards if I don't look them up!
>
> AND takes precedence over OR. I had this backwards.  The bool_expr part of
> the program should be:
>
>     boolExpr = Forward()
>     operand = boolcomparison | LPAR + boolExpr + RPAR
>     and_term = Group(operand + ZeroOrMore(AND + operand))
>     or_term = Group(and_term + ZeroOrMore(OR + and_term))
>     boolExpr << or_term
>
> I'll add in NOT processing for you (NOT is highest precedence):
>
>     NOT,AND,OR = map(CaselessKeyword, "NOT AND OR".split())
>
> And change:
>
>     operand = boolcomparison | LPAR + boolExpr + RPAR
>
> to:
>
>     operand = Optional(NOT) + (boolcomparison | LPAR + boolExpr + RPAR)
>
> Sorry for the confusion!
>
> -- Paul
>
>
> -----Original Message-----
> From: mayamatakeshi [mailto:may...@gm...]
> Sent: Tuesday, September 01, 2015 11:48 PM
> To: Paul McGuire <pt...@au...>
> Cc: pyp...@li...
> Subject: Re: [Pyparsing] Getting "maximum recursion depth exceeded" when
> using Forward
>
> Paul,
> it was exactly what I wanted to achieve!
> Thanks a lot.
> R,
> Takeshi
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
>