CE204
Data Structures and Algorithms
Part 6
18/02/2020 CE204 Part 6
1
Parse Trees 1
A tree provides a convenient means of representing the structure of the source code of a program. For example, the expression (a+7)*b can be represented by the tree
18/02/2020 CE204 Part 6
2
Parse Trees 2
It is not necessary to show the parentheses in the tree; the structure of the tree for a+(7*b) would be different.
A parser is a program that converts text such as program source code into a tree; hence these trees are called parse trees.
Binary parse trees are adequate for the representation of most programming language constructs, but it is sometimes desirable to use ternary trees – for example a tree for an if…then…else… statement could have three children, the expression and the two statements. We could, however, represent this as a binary tree with the two statements being stored as grandchildren.
18/02/2020 CE204 Part 6
3
Parse Trees in Java 1
A node in a parse tree needs to hold two pieces of information – the kind of node (e.g. a number, identifier or operator) and its value (e.g. 7, myId, or plus). Since the latter can have various types we need to be able to store different types of value in the different kinds of nodes. Two approaches are possible in Java – we can use the Object class to store the value, or declare the node type as an abstract class with subclasses for each kind of node, with each subclass having a different type for the value.
18/02/2020 CE204 Part 6
4
Parse Trees in Java 2
Using the first approach we would store the kind of node as an integer (e.g. 0 for number nodes, 1 for identifier nodes and 2 for operator nodes). In order to make programs readable we should enumerate as constants the values used to represent each kind of node. The following slide shows an outline of the class declaration for this approach.
18/02/2020 CE204 Part 6
5
Parse Trees in Java 3
public class ParseTree
{ private int kind;
private Object value;
private ParseTree lChild, rChild;
public static final int numNode = 0,
idNode = 1, opNode = 2;
public ParseTree(int knd, Object val, ParseTree l, ParseTree r)
{ kind = knd; value = val;
lChild = l; rChild = r;
}
// methods to examine the node needed }
18/02/2020 CE204 Part 6
6
Parse Trees in Java 4
If we choose the abstract class approach for representing parse trees it is not necessary to store the kind in the node since this can be determined using the instanceof operator. However, if there are many kinds of node we might decide to store the kind so that a switch statement could be used instead of many if statements.
Assuming that the kind is not being stored, the declaration of the abstract class might take the form shown on the next slide. The instance variables have been declared as protected so that the constructors of the subclasses can access them.
18/02/2020 CE204 Part 6
7
Parse Trees in Java 5
public abstract class ParseTree
{ protected ParseTree lChild, rChild;
public ParseTree leftChild() { return lChild;
}
public ParseTree rightChild() { return rChild;
}
public abstract String toString();
}
18/02/2020 CE204 Part 6
8
Parse Trees in Java 6
A class that extends the abstract class ParseTree would then be written for each kind of node that can occur in a parse tree.
These classes would inherit the child-access methods of the abstract class but would have constructors and value-returning methods appropriate to the type of data that they store. The constructors for leaf nodes, such as numbers, would have only one argument, the value to be stored in the node, but those for non-leaf nodes, such as operators, would need the children as extra arguments.
An example is seen on the next slide. 18/02/2020 CE204 Part 6
9
Parse Trees in Java 7
class NumNode extends ParseTree
{ private int value;
public NumNode(int val)
{ lChild = rChild = null; // it’s a leaf
value = val; }
public int numValue() { return value;
}
public String toString() { return “”+value;
}
}
18/02/2020 CE204 Part 6
10