Package step9

Step 9: Typing.


Interface Summary
expr.yyActions interface between grammar and actions.
expr.yyInput must be implemented by a scanner object to supply input to the parser.

Class Summary
bdis rewrites Node trees as typed trees.
bdis.DAdd add two bdis.DoubleT trees.
bdis.DDiv divide two bdis.DoubleT trees.
bdis.DEq equal of two bdis.DoubleT trees.
bdis.DGe greater-equal of two bdis.DoubleT trees.
bdis.DGt greater-then of two bdis.DoubleT trees.
bdis.DLe less-equal of two bdis.DoubleT trees.
bdis.DLt less-then of two bdis.DoubleT trees.
bdis.DMinus sign-change an bdis.DoubleT tree.
bdis.DMul multiply two bdis.DoubleT trees.
bdis.DNe not-equal of two bdis.DoubleT trees.
bdis.DoubleT base class for double operations, itself used to type a Double leaf.
bdis.DPrint print a bdis.DoubleT object.
bdis.DSub subtract two bdis.DoubleT trees.
bdis.I2D convert i.IntegerT to bdis.DoubleT.
bdis.SAdd concatenate two bdis.StringT trees.
bdis.SEq equal of two bdis.StringT trees.
bdis.SGe greater-equal of two bdis.StringT trees.
bdis.SGt greater-then of two bdis.StringT trees.
bdis.SLe less-equal of two bdis.StringT trees.
bdis.SLt less-then of two bdis.StringT trees.
bdis.SNe not-equal of two bdis.StringT trees.
bdis.SPrint print a bdis.StringT object.
bdis.StringT base class for string operations, itself used to type a String leaf.
bi rewrites Node trees as typed trees.
bi.BAnd and of two bi.BooleanT trees.
bi.BAndIf and-if of two bi.BooleanT trees.
bi.BEq equal of two bi.BooleanT trees.
bi.BNe not-equal of two bi.BooleanT trees.
bi.BNot negate a bi.BooleanT tree.
bi.BooleanT base class for boolean operations, itself used to type an Boolean leaf.
bi.BOr or of two bi.BooleanT trees.
bi.BOrIf or-if of two bi.BooleanT trees.
bi.BPrint print a bi.BooleanT object.
bi.BXor xor of two bi.BooleanT trees.
bi.IEq equal of two i.IntegerT trees.
bi.IGe greater-equal of two i.IntegerT trees.
bi.IGt greater-then of two i.IntegerT trees.
bi.ILe less-equal of two i.IntegerT trees.
bi.ILt less-then of two i.IntegerT trees.
bi.INe not-equal of two i.IntegerT trees.
expr fairly comprehensive mixed mode expressions on lines.
expr.yyTree tree factory.
i rewrites Node trees as typed trees.
i.IAdd add two i.IntegerT trees.
i.IAnd bit-and two i.IntegerT trees.
i.IDiv divide two i.IntegerT trees.
i.ILsh left shift two i.IntegerT trees.
i.IMinus sign-change an i.IntegerT tree.
i.IMod remainder of two i.IntegerT trees.
i.IMul multiply two i.IntegerT trees.
i.INeg bit-complement an i.IntegerT tree.
i.IntegerT base class for integer operations, itself used to type an Integer leaf.
i.IOr bit-or two i.IntegerT trees.
i.IPrint print an i.IntegerT object.
i.IRsh right shift two i.IntegerT trees.
i.ISub subtract two i.IntegerT trees.
i.IXor bit-xor two i.IntegerT trees.
i.T base class for typed branch nodes.

Exception Summary
expr.yyException thrown for irrecoverable syntax errors and stack overflow.

Package step9 Description

Step 9: Typing.

Typing by Rewriting

Code generation for the register machine in step 8 demonstrates one approach to dealing with different types for values: a visitor decides the result type of each operation and selects the appropriate operator. Machine instructions to convert operand values are generated if the operand types do not fit the operator. As illustrated, the approach works well for a combination of integer and floating point arithmetic, but it does not scale well to more data types.

