pyparsing-users

[Pyparsing] Logical operations

[happybrowndog <hap...@ho...>]

Hello...
first of all, thanks for your help in my last post on "Function 
parameters that may have brackets" - I solved the problem by going 
through the code samples as you stated and the problem is solved now.

Now I am having problems with parsing logical operations.

I have an expression:
calcexpr = operatorPrecedence( w_operand,[(op_sign, 1, 
opAssoc.RIGHT),(op_mult, 2, opAssoc.LEFT),(op_div, 2, 
opAssoc.LEFT),(op_plus, 2, opAssoc.LEFT),(op_minus, 2, opAssoc.LEFT),])

which parses the following correctly: "(3+6)/5".

then I have:
boolexpr = Forward()
boolexpr << calcexpr + ("=" ^ ">" ^ "<") + calcexpr + Optional(("AND" ^ 
"OR") + boolexpr)

boolexpr then parses the following correctly: "(3+6)/5 > 1 AND 2 < 9"

but returns an error on the following: "((3+6)/5 > 1) AND (2 < 9)"

ultimately, I would like to be able to parse a statement such as:
"((3+6)/5 > 1) AND ( (2 < 9) OR ( (2+5/12 < 1) AND ( 3 < 4) ) )"

but of course this would also fail.

To try to get to my goal, I try adding Optional("(") and Optional(")") 
to boolexpr, such as:

boolexpr << Optional("(") + calcexpr +  ("=" ^ ">" ^ "<") + calcexpr + 
Optional(")") + Optional(("AND" ^ "OR") + boolexpr)

but this does not resolve the problem.  The brackets are screwing things 
up.  I think the cause may be related to the same reason I was having 
problems previously, but I can't seem to link the two.

Can you please point me in the right direction?

Re: [Pyparsing] Logical operations

[Eike W. <ei...@us...>]

On Tuesday 03 June 2008 09:34, happybrowndog wrote:
> Hello...
> first of all, thanks for your help in my last post on "Function
> parameters that may have brackets" - I solved the problem by going
> through the code samples as you stated and the problem is solved
> now.
>
> Now I am having problems with parsing logical operations.
>
> I have an expression:
> calcexpr = operatorPrecedence( w_operand,[(op_sign, 1,
> opAssoc.RIGHT),(op_mult, 2, opAssoc.LEFT),(op_div, 2,
> opAssoc.LEFT),(op_plus, 2, opAssoc.LEFT),(op_minus, 2,
> opAssoc.LEFT),])
>
> which parses the following correctly: "(3+6)/5".
>
> then I have:
> boolexpr = Forward()
> boolexpr << calcexpr + ("=" ^ ">" ^ "<") + calcexpr +
> Optional(("AND" ^ "OR") + boolexpr)
>
> boolexpr then parses the following correctly: "(3+6)/5 > 1 AND 2 <
> 9"
>
> but returns an error on the following: "((3+6)/5 > 1) AND (2 < 9)"
>
> ultimately, I would like to be able to parse a statement such as:
> "((3+6)/5 > 1) AND ( (2 < 9) OR ( (2+5/12 < 1) AND ( 3 < 4) ) )"
>
> but of course this would also fail.
>
> To try to get to my goal, I try adding Optional("(") and
> Optional(")") to boolexpr, such as:
>
> boolexpr << Optional("(") + calcexpr +  ("=" ^ ">" ^ "<") +
> calcexpr + Optional(")") + Optional(("AND" ^ "OR") + boolexpr)
>
> but this does not resolve the problem.  The brackets are screwing
> things up.  I think the cause may be related to the same reason I
> was having problems previously, but I can't seem to link the two.
>
> Can you please point me in the right direction?

You should should add the additional operators to operatorPrecedence. 
First define:

op_and = Keyword('AND')
op_or = Keyword('OR')
op_eq = Literal('=')
op_lt = Literal('<')
op_gt = Literal('>')

And then add the following to the call to operatorPrecedence.:

(op_and, 2, opAssoc.LEFT),

(op_or, 2, opAssoc.LEFT),

(op_eq, 2, opAssoc.LEFT),
(op_lt, 2, opAssoc.LEFT),
(op_gt, 2, opAssoc.LEFT),


The "AND" belongs to the same level like multiplication, the 'OR' 
belongs to '+' and the and the comparison operators '= < >' belong to 
the end (IMHO). (Everything completely untested.)

HTH, Eike.

Re: [Pyparsing] Logical operations

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

To begin with, just for readability, I would convert your operatorPrecedence
call to:
    
