Understanding Boolean Expressions

[Bruce McGoveran]

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 readersof 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 inthis section, it is the grammar definitions themselves that confuse me. For example, I am not clear how an or_test can be an and_test. Moreover, ifI follow the chain of non-terminal references, I move from or_test, to and_test, to not_test, to comparison. And when I look at the definition for comparison, I seem to be into bitwise comparisons. I cannot explain this.

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

If people can offer some thoughts to put me in the right direction (or out of my misery), I would appreciate it.

Thank you in advance.

 

[Dave Angel]

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, it is the grammar definitions themselves that confuse me. For example, I am not clear how an or_test can be an and_test. Moreover, if I follow the chain of non-terminal references, I move from or_test, to and_test, to not_test, to comparison. And when I look at the definition for comparison, I seem to be into bitwise comparisons. I cannot explain this.

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

If people can offer some thoughts to put me in the right direction (or out of my misery), I would appreciate it.

It's been decades since I really had to understand a complete grammar.
But in some ways, a fragment like you're referencing is even harder. The
trick is to take those names "and_test" as rather arbitrary. There's no
token meaning "an expression containing 4 or's, 2 and's, and 1 not" So
sometimes the terms used are rather silly looking.

The point is you can combine 'not', 'and', 'or', and comparison
operators like ==, >= etc. in some complex ways. The grammar just
says which of these is legal, and doesn't help you figure out the
semantics, which is usually much more important to you and me.

First, nearly all objects have a 'truth' value, for which I use the
terms 'true' and 'false'. For numbers, nonzero values are true, and
zero values are false. For collections, nonempty collections are true
and empty ones are false. And so on. So if x is an int, and if you say:
if x:

You're checking the 'truth' of x, and it'll execute the if clause for
nonzero integers, for example.

If you have an arbitrary object 'x', it is not necessarily of type bool.
But if you compare it to another one, x==y the result is a bool,
either True or False. Likewise if you apply the unary 'not' to an
object; the result will be either True or False.

But if you combine two expressions with 'or' the result is NOT
necessarily of type bool. If the first expression is true, then the
second expression isn't even examined. If the first expression is
false, the second expression is the result.

'and' has the reverse meaning. And more complex expressions can be
understood by breaking them into steps, according to operator precedence
and parentheses.

 

[Terry Jan Reedy]

[2nd try, quotation a bit messed up]

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

 

[Bruce McGoveran]

Thank you all for thoughts. I'm just about to post another question about atoms and primaries. If you have a moment to look it over, I would appreciate your thoughts.

Many thanks in advance.

 

[Steven D'Aprano]

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, it is the grammar definitions themselves that
confuse me. For example, I am not clear how an or_test can be an
and_test.

In this case, you could have saved us some time by copying and pasting
the relevant three lines:

or_test ::= and_test | or_test "or" and_test
and_test ::= not_test | and_test "and" not_test
not_test ::= comparison | "not" not_test


I agree that this is not entirely the most obvious wording, but it makes
a sort of sense if you follow it through carefully. Unfortunately, to
really understand the grammar, you have to follow through the entire
thing. But translated into English, the above three rules might read like
this:

An expression which we call an or_test can be either:

1) an and_test; or

2) another or_test, followed by the literal string "or", followed by an
and_test.

An expression which we call an and_test can be either:

3) a not_test; or

4) another and_test, followed by the literal string "and", followed by
another not_test.

An expression which we call a not_test can be either:

5) a comparison; or

6) the literal string "not", followed by another not_test.

An expression which we call a comparison can be:

.... a bunch more different alternatives, going through bitwise
comparisons, then arithmetic operators, then other expressions, and so
on, until finally you reach the simplest expressions possible, names and
constant literals.

So in a sense, an "or_test" does not JUST mean it's a test with an "or"
in it. The thing called an or_test is an and_test *or* a test with an
"or" in it; an and_test is a not_test *or* a test with an "and" in it; a
not_test is a comparison *or* a test with a "not" in it; a comparison
is ... and so forth, until you run out of expressions and end up with a
simple atom like a name or a constant.

So paradoxically, that means that "x or y" counts as an and_test
(obviously!) but also as an or_test, since every and_test also counts as
an or_test. Here's some crappy ASCII art of a Venn diagram with a couple
of examples shown: (best viewed in a fixed-width font):


+---------------------------------+
| or_tests |
| "x or y" |
| +----------------------+ |
| | and_tests | |
| | "x and y" | |
| | +-------------+ | |
| | | not_tests | | |
| | | | | |
| | | "not x" | | |
| | +-------------+ | |
| +----------------------+ |
+---------------------------------+


Inside the "not_test" box, not shown, are other boxes relating to other
expressions, and ending deep down with boxes labelled "names" and
"literals". (Or so I expect, since I haven't followed the maze of twisty
grammar rules, all alike, to the very end.)


Of course, in practice we wouldn't normally call an expression such as
"x and y" as an or_test, even though strictly speaking the grammar says
it is. We would call it by the smallest box it is contained within,
namely "and_test".

An analogy: normally, we would refer to Python's creator Guido van Rossum
as a "man", not a "mammal", but since all men are mammals, it wouldn't be
wrong to call him such. But not all mammals are men, and not all or_tests
are and_tests. "x or y" is an or_test, obviously, but not an and_test.

Does this help explain it?

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

"x or y" maps to the second option. The "x" matches and_test, which then
matches not_test, which then matches comparison, which ... blah blah
blah ... which finally matches a plain name. The "or" matches the literal
string "or" in the grammar rule. Then the "y" matches and_test, which ...
finally matches a plain name.

Of course, this is NOT necessarily what Python does every time it parses
a piece of code! It's just a description of the grammar.

 

[Jussi Piitulainen]

So paradoxically, that means that "x or y" counts as an and_test
(obviously!) but also as an or_test, since every and_test also
counts as an or_test. Here's some crappy ASCII art of a Venn diagram

I think you mean to say that "x and y" counts as an and_test and also
as an or_test.

 

[Steven D'Aprano]

I think you mean to say that "x and y" counts as an and_test and also as
an or_test.

You may very well be right, but I'll be damned if I go back and read
through my post trying to work out what I intended to say instead of what
I actually said!





And-or-or-and-or-or-or-and-and-or-ly y'rs,

 

[Jussi Piitulainen]

You may very well be right, but I'll be damned if I go back and read
through my post trying to work out what I intended to say instead of what
I actually said!

The quote above is sufficient context for one who knows that "x or y"
is not an and_test. I'm hoping that pointing this little thing out
will help some potentially confused reader of your otherwise excellent
explanation see more quickly that this is really just a harmless typo.
(Unless it's me who's confused

The quote appeared just before your ASCII art.