An Expression Parser

The Expression Parser ("Expressions") was intended to be a very simple program that explored the AspectJ tools and some uses of aspects.

The base program parses the following grammar for expressions (boldface blue denotes terminal symbols; metasyntactic symbols and non-terminals are in this font)

expression	= primary | primary / primary | primary * primary
primary	= factor | - factor | factor + factor | factor - factor | - factor + factor | - factor - factor
factor	= literal | ( expression )
literal	= integerLiteral | realLiteral
integerLiteral	= digitString
realLiteral	= . digitstring | digitstring . digitstring | digitstring .
digitstring	= [ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ] +

Each of the non-terminals expression, primary, factor and literal is represented by an interface in the program. Classes corresponding to the right hand sides of the above syntax rules implement these interfaces; some additional abstract superclasses are introduced to enable code-sharing. For example, Quotient and Product inherit code from BinaryExpression.

Here is a diagram of the classes and interfaces.

All of the interfaces (Literal, Factor, Primary and Expression) are identical: they contain a single method printOn(PrintStream), although I imagine taht they would evolve to be different if more functionality were added. In addition, all of the classes understand the method readFrom(LookAheadInputStream), although this importqant commonaliy cannot be captured with Java interfaces. Each of the readFrom methods assumes that it is called with the input stream in a legal state for the kind of syntactic entity that it is designed to read, and continues to consume input (invoking other readFrom methods) until a character is found that is not a legal input.

Note that the readFrom methods tend to be in the abstract superclasses. For example, having observed that the next imput character is a digit, we know that we need to read some kind of literal, but not whether it is an integerLiteral or a realLitteral. So the readFrom method in class SomeLiteral is called, which makes that determination and constructs the appropriate object.

Thus, the result of calling Expression e = SomeExpression.readFrom(i) is to build an expression tree corresponding to the input. The message e.printOn(System.out) will cause the tree to be printed, by recurseively sending printOn to all of the component objects.

To do anything interesting, we need to add methods to all of the relvant objects. For example, to do evaluation of the arithmatic expression, we would need to add a method that responds to ArithmeticEval to the IntegerLiteral, RealLiteral, ParenthesizedExpression, Product, Quotient, Sum, Difference, and Negated objects. Each of these methods is different, so inheritance does not help us to factor the code.

The conventional solution to this problem is to use the "visitor" pattern, and to make ArithmenticEval a class rather than a method. However, this still requires that a visit method be added to every terminal object.

Aspects provide an alternative and superior solution. All of the ArithmeticEval methods can be placed in a single ArithmeticEval aspect:

// first the interfaces
 
introduce public double Expression.ArithmeticEval();
 
// then the classes
 
introduce public double IntegerLiteral.ArithmeticEval()
{ return theDigits.toLong();
}
 
introduce public double RealLiteral.ArithmeticEval()
{ return (wholePart.toLong() + fractionalPart.toLong() /
    Math.pow(10, fractionalPart.length()));
}
 
introduce public double ParenthesizedExpression.ArithmeticEval()
{ return theExp.ArithmeticEval();
}
 
introduce public double Product.ArithmeticEval()
{ return left.ArithmeticEval() * right.ArithmeticEval();
}
 
introduce public double Quotient.ArithmeticEval()
{ return left.ArithmeticEval() / right.ArithmeticEval();
}
 
introduce public double Sum.ArithmeticEval()
{ return left.ArithmeticEval() + right.ArithmeticEval();
}
 
introduce public double Difference.ArithmeticEval()
{ return left.ArithmeticEval() - right.ArithmeticEval();
}
 
introduce public double Negated.ArithmeticEval()
{ return - theFactor.ArithmeticEval();
}

} // end of ArithmeticEval

Notice that it is also necessary to intorduce an ArithmeticEval method into the interface Expression so that clients can send this message to objects of type Expression.

One this pattern has been established, it is easy to see how to add alternative evaluations. For example, an abstract evaluation for type can be added as a separate aspect:

// first the interfaces
 
introduce public Type Expression.TypeEval();
 
// then the classes
 
introduce public Type IntegerLiteral.TypeEval()
{ return Type.integer();
}

introduce public Type RealLiteral.TypeEval()
{ return Type.real();
}

introduce public Type ParenthesizedExpression.TypeEval()
{ return theExp.TypeEval();
}

introduce public Type Product.TypeEval()
{ return Type.times(left.TypeEval(), right.TypeEval());
}

introduce public Type Quotient.TypeEval()
{ return Type.divide(left.TypeEval(), right.TypeEval());
}

introduce public Type Sum.TypeEval()
{ return Type.plus(left.TypeEval(), right.TypeEval());
}

introduce public Type Difference.TypeEval()
{ return Type.minus(left.TypeEval(), right.TypeEval());
}

introduce public Type Negated.TypeEval()
{ return theFactor.TypeEval();
}
 

} // end of TypeEval

Of course, this aspect also requires a suitable definition for Type, which is essentially an enumeration type with appropriate definitions for plus, times, etc. A simple main method can call on both kinds of evaluation:

public static void main(String args[])
throws EOFException, IOException, InvalidParameter {

LookAheadInputStream i = new LookAheadInputStream(System.in);
Expression e = SomeExpression.readFrom(i);
e.printOn(System.out);
System.out.print(" = ");
System.out.print(e.ArithmeticEval());
System.out.println(" (" + e.TypeEval() + ")");

}

} // end of class Expr2Aspects

input:  2 + (9/3) =

output: 2 + (9 / 3) = 5.0 (rational)

Notice that the type analysis correctly tells us that the result is rational, since it involves the division of 9 by 3, even though in this case the answer happens to be a whole number. Another run gives a perhaps unexpected result:

input:   4 + 5 /2.5 =

output:  4 + 5 / 2.5 = 3.6 (real)

Here we see that the expression is evaluated left to right, as (4+5)/2.5. This is not what someone who did not examine the grammar closely might expect! To try to understand why the program behaves in this way, we might add a print statement to each of the readFrom(...) methods. This can also be accomplished by means of an aspect:

advise

static * BinaryExpression.readFrom(LookAheadInputStream i, Primary first),
static * BinaryPrimary.readFrom(LookAheadInputStream i, Factor first),
static * DigitString.readFrom(LookAheadInputStream i)
static * SomeFactor.readFrom(LookAheadInputStream i),
static * ParenthesizedExpression.readFrom(LookAheadInputStream i),
static * SomeExpression.readFrom(LookAheadInputStream i),
static * SomeFactor.readFrom(LookAheadInputStream i),
static * SomeLiteral.readFrom(LookAheadInputStream i),
static * SomePrimary.readFrom(LookAheadInputStream i)

{

static before
{

System.out.println("reading " + thisClassName +
  "; next character is '" + i.peek() +"'" );

}

}

}