expr.pj is a frontend which recognizes lines with an extensive set of expressions with boolean, floating point, integer, and string literals and uses Node as a common base class for all branch nodes. (There should be an additional class to represent leaf nodes with strings which removes delimeters and elaborates escape sequences when a leaf node is constructed.)

$ mkdir step9
$ java -jar pj.jar -jay -scanner:static - -tree:static - expr.pj > step9/
$ javac step6/ step9/
$ java step9.expr
- (1 % ( 2 + 3 * 4 - 5 / 6 ))
  Mod 1
      Add 2
        Mul 3 4
      Div 5 6]

i.jag is a visitor which replaces each branch node with integer operands and result by a new branch node which is specific for the integer operation, e.g., expr.yyTree.Add is replaced by i.IAdd.

$ java -jar jag.jar < step9/i.jag > step9/
$ javac step9/
$ java step9.i
1 + 2
[Add 1 2]
    IntegerT 1
    IntegerT 2]

The visitor proceeds in postorder. An Integer leaf node is pushed below a i.IntegerT branch node to simplify further analysis:

Integer: { $$ = IntegerT($0); };
The visitor itself is a factory and provides the new tree classes which all descend from i.T.

The rule for a binary branch node arranges for the postorder visit and attaches the rewritten subtrees in place of the generic subtrees:

  // ... typed part, see below
  | Object Object     { $0.set(0, visit($1)); $0.set(1, visit($2));
                        $$ = visit($0);
The current node, which now has typed descendants, is then revisited to create the typed result node. (If the original tree should be preserved for some reason, the new subtrees could be attached to an ArrayList node for the visit. Old and new tree would then only share the leaf nodes.) The typed rules are more specific and have to appear before the postorder rules:
    IntegerT IntegerT { $$ = prefix("I", $0); }
  | T T               { if ($0 != null) // avoid 'unreachable' error
                          throw new RuntimeException(classname($0)
                            +" "+classname($1)+" "+classname($2)
                            +": no such operation");
  // ... untyped part, see above
prefix() uses reflection to find a factory method implemented by the visitor which generates a branch node for the typed operation with a classname similar to the generic operation:
  public Object prefix (java.lang.String name, List op) {
    name += classname(op);
    try {
      return getClass().getMethod(name, new Class[]{ ArrayList.class })
        .invoke(this, new Object[]{ op });
    } catch (Exception e) {
      throw new RuntimeException(name+": no such operation", e);
The visitor class i has to contain factory methods and nested classes for all supported operations. A simple awk program can create them from a table:
// class param superclass construct
% IPrint IntegerT T add print an i.IntegerT object
% IOr ArrayList IntegerT super bit-or two i.IntegerT trees
% IXor ArrayList IntegerT super bit-xor two i.IntegerT trees
% IAnd ArrayList IntegerT super bit-and two i.IntegerT trees
% ILsh ArrayList IntegerT super left shift two i.IntegerT trees
% IRsh ArrayList IntegerT super right shift two i.IntegerT trees
% IAdd ArrayList IntegerT super add two i.IntegerT trees
% ISub ArrayList IntegerT super subtract two i.IntegerT trees
% IMul ArrayList IntegerT super multiply two i.IntegerT trees
% IDiv ArrayList IntegerT super divide two i.IntegerT trees
% IMod ArrayList IntegerT super remainder of two i.IntegerT trees
% IMinus ArrayList IntegerT super sign-change an i.IntegerT tree
% INeg ArrayList IntegerT super bit-complement an i.IntegerT tree

Once the infrastructure is in place, it is easy to extend it to a mix of types. bi.jag provides bi.BooleanT to represent logical operations and integer comparisons.

$ java -jar jag.jar < step9/bi.jag > step9/
$ javac step9/
$ java
10 < 12 && !false
  Lt 10 12
  Not false]
      IntegerT 10
      IntegerT 12
      BooleanT false]

Result types have nothing to do with jag rules. Therefore, this just requires a rule for expressions with boolean operands:

  // ... other specific types, see above
  | BooleanT BooleanT { $$ = prefix("B", $0); }
The following branch nodes are added:
// class param superclass construct
// boolean operations
% BPrint BooleanT T add print a bi.BooleanT object
% BOrIf ArrayList BooleanT super or-if of two bi.BooleanT trees
% BAndIf ArrayList BooleanT super and-if of two bi.BooleanT trees
% BOr ArrayList BooleanT super or of two bi.BooleanT trees
% BXor ArrayList BooleanT super xor of two bi.BooleanT trees
% BAnd ArrayList BooleanT super and of two bi.BooleanT trees
% BEq ArrayList BooleanT super equal of two bi.BooleanT trees
% BNe ArrayList BooleanT super not-equal of two bi.BooleanT trees
% BNot ArrayList BooleanT super negate a bi.BooleanT tree
// integer comparisons with boolean result
% ILt ArrayList BooleanT super less-then of two i.IntegerT trees
% ILe ArrayList BooleanT super less-equal of two i.IntegerT trees
% IGt ArrayList BooleanT super greater-then of two i.IntegerT trees
% IGe ArrayList BooleanT super greater-equal of two i.IntegerT trees
% IEq ArrayList BooleanT super equal of two i.IntegerT trees
% INe ArrayList BooleanT super not-equal of two i.IntegerT trees

Finally, bdis.jag provides bdis.DoubleT to represent floating point operations and bdis.StringT to represent string operations.

$ java -jar jag.jar < step9/bdis.jag > step9/
$ javac step9/
$ java step9.bdis
"high" < "low" || 1. + 2 == 3
  Lt "high" "low"
    Add 1.0 2
      StringT "high"
      StringT "low"
        DoubleT 1.0
          IntegerT 2
        IntegerT 3]

Again, this requires rules for expressions with operands of the new types and additionally some rules for mixed mode arithmetic:

  // ... other specific types, see above
  | DoubleT DoubleT   { $$ = prefix("D", $0); }
  | IntegerT DoubleT  { $0.set(0, I2D($1)); $$ = visit($0); } // widen
  | DoubleT IntegerT  { $0.set(1, I2D($2)); $$ = visit($0); }
  | StringT StringT   { $$ = prefix("S", $0); }
Many more branch nodes can be added. If a branch node class and factory method exists, the typed operation is supported. A hand-written factory method or a more specific rule for a generic operation and certain types of descendants can be used to disallow a particular combination.
// class param superclass construct
// double operations
% DPrint DoubleT T add print a bdis.DoubleT object
% DAdd ArrayList DoubleT super/tt> add two bdis.DoubleT trees
% DSub ArrayList DoubleT super/tt> subtract two bdis.DoubleT trees
% DMul ArrayList DoubleT super/tt> multiply two bdis.DoubleT trees
% DDiv ArrayList DoubleT super/tt> divide two bdis.DoubleT trees
% DMinus ArrayList DoubleT super/tt> sign-change an bdis.DoubleT tree
// conversion to double
% I2D IntegerT DoubleT add/tt> convert i.IntegerT to bdis.DoubleT
// double comparisons with boolean result
% DLt ArrayList BooleanT super/tt> less-then of two bdis.DoubleT trees
% DLe ArrayList BooleanT super/tt> less-equal of two bdis.DoubleT trees
% DGt ArrayList BooleanT super/tt> greater-then of two bdis.DoubleT trees
% DGe ArrayList BooleanT super/tt> greater-equal of two bdis.DoubleT trees
% DEq ArrayList BooleanT super/tt> equal of two bdis.DoubleT trees
% DNe ArrayList BooleanT super/tt> not-equal of two bdis.DoubleT trees
// string operations
% SPrint StringT T add/tt> print a bdis.StringT object
% SAdd ArrayList StringT super/tt> concatenate two bdis.StringT trees
// string comparisons with boolean result
% SLt ArrayList BooleanT super/tt> less-then of two bdis.StringT trees
% SLe ArrayList BooleanT super/tt> less-equal of two bdis.StringT trees
% SGt ArrayList BooleanT super/tt> greater-then of two bdis.StringT trees
% SGe ArrayList BooleanT super/tt> greater-equal of two bdis.StringT trees
% SEq ArrayList BooleanT super/tt> equal of two bdis.StringT trees
% SNe ArrayList BooleanT super/tt> not-equal of two bdis.StringT trees