Internal Representation of AHEAD Abstract Syntax Trees/Parse Trees

This section presents the low-level, programmatic capabilities AHEAD offers for creating and manipulating abstract-syntax trees (ASTs) of Java and extended-Java programs.  While the discussion centers on Java dialects, the basic technology applies to all AHEAD-produced languages.

AHEAD relies on a hierarchy of different kinds of AST nodes.  The kernel hierarchy is shown in the figure below, where AstNode is the root of the AST class hierarchy; all tokens are instances of AstToken.

Note that all Bali-generated classes are subclasses of AstNode.

An AstNode has an array (arg) of zero of more children (of type AstNode), a left and right to connect a node with its siblings, and an up pointer to its parent. Not depicted is an array (tok) of zero or more tokens.  The up pointer is null if an AST node has no parent; left is null if there is no left sibling, and similarly for right.  A terminal node of an AST has (obviously) zero children; the arg array is null.

In general, programmers need not know about these pointers, although it may be useful information.  The code below sketches the definition of the AstNode class (which is defined in the kernel layer).

static public abstract class AstNode implements Cloneable, Serializable {

   public Token[]     tok;
   public AstNode[]   arg;
   public AstNode     right;
   public AstNode     left;
   public AstNode     up;
   ...
}

AST classes are generated from Bali grammar specifications. Consider a Bali production that is a named rule:

NonTerm1
        : TOKEN1 NonTerm2 TOKEN2 TOKEN3 NonTerm3 :: AClass
        ;

Bali generates a class called AClass that is instantiated whenever the pattern associated with AClass is recognized.  The AST that is produced is shown to the right: an instance of AClass roots an AST that has two children: an instance of NonTerm2 and an instance of NonTerm3 (both objects of which are siblings of each other).  The contents of the arg[] array and tok[] array is:

arg[0] = // pointer to NonTerm2 instance
arg[1] = // pointer to NonTerm3 instance

tok[0] = // pointer to TOKEN1 instance
tok[1] = // pointer to TOKEN2 instance
tok[2] = // pointer to TOKEN3 instance

How an AST is printed can be answered in two levels of detail. In the most detailed, we'll see the information that is stored within an AST node for printing. In the more typical interpretation, click here to see the standard idioms to use when programming in AHEAD.

In order to print the AST rooted at the AClass node (or any node for that matter), we need to be able to print each subtree and each of the nodes tokens in the order prescribed by the AClass named rule.  This is accomplished by a boolean array order[] which specifies the interweaving of token and subtree printing.  In the AClass example above:

boolean order[] = { true, false, true, true, false };

That is, order[0] means print the first token (tok[0]), order[1] means print the first subtree (arg[0]), order[2] means print the second token (tok[1]), and so on.  The order array is generated by Bali and is otherwise unseen by users.

Note also that tokens store both the text of the token plus the white space (comments, new lines, etc.) that preceded the token during a parse.  In this way, it is possible for AHEAD-produced precompilers to parse an input file and unparse it to produce an output file that is Unix-diff equivalent to the input file.  (Stated another way, saving the white space allows one to transform programs while retaining comments.  This is essential for tools that automatically modify programs which are subsequently hand-edited by programmers).

Below are methods that are useful for tokens.  These methods are invoked by the pattern tok[i].method() -- meaning apply method() to token #i:

In general, AHEAD allows no sharing of AST subtrees - i.e., multiple parent nodes point to the same child AST subtree.  Now, sharing subtrees is too easy to do in AHEAD metaprogramming:

AST_Exp e = exp{ 4+5 }exp;
AST_Stmt s = stm{ System.out.println( $exp(e), $exp(e)); }stm; //sharing!

The above code is not correct if it is to be subsequently manipulated.  (If it is merely to be printed, then tree sharing is OK).  One fix to the above code would be to clone each AST before linking it in. 

AST_Exp e1 = (AST_Exp) e.clone();
AST_Stmt s = stm{ System.out.println( $exp(e), $exp(e1)); }stm;

Another and simpler is to normalize the tree.   The normalize method walks a tree and locates shared subtrees; it clones each shared subtree so that the resulting AST has no tree sharing.

AST_Exp e = exp{ 4+5 }exp;
AST_Stmt s = stm{ System.out.println( $exp(e), $exp(e)); }stm; //sharing!
s.normalize();       // tree sharing removed

Occasionally it is useful to detach a subtree from an AST.   (That is, all parent and sibling linkages are removed). A typical application is that the detached tree is to be serialized to disk for some later retrieval and manipulation.   The following idiom illustrates the usage of Detach.

// let a be the node that is to be detached from an AST
// and is to be written to file "myfile"

a.Detach();
a.writeTree("myfile");

The following are methods that can be performed on AST nodes.

 AHEAD Home Page

Copyright © Software Systems Generator Research Group. All rights reserved.
Revised: April 17, 2003.