calcexpr = operatorPrecedence( w_operand,[
    (op_sign, 1, opAssoc.RIGHT),
    (op_mult, 2, opAssoc.LEFT),
    (op_div, 2, opAssoc.LEFT),
    (op_plus, 2, opAssoc.LEFT),
    (op_minus, 2, opAssoc.LEFT),
    ])

Then, since one of the main purposes of opPrec is to manage levels of
precedence of operations, I would combine operators of the same precedence
to the same level:

calcexpr = operatorPrecedence( w_operand,[
    (op_sign, 1, opAssoc.RIGHT),
    (op_mult | op_div, 2, opAssoc.LEFT),
    (op_plus | op_minus, 2, opAssoc.LEFT),
    ])

(There is also value in minimizing the number of levels in a call to opPrec
- performance can get pretty bad if the number of levels gets too deep.)

You can then validate this expression with some asserts, using the new '=='
operator defined in 1.4.11:

assert "(3+6)/5" == calcexpr
assert "((3+6)/5)" == calcexpr

boolexpr is really just another set of operators with precedence:

op_comparison = oneOf("= > < <= >= !=")
comparison = calcexpr + op_comparison + calcexpr
boolexpr = operatorPrecedence( comparison, [
    ("NOT", 1, opAssoc.RIGHT),
    ("AND", 2, opAssoc.LEFT),
    ("OR", 2, opAssoc.LEFT),
    ])

But for this simple a set of operators, you can also do things the
old-fashioned, by-hand way:

boolexpr = Forward()
boolTerm = Optional("NOT") + (comparison | Group("(" + boolexpr + ")"))
boolAnd = boolTerm + ZeroOrMore("AND" + boolTerm)
boolOr = boolAnd + ZeroOrMore("OR" + boolAnd)
boolexpr << ( boolOr )

This also bypasses some of the overhead cruft in opPrec, and so will perform
better.

Check it out:
assert "(3+6)/5 > 1 AND 2 < 9" == boolexpr
assert "((3+6)/5 > 1) AND (2 < 9)" == boolexpr
assert "((3+6)/5 > 1) AND ( (2 < 9) OR ( (2+5/12 < 1) AND ( 3 < 4) ) )" ==
boolexpr

You can see how the precedence of operations automatically groups the
operands, so that higher-order operations get evaluated ahead of lower
order, that is "A AND B OR C" correctly evaluates to "(A AND B) OR C":

def test(s):
    from pprint import pprint
    print s
    try:
        pprint (boolexpr.parseString(s).asList())
    except ParseException, pe:
        print "Exception:", pe.msg
    print
        
test("(3+6)/5 > 1 AND 2 < 9")
test("((3+6)/5 > 1) AND (2 < 9)")
test("((3+6)/5 > 1) AND ( (2 < 9) OR ( (2+5/12 < 1) AND ( 3 < 4) ) )")

prints:

(3+6)/5 > 1 AND 2 < 9
[[['3', '+', '6'], '/', '5'], '>', '1', 'AND', '2', '<', '9']

((3+6)/5 > 1) AND (2 < 9)
[['(', [['3', '+', '6'], '/', '5'], '>', '1', ')'],
 'AND',
 ['(', '2', '<', '9', ')']]

((3+6)/5 > 1) AND ( (2 < 9) OR ( (2+5/12 < 1) AND ( 3 < 4) ) )
[['(', [['3', '+', '6'], '/', '5'], '>', '1', ')'],
 'AND',
 ['(',
  ['(', '2', '<', '9', ')'],
  'OR',
  ['(',
   ['(', ['2', '+', ['5', '/', '12']], '<', '1', ')'],
   'AND',
   ['(', '3', '<', '4', ')'],
   ')'],
  ')']]
  
Lastly, you can do the evaluation of these various terms in parse actions
attached to individual expressions in the grammar:
    
calcexpr.setParseAction(evaluateCalc)
comparison.setParseAction(evaluateComparison)
boolexpr.setParseAction(evaluateBool)

