Can you explain ANTLR's tree construction facilities?

ANTLR v3 has moved away from using the ANTLR v2 child-sibling trees for the common tree implementation. Instead, ANTLR v3 uses a simple list-of-children approach by default. To avoid locking everyone into the same implementation, ANTLR uses an approach similar to the TreeModel in Java's Swing tree viewing classes. All tree nodes are of type Object and an adaptor, TreeAdaptor, indicates how to create nodes and constructs trees--ANTLR does not care about the type at all.

ANTLR builds trees when you use the option output=AST.

grammar T;
options {output=AST;}
a : ID INT;
ID : 'a'..'z'+ ;
INT : '0'..'9'+;
WS : (' '|'\n') {channel=99;} ;

By default, a CommonTreeAdaptor is created for the parser:

protected TreeAdaptor adaptor = new CommonTreeAdaptor();

The generated code for rule a() has calls to the adaptor to construct nodes and add them to the current rules subtree:

root_0 = (Object)adaptor.nil();
ID1=(Token)input.LT(1);
match(input,ID,FOLLOW_ID_in_a16); 
ID1_tree = (Object)adaptor.create(ID1);
adaptor.addChild(root_0, ID1_tree);
INT2=(Token)input.LT(1);
match(input,INT,FOLLOW_INT_in_a18); 
INT2_tree = (Object)adaptor.create(INT2);
adaptor.addChild(root_0, INT2_tree);

A nil node is used to hold a flat tree--a list of children. Here, ID and INT nodes are created and added to the nil root_0. Before returning the tree, a rule does some postprocessing:

retval.tree = (Object)adaptor.rulePostProcessing(root_0);
adaptor.setTokenBoundaries(retval.tree, retval.start, retval.stop);

An important advantage that v3 has over v2 is that v3 automatically computes and stores the range of tokens associated with the subtree created for each rule.