Assignment 1 for CSCI 431

Compiling and Evaluating Simple Expressions

<var>-> a | i | j

{<expr>, <term>, <factor>, <var>, <addOp>, <multOp>} are the non-terminals. {a,i,j,+,*,(,)} are the terminals. <expr> is the start symbol. The meta-symbol "->" separates the lhs and the rhs of a production rule, the meta-symbol "|" represents alternatives on the rhs, and the paired curly braces "{...}" stands for Kleene-star operator (that is, 0 or more iterations of the enclosed regular expression).

Some example arithmetic expressions are "i",   "( a + a ) * i",   " (i * a) + (j + a)", etc. Some illegal expressions are "(b)",   "6", etc. (Note that the double quotes are not part of the expression.)

Now consider the following template for a collection of Java programs.

class Test {
   static double f(double a, int i, int j) {
      return <expr>;
   }
   public static void main(String[] args) {
      System.out.println(f(0.0,1,2));
   }
}

To obtain a valid Java program (that is, valid function body), replace <expr> with a string derived from the above grammar.

A Java compiler takes the source code and generates Java bytecode, which resemble assembly language instructions for a stack machine. The translation of the return-expression "((i + a) * j)" into bytecode can be given symbolically as:

   iload_2
   i2d
   dload_0
   dadd
   iload_3
   i2d
   dmul
   dreturn

The formal arguments a, i, and j are encoded as variables in registers 0, 2, and 3. (The double value requires registers 0 and 1.) A typical instruction encodes information about the type and the location of the operands, and the nature of the operation. For example, iload_2 (dload_0) stands for pushing the value of the integer (double) variable i (a) on top of the stack ; istore_2 (dstore_0) stands for moving the value from the top of the stack to the location of the integer (double) variable i (a) ; dadd (imul) stands for popping the top two double (integer) values from the stack, adding (multiplying) them, and pushing the result on top of the stack; and i2d(d2i) stands for coercing an integer (a double) value to a double (an integer) value. (For other details about the JVM, refer to The Java Virtual Machine Specification, specifically the chapter on the Instruction Set.)

To generate more examples of such translation, instantiate the above template by replacing <expr> with a legal arithmetic expression in "Test.java", compile it using
"javac Test.java", and reverse engineer the class file using
"javap -c Test", focusing on "Method double f(double, int, int).

Your assignment

1. A parse tree for the expression demonstrating that it is legal in the grammar given above.
2. A hand-annotated version of the bytecode for that expression. Your annotations should explain each bytecode instruction generated for the expression.