Assignment 6

Abstract Syntax Trees

Description

Various programs (such as compilers and calculators), use a data structure called an Abstract Syntax Tree (AST) to represent syntax that has been recognized by the program.

Note: An Abstract Syntax Tree is not the same as a Binary Search Tree.
In a Binary Search Tree, both interior and leaf nodes can contain data, and the nodes are ordered in such a way that the data can be found by searching the tree in a prescribed order. In an Abstract Syntax Tree, the interior nodes contain operator information, while the leaf nodes contain operand information.
The order of the nodes within a Binary Search Tree is determined by the contents of each node. The order of the nodes in an AST is determined by the expression that the AST represents, and by the precedence of the expression’s components.

For example, the arithmetic expression:

-5+12*4

would be represented in Abstract Syntax Tree form as:

Note: Conventionally, trees in Computer Science are drawn upside down when compared to trees in the real world. Thus, the root of the tree is at the top, not the bottom.

An arithmetic expression uses a convention to distinguish between the different possible interpretations. For example, the expression:

-5+12*4

could be interpreted as either:

(-5+12)*4

or:

-5+(12*4)

The latter is the conventionally correct interpretation, because the multiplication operator conventionally has higher precedence than the addition operator. However, the Abstract Syntax Tree representation is inherently unambiguous, which is one of the reasons it is so popular.

In the above AST diagram, each element in the tree is connected to other items in the tree by lines. An element in an Abstract Syntax Tree is usually called a Node. Nodes can either be interior nodes or leaf nodes. Interior nodes are those that have one or more lines connecting them with other nodes further down the tree. Leaf nodes have no such connections; they are the lowest nodes in that particular branch of the tree. We say that interior nodes have child nodes, while leaf nodes do not.

In this example, interior nodes are used to represent the arithmetic operators (+, -, *, /, etc.). Arithmetic operators can be unary (operating on a single operand), or binary (operating on two operands). A unary operator has exactly one child node, while a binary operator has exactly two child nodes. For example, the minus sign in the above expression represents the unary minus operator, while the asterisk represents the binary multiplication operator, and the plus sign represents the binary addition operator.

A node below an operand in the tree can represent a value such as 5 or 12 (in the above diagram, all values are integer values). If the node represents a simple value, then it must be a leaf node. If it represents an expression (consisting of some combination of operators and operands), then the node must represent an operator, and therefore must be an interior node.

For example, imagine you wish to modify the original expression to look like this:

-(5/23)+12*(4-2)

The Abstract Syntax Tree for this new expression looks like:

Note that we have replaced the original leaf nodes for 5 and 4 by subtrees which represent the new subexpressions. The top node in each of these subexpressions represents an operator; which operator depends on the relative precedence of the operators in the subexpression.

A program can evaluate such a tree by walking the tree in a prescribed order: at each interior node it determines the value from each subtree, and applies the operator to those values to produce a value for the tree represented by that interior node. A leaf node provides a value directly. A program can also walk the tree in the same fashion to produce a printout of the equivalent arithmetic expression (although it would have to insert parentheses appropriately to maintain the operator precedence).

The Assignment

Your job is to write a set of classes which will allow you to construct such an abstract syntax tree, and then walk it, and evaluate it. Here’s an abstract Node class to start with:

package abstractSyntaxTree;

/**
 *  A class to represent a node in an Abstract Syntax Tree.
 *  <p>
 *  @author: Bryan J. Higgs, 5 September 1998
 *  <p>
 *  @version 1.0
 */

public abstract class Node
{
    public abstract double evaluate();
    public abstract void walk();
}

This class is to be used as a base class for a family of node classes which can be used to construct an AST and then evaluate and walk it. Copy it from this web page and paste it into your editor.

The evaluate() method returns the value for the (sub)tree, starting from that node on down. (Notice that it returns a double, not an int. This is because we would like to be able to evaluate expressions that contain more than integer values — see later.) For example, calling evaluate() for the node that represents the binary multiplication operator, *, in the original expression, will return a value of 48.0 (12*4). Calling evaluate() for the node at the top of the tree will return the value of the entire expression.

The walk() method prints out (on System.out) the arithmetic expression represented by that (sub)tree. In the original example expression, calling walk() for the node that represents the unary minus operator will print out:

-5

while calling walk() for the node that represents the binary multiplication operator will print out:

12 * 4

Calling walk() for the node at the top of the tree will print out the entire expression:

-5 + 12 * 4

We will break the assignment into three parts:

Part 1: Integer, UnaryMinus, Plus and Times

