16.6. Boolean “AND

With that bit of philosophy out of the way, we can press on to the “and” operator, which goes into procedure Term. By now, you can probably do this without me, but here's the code, anyway:

In Scanner,

function IsMulop(c: char): boolean;
begin
        IsMulop := c in ['*','/', '&'];
end;

In Parser,

procedure Term;
begin
        Factor;
        while IsMulop(Look) do
                case Look of
                        '*': Multiply;
                        '/': Divide;
                        '&': _And;
                end;
end;

{ Parse and Translate a Boolean And Operation }
procedure _And;
begin
        Match('&');
        Push;
        Factor;
        PopAnd;
end;

and in CodeGen,

{ And Primary with TOS }
procedure PopAnd;
begin
        EmitLn('AND (SP)+,D0');
end;

Your parser should now be able to process almost any sort of logical expression, and (should you be so inclined), mixed-mode expressions as well.

Why not “all sorts of logical expressions”? Because, so far, we haven't dealt with the logical “not” operator, and this is where it gets tricky. The logical “not” operator seems, at first glance, to be identical in its behavior to the unary minus, so my first thought was to let the exclusive or operator, '~', double as the unary “not.” That didn't work. In my first attempt, procedure SignedTerm simply ate my '~', because the character passed the test for an addop, but SignedTerm ignores all addops except '-'. It would have been easy enough to add another line to SignedTerm, but that would still not solve the problem, because note that Expression only accepts a signed term for the first argument.

Mathematically, an expression like:

-a * -b

makes little or no sense, and the parser should flag it as an error. But the same expression, using a logical “not,” makes perfect sense:

not a and not b

In the case of these unary operators, choosing to make them act the same way seems an artificial force fit, sacrificing reasonable behavior on the altar of implementational ease. While I'm all for keeping the implementation as simple as possible, I don't think we should do so at the expense of reasonableness. Patching like this would be missing the main point, which is that the logical “not” is simply not the same kind of animal as the unary minus. Consider the exclusive or, which is most naturally written as:

a~b ::= (a and not b) or (not a and b)

If we allow the “not” to modify the whole term, the last term in parentheses would be interpreted as:

not(a and b)

which is not the same thing at all. So it's clear that the logical “not” must be thought of as connected to the factor, not the term.

The idea of overloading the '~' operator also makes no sense from a mathematical point of view. The implication of the unary minus is that it's equivalent to a subtraction from zero:

-x <=> 0-x

In fact, in one of my more simple-minded versions of Expression, I reacted to a leading addop by simply preloading a zero, then processing the operator as though it were a binary operator. But a “not” is not equivalent to an exclusive or with zero ... that would just give back the original number. Instead, it's an exclusive or with FFFFh, or -1.

In short, the seeming parallel between the unary “not” and the unary minus falls apart under closer scrutiny. “not” modifies the factor, not the term, and it is not related to either the unary minus nor the exclusive or. Therefore, it deserves a symbol to call its own. What better symbol than the obvious one, also used by C, the '!' character? Using the rules about the way we think the “not” should behave, we should be able to code the exclusive or (assuming we'd ever need to), in the very natural form:

a & !b | !a & b

Note that no parentheses are required — the precedence levels we've chosen automatically take care of things.

If you're keeping score on the precedence levels, this definition puts the '!' at the top of the heap. The levels become:

  1. !
  2. - (unary)
  3. *, /, &
  4. +, -, |, ~

Looking at this list, it's certainly not hard to see why we had trouble using '~' as the “not” symbol!

So how do we mechanize the rules? In the same way as we did with SignedTerm, but at the factor level. We'll define a procedure NotFactor:

{ Parse and Translate a Factor with Optional "Not" }
procedure NotFactor;
begin
        if Look ='!' then begin
                Match('!');
                Factor;
                Notit;
                end
        else
                Factor;
end;

and call it from all the places where we formerly called Factor, i.e., from Term, Multiply, Divide, and _And. Note the new code generation procedure:

{ Bitwise Not Primary }
procedure NotIt;
begin
        EmitLn('EOR #-1,D0');
end;

Try this now, with a few simple cases. In fact, try that exclusive or example,

a&!b|!a&b

You should get the code (without the comments, of course):

        MOVE A(PC),DO           ; load a 
        MOVE D0,-(SP)           ; push it 
        MOVE B(PC),DO           ; load b 
        EOR #-1,D0              ; not it 
        AND (SP)+,D0            ; and with a 
        MOVE D0,-(SP)           ; push result 
        MOVE A(PC),DO           ; load a 
        EOR #-1,D0              ; not it 
        MOVE D0,-(SP)           ; push it 
        MOVE B(PC),DO           ; load b 
        AND (SP)+,D0            ; and with !a 
        OR (SP)+,D0             ; or with first term

That's precisely what we'd like to get. So, at least for both arithmetic and logical operators, our new precedence and new, slimmer syntax hang together. Even the peculiar, but legal, expression with leading addop:

~x

makes sense. SignedTerm ignores the leading '~', as it should, since the expression is equivalent to:

0~x

which is equal to x.

When we look at the BNF we've created, we find that our boolean algebra now adds only one extra line:

<not_factor>    ::= [!] <factor>
<factor>        ::= <variable> | <constant> | '(' <expression> ')'
<signed_term>   ::= [<addop>] <term>
<term>          ::= <not_factor> (<mulop> <not_factor>)*
<expression>    ::= <signed_term> (<addop> <term>)*
<assignment>    ::= <variable> '=' <expression>

That's a big improvement over earlier efforts. Will our luck continue to hold when we get to relational operators? We'll find out soon, but it will have to wait for the next installment. We're at a good stopping place, and I'm anxious to get this installment into your hands. It's already been a year since the release of Chapter 15, Back To The Future. I blush to admit that all of this current installment has been ready for almost as long, with the exception of relational operators. But the information does you no good at all, sitting on my hard disk, and by holding it back until the relational operations were done, I've kept it out of your hands for that long. It's time for me to let go of it and get it out where you can get value from it. Besides, there are quite a number of serious philosophical questions associated with the relational operators, as well, and I'd rather save them for a separate installment where I can do them justice.

Have fun with the new, leaner arithmetic and logical parsing, and I'll see you soon with relationals.