tutor10.doc

计算机编译原理教材

       This version still won't generate any code for  the   "assignment
       statements" ... all it does is to eat characters  until  it  sees
       the 'e' for 'END.'  But it sets the stage for what is to follow.

       The  next  step,  of  course,  is  to  flesh out the code for  an
       assignment statement.  This  is  something  we've done many times
       before,  so  I  won't belabor it.  This time, though, I'd like to
       deal with the code generation a little differently.  Up till now,
       we've always just inserted the Emits that generate output code in
       line with  the parsing routines.  A little unstructured, perhaps,
       but it seemed the most straightforward approach, and made it easy
       to see what kind of code would be emitted for each construct.

       However, I realize that most of you are using an  80x86 computer,
       so  the 68000 code generated is of little use to you.  Several of
       you have asked me if the CPU-dependent code couldn't be collected
       into one spot  where  it  would  be easier to retarget to another
       CPU.  The answer, of course, is yes.

       To  accomplish  this,  insert  the  following  "code  generation"
       routines:


       {---------------------------------------------------------------}
       { Clear the Primary Register }

       procedure Clear;
       begin
          EmitLn('CLR D0');
       end;


       {---------------------------------------------------------------}
       { Negate the Primary Register }

       procedure Negate;
       begin
          EmitLn('NEG D0');
       end;


       {---------------------------------------------------------------}
       { Load a Constant Value to Primary Register }

       procedure LoadConst(n: integer);
       begin
          Emit('MOVE #');A*2A*
                                    - 15 -

PA2A





          WriteLn(n, ',D0');
       end;


       {---------------------------------------------------------------}
       { Load a Variable to Primary Register }

       procedure LoadVar(Name: char);
       begin
          if not InTable(Name) then Undefined(Name);
          EmitLn('MOVE ' + Name + '(PC),D0');
       end;


       {---------------------------------------------------------------}
       { Push Primary onto Stack }

       procedure Push;
       begin
          EmitLn('MOVE D0,-(SP)');
       end;


       {---------------------------------------------------------------}
       { Add Top of Stack to Primary }

       procedure PopAdd;
       begin
          EmitLn('ADD (SP)+,D0');
       end;


       {---------------------------------------------------------------}
       { Subtract Primary from Top of Stack }

       procedure PopSub;
       begin
          EmitLn('SUB (SP)+,D0');
          EmitLn('NEG D0');
       end;


       {---------------------------------------------------------------}
       { Multiply Top of Stack by Primary }

       procedure PopMul;
       begin
          EmitLn('MULS (SP)+,D0');
       end;


       {---------------------------------------------------------------}
       { Divide Top of Stack by Primary }A62A6
                                    - 16 -A*2A*

PA2A





       procedure PopDiv;
       begin
          EmitLn('MOVE (SP)+,D7');
          EmitLn('EXT.L D7');
          EmitLn('DIVS D0,D7');
          EmitLn('MOVE D7,D0');
       end;


       {---------------------------------------------------------------}
       { Store Primary to Variable }

       procedure Store(Name: char);
       begin
          if not InTable(Name) then Undefined(Name);
          EmitLn('LEA ' + Name + '(PC),A0');
          EmitLn('MOVE D0,(A0)')
       end;
       {---------------------------------------------------------------}


       The  nice  part  of  this  approach,  of  course,  is that we can
       retarget  the compiler to a new CPU  simply  by  rewriting  these
       "code generator" procedures.  In  addition,  we  will  find later
       that we can improve the code quality by tweaking these routines a
       bit, without having to modify the compiler proper.

       Note that both LoadVar  and  Store check the symbol table to make
       sure that the variable is defined.  The  error  handler Undefined
       simply calls Abort:


       {--------------------------------------------------------------}
       { Report an Undefined Identifier }

       procedure Undefined(n: string);
       begin
          Abort('Undefined Identifier ' + n);
       end;
       {--------------------------------------------------------------}


       OK, we are now finally ready to begin processing executable code.
       We'll  do  that  by  replacing  the  stub  version  of  procedure
       Assignment.

       We've been down this  road  many times before, so this should all
       be familiar to you.    In fact, except for the changes associated
       with the code generation, we  could just copy the procedures from
       Part  VII.    Since we are making some changes, I won't just copy
       them, but we will go a little faster than usual.

       The BNF for the assignment statement is:A62A6
                                    - 17 -A*2A*

