10.7. Booleans

The next step should also be familiar to you. We must add Boolean expressions and relational operations. Again, since we've already dealt with them more than once, I won't elaborate much on them, except where they are different from what we've done before. Again, we won't just copy from other files because I've changed a few things just a bit. Most of the changes just involve encapsulating the machine-dependent parts as we did for the arithmetic operations. I've also modified procedure NotFactor somewhat, to parallel the structure of FirstFactor. Finally, I corrected an error in the object code for the relational operators: The Scc instruction I used only sets the low 8 bits of D0. We want all 16 bits set for a logical true, so I've added an instruction to sign-extend the low byte.

To begin, we're going to need some more recognizers:

{ Recognize a Boolean Orop }
function IsOrop(c: char): boolean;
begin
   IsOrop := c in ['|', '~'];
end;

{ Recognize a Relop }
function IsRelop(c: char): boolean;
begin
   IsRelop := c in ['=', '#', '<', '>'];
end;

Also, we're going to need some more code generation routines:

{ Complement the Primary Register }
procedure NotIt;
begin
   EmitLn('NOT D0');
end;
.
.
.
{ AND Top of Stack with Primary }
procedure PopAnd;
begin
   EmitLn('AND (SP)+,D0');
end;

{ OR Top of Stack with Primary }
procedure PopOr;
begin
   EmitLn('OR (SP)+,D0');
end;

{ XOR Top of Stack with Primary }
procedure PopXor;
begin
   EmitLn('EOR (SP)+,D0');
end;

{ Compare Top of Stack with Primary }
procedure PopCompare;
begin
   EmitLn('CMP (SP)+,D0');
end;

{ Set D0 If Compare was = }
procedure SetEqual;
begin
   EmitLn('SEQ D0');
   EmitLn('EXT D0');
end;

{ Set D0 If Compare was != }
procedure SetNEqual;
begin
   EmitLn('SNE D0');
   EmitLn('EXT D0');
end;

{ Set D0 If Compare was > }
procedure SetGreater;
begin
   EmitLn('SLT D0');
   EmitLn('EXT D0');
end;

{ Set D0 If Compare was < }
procedure SetLess;
begin
   EmitLn('SGT D0');
   EmitLn('EXT D0');
end;

All of this gives us the tools we need. The BNF for the Boolean expressions is:

     <bool-expr> ::= <bool-term> ( <orop> <bool-term> )*
     <bool-term> ::= <not-factor> ( <andop> <not-factor> )*
     <not-factor> ::= [ '!' ] <relation>
     <relation> ::= <expression> [ <relop> <expression> ]

Sharp-eyed readers might note that this syntax does not include the non-terminal “bool-factor” used in earlier versions. It was needed then because I also allowed for the Boolean constants TRUE and FALSE. But remember that in TINY there is no distinction made between Boolean and arithmetic types … they can be freely intermixed. So there is really no need for these predefined values … we can just use -1 and 0, respectively.

In C terminology, we could always use the defines:

     #define TRUE -1
     #define FALSE 0

Note

That is, if TINY had a preprocessor.

Later on, when we allow for declarations of constants, these two values will be predefined by the language.

The reason that I'm harping on this is that I've already tried the alternative, which is to include TRUE and FALSE as keywords. The problem with that approach is that it then requires lexical scanning for every variable name in every expression. If you'll recall, I pointed out in Installment Chapter 7, Lexical Scanning that this slows the compiler down considerably. As long as keywords can't be in expressions, we need to do the scanning only at the beginning of every new statement … quite an improvement. So using the syntax above not only simplifies the parsing, but speeds up the scanning as well.

OK, given that we're all satisfied with the syntax above, the corresponding code is shown below:

{ Recognize and Translate a Relational "Equals" }
procedure Equals;
begin
   Match('=');
   Expression;
   PopCompare;
   SetEqual;
end;

{ Recognize and Translate a Relational "Not Equals" }
procedure NotEquals;
begin
   Match('#');
   Expression;
   PopCompare;
   SetNEqual;
end;

{ Recognize and Translate a Relational "Less Than" }
procedure Less;
begin
   Match('<');
   Expression;
   PopCompare;
   SetLess;
end;

{ Recognize and Translate a Relational "Greater Than" }
procedure Greater;
begin
   Match('>');
   Expression;
   PopCompare;
   SetGreater;
end;

{ Parse and Translate a Relation }
procedure Relation;
begin
   Expression;
   if IsRelop(Look) then begin
      Push;
      case Look of
       '=': Equals;
       '#': NotEquals;
       '<': Less;
       '>': Greater;
      end;
   end;
end;

{ Parse and Translate a Boolean Factor with Leading NOT }
procedure NotFactor;
begin
   if Look = '!' then begin
      Match('!');
      Relation;
      NotIt;
      end
   else
      Relation;
end;

{ Parse and Translate a Boolean Term }
procedure BoolTerm;
begin
   NotFactor;
   while Look = '&' do begin
      Push;
      Match('&');
      NotFactor;
      PopAnd;
   end;
end;

{ Recognize and Translate a Boolean OR }
procedure BoolOr;
begin
   Match('|');
   BoolTerm;
   PopOr;
end;

{ Recognize and Translate an Exclusive Or }
procedure BoolXor;
begin
   Match('~');
   BoolTerm;
   PopXor;
end;

{ Parse and Translate a Boolean Expression }
procedure BoolExpression;
begin
   BoolTerm;
   while IsOrOp(Look) do begin
      Push;
      case Look of
       '|': BoolOr;
       '~': BoolXor;
      end;
   end;
end;

To tie it all together, don't forget to change the references to Expression in procedures Factor and Assignment so that they call BoolExpression instead.

OK, if you've got all that typed in, compile it and give it a whirl. First, make sure you can still parse an ordinary arithmetic expression. Then, try a Boolean one. Finally, make sure that you can assign the results of relations. Try, for example:

pvx,y,zbx=z>ye.

which stands for:

PROGRAM
VAR X,Y,Z
BEGIN
X = Z > Y
END.

See how this assigns a Boolean value to X?