10.6. Executable Statements

At this point, we can generate a null program that has some data variables declared and possibly initialized. But so far we haven't arranged to generate the first line of executable code.

Believe it or not, though, we almost have a usable language! What's missing is the executable code that must go into the main program. But that code is just assignment statements and control statements … all stuff we have done before. So it shouldn't take us long to provide for them, as well.

The BNF definition given earlier for the main program included a statement block, which we have so far ignored:

     <main> ::= BEGIN <block> END

For now, we can just consider a block to be a series of assignment statements:

     <block> ::= (Assignment)*

Let's start things off by adding a parser for the block. We'll begin with a stub for the assignment statement:

{ Parse and Translate an Assignment Statement }
procedure Assignment;
begin
   GetChar;
end;

{ Parse and Translate a Block of Statements }
procedure Block;
begin
   while Look <> 'e' do
      Assignment;
end;

Modify procedure Main to call Block as shown below:

{ Parse and Translate a Main Program }
procedure Main;
begin
   Match('b');
   Prolog;
   Block;
   Match('e');
   Epilog;
end;

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 #');
   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 }
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:

     <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('-');
   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;
      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;
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!