An AST is a simplified representation of the parse tree. Parse trees can have many nodes in them that are not necessary in indicating the semantics of the parsed text. For example, if you had the following grammar (as pointless as it may be):
| A ::= B; B ::= C; C ::= Constant; Constant ::= tknInteger; |
Then a parse tree for the string "123" would look something like what is shown below:
| A | B | Constant | 123 |
Where Constant is a node holding the value of the tknInteger terminal. As you can see, in this case, there is really no reason to have the nodes for A, B, and C in the tree, since all occurrences of the tknInteger token must go through that sequence of derivations. Therefore, an AST representation of this example would only need to have the Constant node and its child which holds the value. For example,
| Constant | 123 |
One thing to note is that if a Constant node always only has one child which is the actual value of the lexeme, then you could even have the Constant node just contain the value of the lexeme as a member field (instance variable) instead of having the value in its own separate node. (In fact, this is probably the easier way to do it so that you will not need to create as many extra node classes).
This simple example shows the reason why many times ASTs are more desirable than the actual parse tree. ASTs do not have the extraneous nodes which do not add anything to the meaning. This makes working with an AST simpler than working with a parse tree.
Now, how are ASTs constructed? Well, you definitely need to have a class that defines an AST node, and having a separate class for each of the possible AST node types will make the interpreter assignment more understandable and cleaner.
You will need to consider what kind of operations the node classes will need to support and the class hierarchy for defining specialized AST node types. Since you are building a tree, some of the standard tree operations will be needed such as inserting a child or multiple children, and retrieving the children. You should note here that ASTs are not necessarily binary trees, since there could be rules in the grammar that would require an AST node to have many children. Thus, you will need to have a resizable data structure to store the pointers to the children. In Java, the java.util.Vector or java.util.ArrayList class is the easiest data structure to use for this (note that ArrayList is "unsynchronized," but this should not cause a problem in single thread code.