(I'll leave the implementation of these parse actions as an exercise - plus
I'm late for work!)
    
-- Paul

Re: [Pyparsing] Logical operations

[happybrowndog <hap...@ho...>]

Thank you for that.  In fact, I already implemented it in very much the 
same way as you suggested - with levels of operations of the same 
precedence Or'd, and that I did see how higher ordered operations 
preside over lower ordered ones.  However, I did stick with 
operatorPrecedence rather than the "old-fashioned" way as the former is 
much more readable.  It's good that you posted what you did, as it now 
confirms that my understanding is (near) correct.

 > You can then validate this expression with some asserts, using the 
new '=='
 > operator defined in 1.4.11:
 >
 > assert "(3+6)/5" == calcexpr
 > assert "((3+6)/5)" == calcexpr

This is a very useful technique.  Thanks for pointing that out.

By the way, your library is a God-send.  Thank you and very very much 
appreciated.  There's a helluva lot of problems we can solve very neatly 
with this at our company.


Paul McGuire wrote:
> To begin with, just for readability, I would convert your operatorPrecedence
> call to:
>     
> calcexpr = operatorPrecedence( w_operand,[
>     (op_sign, 1, opAssoc.RIGHT),
>     (op_mult, 2, opAssoc.LEFT),
>     (op_div, 2, opAssoc.LEFT),
>     (op_plus, 2, opAssoc.LEFT),
>     (op_minus, 2, opAssoc.LEFT),
>     ])
> 
> Then, since one of the main purposes of opPrec is to manage levels of
> precedence of operations, I would combine operators of the same precedence
> to the same level:
> 
> calcexpr = operatorPrecedence( w_operand,[
>     (op_sign, 1, opAssoc.RIGHT),
>     (op_mult | op_div, 2, opAssoc.LEFT),
>     (op_plus | op_minus, 2, opAssoc.LEFT),
>     ])
> 
> (There is also value in minimizing the number of levels in a call to opPrec
> - performance can get pretty bad if the number of levels gets too deep.)
> 
> You can then validate this expression with some asserts, using the new '=='
> operator defined in 1.4.11:
> 
> assert "(3+6)/5" == calcexpr
> assert "((3+6)/5)" == calcexpr
> 
> boolexpr is really just another set of operators with precedence:
> 
> op_comparison = oneOf("= > < <= >= !=")
> comparison = calcexpr + op_comparison + calcexpr
> boolexpr = operatorPrecedence( comparison, [
>     ("NOT", 1, opAssoc.RIGHT),
>     ("AND", 2, opAssoc.LEFT),
>     ("OR", 2, opAssoc.LEFT),
>     ])
> 
> But for this simple a set of operators, you can also do things the
> old-fashioned, by-hand way:
> 
> boolexpr = Forward()
> boolTerm = Optional("NOT") + (comparison | Group("(" + boolexpr + ")"))
> boolAnd = boolTerm + ZeroOrMore("AND" + boolTerm)
> boolOr = boolAnd + ZeroOrMore("OR" + boolAnd)
> boolexpr << ( boolOr )
> 
> This also bypasses some of the overhead cruft in opPrec, and so will perform
> better.
> 
> Check it out:
> assert "(3+6)/5 > 1 AND 2 < 9" == boolexpr
> assert "((3+6)/5 > 1) AND (2 < 9)" == boolexpr
> assert "((3+6)/5 > 1) AND ( (2 < 9) OR ( (2+5/12 < 1) AND ( 3 < 4) ) )" ==
> boolexpr
> 
> You can see how the precedence of operations automatically groups the
> operands, so that higher-order operations get evaluated ahead of lower
> order, that is "A AND B OR C" correctly evaluates to "(A AND B) OR C":
> 
> def test(s):
>     from pprint import pprint
>     print s
>     try:
>         pprint (boolexpr.parseString(s).asList())
>     except ParseException, pe:
>         print "Exception:", pe.msg
>     print
>         
> test("(3+6)/5 > 1 AND 2 < 9")
> test("((3+6)/5 > 1) AND (2 < 9)")
> test("((3+6)/5 > 1) AND ( (2 < 9) OR ( (2+5/12 < 1) AND ( 3 < 4) ) )")
> 
> prints:
> 
> (3+6)/5 > 1 AND 2 < 9
> [[['3', '+', '6'], '/', '5'], '>', '1', 'AND', '2', '<', '9']
> 
> ((3+6)/5 > 1) AND (2 < 9)
> [['(', [['3', '+', '6'], '/', '5'], '>', '1', ')'],
>  'AND',
>  ['(', '2', '<', '9', ')']]
> 
> ((3+6)/5 > 1) AND ( (2 < 9) OR ( (2+5/12 < 1) AND ( 3 < 4) ) )
> [['(', [['3', '+', '6'], '/', '5'], '>', '1', ')'],
>  'AND',
>  ['(',
>   ['(', '2', '<', '9', ')'],
>   'OR',
>   ['(',
>    ['(', ['2', '+', ['5', '/', '12']], '<', '1', ')'],
>    'AND',
>    ['(', '3', '<', '4', ')'],
>    ')'],
>   ')']]
>   
> Lastly, you can do the evaluation of these various terms in parse actions
> attached to individual expressions in the grammar:
>     
> calcexpr.setParseAction(evaluateCalc)
> comparison.setParseAction(evaluateComparison)
> boolexpr.setParseAction(evaluateBool)
> 
> (I'll leave the implementation of these parse actions as an exercise - plus
> I'm late for work!)
>     
> -- Paul
> 
> 
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/