tutor10.doc

计算机编译原理教材

       {--------------------------------------------------------------}


       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');A*2A*
                                    - 22 -

PA2A





       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;
       {---------------------------------------------------------------}AN2AN
                                    - 23 -A*2A*

PA2A





       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


       (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 VII  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;A*2A*
                                    - 24 -

PA2A





          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;A*2A*
                                    - 25 -

PA2A





              '>': 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;A*2A*
                                    - 26 -

PA2A





          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?

       CONTROL STRUCTURES

       We're almost home.   With  Boolean  expressions  in place, it's a
       simple  matter  to  add control structures.  For TINY, we'll only
       allow two kinds of them, the IF and the WHILE:


            <if> ::= IF <bool-expression> <block> [ ELSE <block>] ENDIF

            <while> ::= WHILE <bool-expression> <block> ENDWHILEA*2A*
                                    - 27 -

PA2A





       Once  again,  let  me  spell  out the decisions implicit in  this
       syntax, which departs strongly from that of C or Pascal.  In both
       of those languages, the "body" of an IF or WHILE is regarded as a
       single  statement.  If you intend to use a block of more than one
       statement, you have to build a compound statement using BEGIN-END
       (in Pascal) or  '{}' (in C).  In TINY (and KISS) there is no such
       thing as a compound statement  ... single or multiple they're all
       just blocks to these languages.

       In KISS, all the control structures will have explicit and unique
       keywords  bracketing  the  statement block, so there  can  be  no
       confusion as to where things begin  and  end.  This is the modern
       approach, used in such respected languages as Ada  and  Modula 2,
       and it completely eliminates the problem of the "dangling else."

       Note  that I could have chosen to use the same keyword END to end
       all  the constructs, as is done in Pascal.  (The closing '}' in C
       serves the same purpose.)  But this has always led  to confusion,
       which is why Pascal programmers tend to write things like


            end { loop }

       or   end { if }


       As I explained in  Part  V,  using  unique terminal keywords does
       increase  the  size  of the keyword list and therefore slows down
       the  scanning, but in this case it seems a small price to pay for
       the added insurance.   Better  to find the errors at compile time
       rather than run time.

       One last thought:  The two constructs above each  have  the  non-
       terminals


             <bool-expression> and <block>


       juxtaposed with no separating keyword.  In Pascal we would expect
       the keywords THEN and DO in these locations.

       I have no problem with leaving out these keywords, and the parser
       has no trouble either, ON CONDITION that we make no errors in the
       bool-expression part.  On  the  other hand, if we were to include
       these extra keywords we would get yet one more level of insurance
       at very little  cost,  and  I  have no problem with that, either.
       Use your best judgment as to which way to go.

       OK, with that bit of explanation let's proceed.  As  usual, we're
       going to need some new  code generation routines.  These generate
       the code for conditional and unconditional branches:AB2AB
                                    - 28 -A*2A*

PA2A





       {---------------------------------------------------------------}
       { Branch Unconditional  }

       procedure Branch(L: string);
       begin
          EmitLn('BRA ' + L);
       end;


       {---------------------------------------------------------------}
       { Branch False }

       procedure BranchFalse(L: string);
       begin
          EmitLn('TST D0');
          EmitLn('BEQ ' + L);
       end;
       {--------------------------------------------------------------}


       Except for the encapsulation of  the code generation, the code to
       parse the control constructs is the same as you've seen before: