|
| |
Abstract Syntax Trees
Part A: Integer, UnaryMinus, Plus and
Times
The first task is to write a set of classes: Integer,
UnaryMinus, Plus and
Times, which use inheritance
and polymorphism, and which can be used in the following
program:
package abstractSyntaxTree;
/**
* A class to represent an Abstract Syntax Tree.
* <p>
* @author: Bryan J. Higgs, 5 September 1998
* <p>
* @version 1.0
*/
public abstract class Tree
{
public static void main(String[] args)
{
Node expression =
new Plus(
new UnaryMinus(
new Integer(5)
),
new Times(
new Integer(12),
new Integer(4)
)
);
double result = expression.evaluate();
System.out.print("Result of ");
expression.walk();
System.out.println(" = " + result);
}
}
|
Sequence of steps to perform:
- Write a class
Integer, in package abstractSyntaxTree,
which extends class Node,
with a data member that will contain the integer value
for an instance of Integer,
with a constructor that allows an int value to be passed
in, and functions evaluate()
and walk().
Instances of class Integer
will be leaf nodes in the Abstract Syntax Tree.
- Now it's time to look at interior (non-leaf)
nodes. As mentioned before, these break down into two
subclasses -- unary and binary. However,
all operators share some degree of commonality, so,
first, let us create an abstract class
Operator,
in
package abstractSyntaxTree,
which extends Node,
and which contains nothing but a single protected
method:
protected abstract String name();
This will force every non-abstract class that extends the Operator
class to
implement a method with this signature. The name() method is
used to output the operator's symbol (+, -,
*, etc.). The name() function
will be called from the walk()
function (see later).
- All unary operators share some common
attributes. Naturally, every unary operator is an
Operator. In particular,
each unary operator needs only a single operand
(child) node. Create an abstract class, UnaryOperator,
in
package abstractSyntaxTree,
that extends class Operator.
This UnaryOperator
class will serve as the base class for all unary
operators. It will contain data members and methods
common to all unary operators.
The UnaryOperator class should have a single data member, representing the
unary operator's operand. [What type should this be?]
Make this data member private!
Provide a protected
method, getOperand(),
to allow derived classes to access, but not modify
this data member. Make the constructor for UnaryOperator
be protected.
Implement the walk()
method in the UnaryOperator
class. [Why there?]
Hint: This
walk() method will make recursive
calls to itself and other virtual walk() member functions.
- Create the non-abstract class
UnaryMinus,
in
package abstractSyntaxTree,
which extends UnaryOperator.
It should have a very simple public
constructor (with what for arguments?).
Implement the evaluate()
and name()
methods for this class.
- All binary operators share some common
attributes. Naturally, every binary operator is an
Operator. In addition,
each binary operator needs two data members--
one its left operand (child) node, and the other its
right operand (child) node. Create an abstract
class, BinaryOperator, in package abstractSyntaxTree,
which extends Operator.
This class will serve as the base class for all binary
operators. It will contain data members and methods
common to all binary operators.
The BinaryOperator class should have a two data
members. What type should each one be? Make
these data members private!
Provide protected
access member functions, getLeftOperand()
and getRightOperand(),
to allow derived classes to access, but not modify
them. Make the constructor for BinaryOperator
be protected.
Implement the walk()
virtual member function in the BinaryOperator
class.
Hint: This walk() method will make recursive
calls to itself and other virtual walk() member functions.
- Create the classes
Plus and
Times, in
package abstractSyntaxTree,
each extending BinaryOperator.
They should have a very simple public
constructor (with what for arguments?)
Implement the evaluate()
and name()
methods for these classes.
- By now, you should be able to build the entire
Tree class,
and run it.
My version produced the following output:
Result of -5 + 12 * 4 = 43.0
|
