A Short Course in Compilers -- A Warm-up Exercise

Warm-up Exercise for Changing xcom

It is faster to make a 4-inch mirrror

and then a 6-inch mirror

than it is to make a 6-inch mirror

-- Allyn J. Thompson Making your own Telescope 1947

Different Styles

Some students want to understand everything before hacking into a piece of complicated software like xcom. If that is you, then wait awhile before doing this exercise, but do read through the description all the way in any case.

If you like to live dangerously, and learn a lot real fast, forge ahead. The idea is to shoot a bullet right through xcom, missing almost everything, but adding just a bit of new functionality. Don't forget, you are getting help with your aim. You can always get another xcom if you mess this one up.

When it comes time to make a serious change to xcom, there is a systematic method. Each module has a unit test and a unit trial After any change to a module, the unit test is also changed to test the new functionality. The idea in this case is to proceed through xcom, checking each step before moving on to the next. More than likely, you will want to enhance the trial as a natural consequence of seeing what is going on with your changes.

Add abs to X

Consulting page 2 of the reference manual for X, one notes that there are four builtin functions. One generates a random number, the other three convert between types. All of them are represented by reserved words. I propose a fifth builtin

signatures	op	meaning
r(r) i(i)	abs(x)	absolute value (real or integer)

Steps

Add a line to context-free grammar X.cfg.
The new line
```
  abs factor
```
conveniently comes right before the line for rand. The new line looks like the line for function r2i. Here is how the end of the X.cfg file should look:
```
  r2i factor
  abs factor
  rand
```
Note that there are no parentheses in the grammar for abs. Since parentheses are allowed in general, then both forms
```
  abs 2.1
```
and
```
  abs(-7)
```
will be syntactically correct. That is, function abs is to be a unary prefix operator like '-'. Because abs appears in the grammar, and not as a rule name, it is automatically classified as a new reserved word by Cfg.m. Of course, you have to remember to run makeCfg (below) for your changes to X.cfg to be noticed by xcom.

Note: The lexer will discover new symbols, such as abs, or an operator such as '.' from X.cfg. The lexer will not, however, know what to do with a new literal constant such as "string". For such as that you will have to hack the lexer itself.

Make new cfg tables

    >> makeCfg -saveMat X.cfg

or, if you are in a hurry and are not using the LR tables,

    >> makeCfg -noLR -saveMat X.cfg

Run xcom
```
    >> xcom x:=1
    >> xcom x:=y+1
    >> xcom x:=abs(-1)
    >> xcom x:=abs(-1.0)
  
```
What you discover is the first two trials work, the second two fail. This result should not be too surprising. Except for the new unknown builtin abs, nothing has changed. Cfg has built new tables but all the old values are still available. Note that the diagnostic has come from the Parser, so apparently the Lexer has not been damaged by your bullet. In fact the Cfg processor has recognized that abs is a new reserved word and added it to the reserved word table. It would do the same for a new operator identifier (say &&). Moving right along...
Modify Parser.m.
Find an M function factor. It has a switch on the current token tok. What you must do is add the line
```
  case rw.abs, step(); factor(); reduce(rule.factor_absfactor);
```
right after the line for r2i. What you are doing is telling the parser that when it encounters this new reserved token abs, it is to stop complaining (as it did on your earlier test) and instead step past the token, call function factor (recursively) and, finally, report that it has reduced a rule named
```
  rule.factor_absfactor
```
The new funny name is constructed by Cfg.m by mangling the whole grammar rule. Look at the grammar to see the correspondence between funny names and rule texts. The funny names are unique and do not change when new rules are added.
Rerun the four xcom tests (above).
The two abs tests still cause errors, but this time from the symbol table. xcom object Tree has built a tree with a new kind of node in it, and the xcom object Symbols does not know what to do with that node. But, this is progress. Apparently Cfg.m, Lexer.m, Parser.m and Tree.m can handle the new builtin.
Modify Symbols.m.
Find the (very big) function exprWalk. It contains a case containing a funny node name for our next-door X.cfg neighbor r2i:
```
  case rn.factor_r2ifactor                 % r2i x
  if bitand(mustBe, intType) == 0
    symErr(nd, 'r2i returns type real');
  end
  exprWalk(tree.getKid(nd, 2), realType);
  res = intType;
```
The first test makes sure that an intType result is allowed by the context (variable mustBe). If not, then r2i has discovered a type error. The symbol module gives a diagnostic and quits.

Supposing intType is allowed by the context, then the tree representing the argument to r2i is walked (recursion). In this case, the new value of mustBe is passed down the tree as realType because r2i demands a real argument. Finally, the resulting type is set to intType (as demanded by r2i).

The r2i case is a template for the new case you need to add.
```
  case rn.factor_absfactor                 % abs x
    if bitand(mustBe, arithType) == 0      % arith is OK
      symErr(nd, 'arithmetic type needed for abs');
    end
    res = exprWalk(tree.getKid(nd, 2), bitand(mustBe, arithType));
```
Since abs can be overloaded, it is has a more relaxed initial type test that r2i. In this case, when the function exprWalk recurs, it makes sure it does not further relax constraint mustBe. When exprWalk returns, it may have tightened the type of the result. Or maybe not.
Rerun the four xcom tests (above).
Now the diagnostic comes from xcom object Generator. The missing code is in the generator's exprWalk function.
Modify Generator.m
Add a case after factor_r2ifactor
```
  rn.factor_absfactor
```
Don't forget the semicolon separating cases.
Rerun the four xcom tests.
Now the diagnostic comes from object EmitX86. We have a missing case in M function expr1 (expressions with a single argument). Actually, we have two missing cases, one for integer and one for real.
Modify EmitX86.m
Since there are two cases for abs, abs needs two new code sequences.

The case for real is analogous to, and in the same switch as, unary '-'. The new code is:
```
  case rn.factor_absfactor               % abs(real)
    toR(opd);                            % to FPS
    asm.fabs();                          % take float abs
    toX(opd);                            % off FPS into temp
```
Code is emitted to push the operand onto the hardware floating point stack, the (very convenient) Intel absolute value instruction is emitted, and then code is emitted to pop the FPS operand into temporary memory. It would be more efficient to leave the result on the floating point stack, but then one would have to deal with potential FPS stack overflow.

The integer case is a little more complicated since there is no integer absolute value instruction. The new code is:
```
  case rn.factor_absfactor               % abs(int)
    toR(opd);                            % into reg
    asm.cmpRC(getVal(opd),0);            % compare with zero
    fixuploc = asm.jge32(0);             % jmp if nonneg
    asm.negR(getVal(opd));               % negate
    asm.fixup32(fixuploc);               % fill in destination
```
The operand is forced into a general register (it may already be in one). Then the register is compared with zero. If it is non-negative, nothing needs to be done so some code is skipped. Otherwise, the register is negated. Finally the conditional branch address needs to be filled in.
Modify AsmX86.m
Actually, the fabs instruction is already implemented. What you should do is look at AsmX86.m to make sure.
Run the four xcom tests above again.
It works!
Do more thorough testing. Run testAll() and tryAll().

The unit tests and trials also pass. You are done! As mentioned above, if making a serious change, each unit test needs new code to confirm that the change did the expected thing.