16.3. Terms And Expressions

I'm sure you know what's coming next: We must, yet again, create the rest of the procedures that implement the recursive-descent parsing of an expression. We all know that the hierarchy of procedures for arithmetic expressions is:

expression 
        term 
                factor

However, for now let's continue to do things one step at a time, and consider only expressions with additive terms in them. The code to implement expressions, including a possibly signed first term, is shown next:

{ Parse and Translate an Expression }
procedure Expression;
begin
        SignedFactor;
        while IsAddop(Look) do
                case Look of
                        '+': Add;
                        '-': Subtract;
                end;
end;

This procedure calls two other procedures to process the operations:

{ Parse and Translate an Addition Operation }
procedure Add;
begin
        Match('+');
        Push;
        Factor;
        PopAdd;
end;

{ Parse and Translate a Subtraction Operation } 
procedure Subtract;
begin
        Match('-');
        Push;
        Factor;
        PopSub;
end;

The three procedures Push, PopAdd, and PopSub are new code generation routines. As the name implies, procedure Push generates code to push the primary register (D0, in our 68000 implementation) to the stack. PopAdd and PopSub pop the top of the stack again, and add it to, or subtract it from, the primary register. The code is shown next:

{ Push Primary to Stack }
procedure Push;
begin
        EmitLn('MOVE D0,-(SP)');
end;

{ Add TOS to Primary }
procedure PopAdd;
begin
        EmitLn('ADD (SP)+,D0');
end;

{ Subtract TOS from Primary }
procedure PopSub;
begin
        EmitLn('SUB (SP)+,D0');
        Negate;
end;

Add these routines to Parser and CodeGen, and change the main program to call Expression. Voila!

The next step, of course, is to add the capability for dealing with multiplicative terms. To that end, we'll add a procedure Term, and code generation procedures PopMul and PopDiv. These code generation procedures are shown next:

{ Multiply TOS by Primary }
procedure PopMul;
begin
        EmitLn('MULS (SP)+,D0');
end;

{ Divide Primary by TOS }
procedure PopDiv;
begin
        EmitLn('MOVE (SP)+,D7');
        EmitLn('EXT.L D7');
        EmitLn('DIVS D0,D7');
        EmitLn('MOVE D7,D0');
end;

I admit, the division routine is a little busy, but there's no help for it. Unfortunately, while the 68000 CPU allows a division using the top of stack (TOS), it wants the arguments in the wrong order, just as it does for subtraction. So our only recourse is to pop the stack to a scratch register (D7), perform the division there, and then move the result back to our primary register, D0. Note the use of signed multiply and divide operations. This follows an implied, but unstated, assumption, that all our variables will be signed 16-bit integers. This decision will come back to haunt us later, when we start looking at multiple data types, type conversions, etc.

Our procedure Term is virtually a clone of Expression, and looks like this:

{ Parse and Translate a Term }
procedure Term;
begin
        Factor;
        while IsMulop(Look) do
                case Look of
                        '*': Multiply;
                        '/': Divide;
                end; 
end;

Our next step is to change some names. SignedFactor now becomes SignedTerm, and the calls to Factor in Expression, Add, Subtract and SignedTerm get changed to call Term:

{ Parse and Translate a Term with Optional Leading Sign }
procedure SignedTerm;
var Sign: char;
begin
        Sign := Look;
        if IsAddop(Look) then
                GetChar;
        Term;
        if Sign = '-' then Negate;
end;
.
.
.
{ Parse and Translate an Expression }
procedure Expression;
begin
        SignedTerm;
        while IsAddop(Look) do
                case Look of
                        '+': Add;
                        '-': Subtract;
                end;
end;

If memory serves me correctly, we once had both a procedure SignedFactor and a procedure SignedTerm. I had reasons for doing that at the time ... they had to do with the handling of Boolean algebra and, in particular, the Boolean “not” function. But certainly, for arithmetic operations, that duplication isn't necessary. In an expression like:

-x*y

it's very apparent that the sign goes with the whole term, x*y, and not just the factor x, and that's the way Expression is coded.

Test this new code by executing Main. It still calls Expression, so you should now be able to deal with expressions containing any of the four arithmetic operators.

Our last bit of business, as far as expressions goes, is to modify procedure Factor to allow for parenthetical expressions. By using a recursive call to Expression, we can reduce the needed code to virtually nothing. Five lines added to Factor do the job:

{ Parse and Translate a Factor }
procedure Factor;
begin
        if Look ='(' then begin
                Match('(');
                Expression;
                Match(')');
                end
        else if IsDigit(Look) then
                LoadConstant(GetNumber)
        else if IsAlpha(Look)then
                LoadVariable(GetName)
        else
                Error('Unrecognized character ' + Look);
end; 

At this point, your “compiler” should be able to handle any legal expression you can throw at it. Better yet, it should reject all illegal ones!