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!