PA2A





            <assignment> ::= <ident> = <expression>

            <expression> ::= <first term> ( <addop> <term> )*

            <first term> ::= <first factor> <rest>

            <term> ::= <factor> <rest>

            <rest> ::= ( <mulop> <factor> )*

            <first factor> ::= [ <addop> ] <factor>

            <factor> ::= <var> | <number> | ( <expression> )


       This version of the BNF is  also  a bit different than we've used
       before ... yet another "variation on the theme of an expression."
       This particular version  has  what  I  consider  to  be  the best
       treatment  of  the  unary minus.  As you'll see later, it lets us
       handle   negative  constant  values  efficiently.    It's   worth
       mentioning  here  that  we  have  often  seen  the advantages  of
       "tweaking"  the  BNF  as we go, to help make the language easy to
       parse.    What  you're looking at here is a bit different:  we've
       tweaked  the  BNF  to make the CODE  GENERATION  more  efficient!
       That's a first for this series.

       Anyhow, the following code implements the BNF:


       {---------------------------------------------------------------}
       { Parse and Translate a Math Factor }

       procedure Expression; Forward;

       procedure Factor;
       begin
          if Look = '(' then begin
             Match('(');
             Expression;
             Match(')');
             end
          else if IsAlpha(Look) then
             LoadVar(GetName)
          else
             LoadConst(GetNum);
       end;


       {--------------------------------------------------------------}
       { Parse and Translate a Negative Factor }

       procedure NegFactor;
       begin
          Match('-');A*2A*
                                    - 18 -

PA2A





          if IsDigit(Look) then
             LoadConst(-GetNum)
          else begin
             Factor;
             Negate;
          end;
       end;


       {--------------------------------------------------------------}
       { Parse and Translate a Leading Factor }

       procedure FirstFactor;
       begin
          case Look of
            '+': begin
                    Match('+');
                    Factor;
                 end;
            '-': NegFactor;
          else  Factor;
          end;
       end;


       {--------------------------------------------------------------}
       { Recognize and Translate a Multiply }

       procedure Multiply;
       begin
          Match('*');
          Factor;
          PopMul;
       end;


       {-------------------------------------------------------------}
       { Recognize and Translate a Divide }

       procedure Divide;
       begin
          Match('/');
          Factor;
          PopDiv;
       end;


       {---------------------------------------------------------------}
       { Common Code Used by Term and FirstTerm }

       procedure Term1;
       begin
          while IsMulop(Look) do begin
             Push;A*2A*
                                    - 19 -

PA2A





             case Look of
              '*': Multiply;
              '/': Divide;
             end;
          end;
       end;


       {---------------------------------------------------------------}
       { Parse and Translate a Math Term }

       procedure Term;
       begin
          Factor;
          Term1;
       end;


       {---------------------------------------------------------------}
       { Parse and Translate a Leading Term }

       procedure FirstTerm;
       begin
          FirstFactor;
          Term1;
       end;


       {--------------------------------------------------------------}
       { Recognize and Translate an Add }

       procedure Add;
       begin
          Match('+');
          Term;
          PopAdd;
       end;


       {-------------------------------------------------------------}
       { Recognize and Translate a Subtract }

       procedure Subtract;
       begin
          Match('-');
          Term;
          PopSub;
       end;


       {---------------------------------------------------------------}
       { Parse and Translate an Expression }

       procedure Expression;A*2A*
                                    - 20 -

PA2A





       begin
          FirstTerm;
          while IsAddop(Look) do begin
             Push;
             case Look of
              '+': Add;
              '-': Subtract;
             end;
          end;
       end;


       {--------------------------------------------------------------}
       { Parse and Translate an Assignment Statement }

       procedure Assignment;
       var Name: char;
       begin
          Name := GetName;
          Match('=');
          Expression;
          Store(Name);
       end;
       {--------------------------------------------------------------}


       OK, if you've  got  all  this  code inserted, then compile it and
       check  it out.  You should  be  seeing  reasonable-looking  code,
       representing a complete program that will  assemble  and execute.
       We have a compiler!


       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 }A62A6
                                    - 21 -A*2A*

PA2A





       function IsOrop(c: char): boolean;
       begin
          IsOrop := c in ['|', '~'];
       end;


       {--------------------------------------------------------------}
       { Recognize a Relop }

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