Part 2: Adding More Node Types

Part 3: Teaching walk() to correctly parenthesize

Part 1: 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:

1. 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.
2. 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).

3. 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.

4. 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.
5. 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.

6. 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.
7. 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

Part 2: Adding More Node Types

Requirement: For Part B, consider all the classes you developed in Part A locked. This means that you cannot add or change anything in those files.  Of course, if you find this rule impossible to abide by, then you probably didn’t implement Part A correctly, or perhaps you don’t understand something.  If the latter, don’t hesitate to ask questions!

Create the following classes, all in package abstractSyntaxTree:

8. A Real class that will hold floating point (double) values. This will, like the Integer class, be a leaf class in the abstract syntax tree.
9. A UnaryPlus class. This, of course, will look very similar to the UnaryMinus class.
10. A Minus class. This, of course, will look very similar to the Plus class.
11. A DividedBy class. This, of course, will look very similar to the Times class.

Here’s an enhanced Tree class to test your work:

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);
        
        expression = 
            new Minus(
                  new DividedBy(
                        new Real(53.5),
                        new Integer(45)
                        ),
                  new Times(
                        new Real(73.54),
                        new Plus(
                              new UnaryPlus(
                                    new Integer(3)
                                    ),
                              new Integer(8)
                              )
                        )
                   );
        result = expression.evaluate();
        System.out.print("Result of ");
        expression.walk();
        System.out.println(" = " + result);
        
        expression = 
            new Times(
                  new Minus(
                        new Real(53.5),
                        new Integer(45)
                        ),
                  new Plus(
                        new Real(73.54),
                        new Plus(
                              new UnaryMinus(
                                    new Integer(3)
                                    ),
                              new Integer(8)
                              )
                        )
                   );
        result = expression.evaluate();
        System.out.print("Result of ");
        expression.walk();
        System.out.println(" = " + result);
    }
}

When you have completed the additional classes, build this new Tree class and run it to get the results of the three expressions. (Copy the above code from this webpage and paste it into your editor.)

Note: You may notice that the second and third expressions in the above class are not correctly parenthesized when printed. Don’t worry about that for now; we’ll fix that later, in Part C.

How hard was it to add these classes?

What did you learn from this exercise?

Part 3: Teaching walk() to Correctly Parenthesize

You probably noticed in Part B that there are certain expressions (such as the second and third expressions in our enhanced Tree class) where the output isn’t quite right — it needed extra parentheses to represent the correct operator precedence.

Let’s fix this. Here are the steps we’ll follow:

1. Modify the Operator class as follows:
   • Add a set of public static final data members (why static and final?) of type int, to indicate various operator precedence levels:
     PREC_HIGHEST, PREC_HIGHER, PREC_MEDIUM, PREC_LOWER, PREC_LOWEST
     Note that the actual values of these data members don’t matter, except that the values should represent the relative precedence values appropriately. I suggest that PREC_LOWEST be assigned a value of 0, and that you increase the value by 5 or 10 for each precedence level above that. That way, if you later needed to insert an additional precedence level, you have room to do so.
   • Add a protected abstract method getPrecedence() to force every class that extends the Operator class to implement this method.
2. At this point, if you build your classes again, you’ll find that they won’t build — they generate errors. To solve this, you’ll have to add an implementation of the getPrecedence() method to every concrete class that extends Operator.
   • Have each method return one of the values defined in Operator (and remember that Operator is a superclass)
   • The UnaryPlus and UnaryMinus classes should return PREC_HIGHEST, the Times and DividedBy classes should return PREC_HIGHER, and the Plus and Minus classes should return PREC_MEDIUM
3. Once you’ve implemented all these getPrecedence() methods, the entire thing should build again. However, we haven’t actually used the methods anywhere, so the behavior of our classes will be as it was before. So, let’s finish the job:
   • In each of the walk() methods you’ll have to do the following:
     • For each operand, find out whether the operand is an Operator. How? 
       Hint: There’s a convenient operator to do this.
     • If it is an Operator, compare its precedence level with the precedence level of the current operator.
     • If the precedence level of the operand operator is lower than that of the current operator, insert parentheses around the walk() call for that operand.
4. That should do it! Rebuild, and try it.
   In my implementation, the second and third expressions printed out as:

Result of 53.5 / 45 - 73.54 * (+3 + 8) = -807.7511111111112
Result of (53.5 - 45) * (73.54 + -3 + 8) = 667.59

Hurray! You’re done! (with Assignment 6, at least)