Understanding Boolean Expressions

[Terry Jan Reedy]

[2nd try, quotation a bit messed up]

On 4/16/2013 6:19 PM, Bruce McGoveran wrote:

 > Hello.  I am new to this group.  I've done a search for the topic
 > about which I'm posting, and while I have found some threads that are
 > relevant, I haven't found anything exactly on point that I can
 > understand.  So, I'm taking the liberty of asking about something
 > that may be obvious to many readers of this group.

 > The relevant Python documentation reference is:
 > http://docs.python.org/2/reference/expressions.html#boolean-operations.

 > I'm trying to make sense of the rules of or_test, and_test, and
 > not_test that appear in this section.  While I understand the
 > substance of the text in this section,


The substance is that 1) 'not' binds tighter than 'and' binds tigher 
than 'or' and 2) 'and' and 'or' both associate left to right in the 
normal manner so that 'a op b op c' == '(a op b) op c'.

 > it is the grammar definitions themselves that confuse me.

The techinical details reflect the fact that Python's grammar is ll(1) 
(top-down, parsed by recursive descent) rather than lr(1) (bottom-up). 
The latter (in lalr(1) form) is what yacc, etc use and might be more 
familiar to you.

 > For example, I am not clear how an or_test can be an and_test.

or_test  ::=  and_test | or_test "or" and_test

The second option expresses the associativity rule, but more is needed 
to get out of infinite regress. Substituting the second rule into second 
rule gives

or_test = (or_test 'or' and_test) 'or' and_test

and so on. At some point, one must replace or_test with and_test to get 
an 'or' of ands. Similarly, an and_test must resolve to an 'and' of nots.

 > Moreover, if I follow the chain of non-terminal references, I move
 > from or_test, to and_test, to nt_test, to comparison.  And when I
 > look at the definition for comparison, I seem to be into bitwise
 > comparisons.  I cannot explain this.

Eventually the chain takes one to primaries, which include things like 
literals and identifiers.

 > Perhaps an example will help put my confusion into more concrete 
terms.  Suppose I write the expression if x or y in my code.  I 
presume this is an example of an or_test.

Yes.

 > Beyond that, though, I'm  not sure whether this maps to an and_test 
(the first option on the  right-hand side of the rule) or to the or_test 
"or" and_test option (the second on the right-hand side of the rule).

The second. Then the or_test on the left also maps to an and_test. Each 
and_test eventually resolves to 'identifier', specifically 'x' and 'y'.

     --
     Terry Jan Reedy