[antlr-interest] Caution in 2.7.1: BaseAST

gidadoifiok gidadoifiok at yahoo.com
Thu Jan 17 11:12:18 PST 2002

I'm not sure if this was fixed in 2.7.2, but I'll just bring
it up quickly.  I only ran across this, because I could not
decipher the tree-data-structure from the guide, nor from the
AST javadoc.

Here's a method, addChild(AST), in BaseAST.  Note that there
are many casts of AST to BaseAST.  How about when someone
provides their own implementation of AST (that does not
extend BaseAST)?  That will certianly break this code with
a ClassCastException.

    protected BaseAST down;
    protected BaseAST right;

    /**Add a node to the end of the child list for this node */
    public void addChild(AST node) {
	if ( node==null ) return;
	BaseAST t = this.down;
	if ( t!=null ) {
	    while ( t.right!=null ) {
		t = t.right;
	    t.right = (BaseAST)node;
	else {
	    this.down = (BaseAST)node;

In thinking about it, I came up with several solutions
that could work, but they depends on the accessiblity
of this code.  Are methods like addChild() only used by
parser?  Then perhaps take it out of AST, and make it
private/package-local in BaseAST.  This way, you know
that you're only going to add BaseAST (or its derivatives),
and your class-casting will work.

On the other hand, if developers outside the parser can
addChild() to an AST (saying their descending an AST),
well then it needs to be in the interface, but then you
cannot guarantee that the AST that a developer adds will
be of type BaseAST.  If this were the case, you could do:

    protected AST down;
    protected AST right;

    public void addChild(AST node) {
	if ( node==null ) return;
	AST t = this.down;
	if ( t!=null ) {
	    while ( t.right!=null ) {
		t = t.right;
	    t.right = node;
	else {
	    this.down = node;

But then of course, you run into problems here in doWorkForAll()

		if ( sibling.getFirstChild()!=null ) {
		    ((BaseAST)sibling.getFirstChild()).doWorkForFindAll(v, target,

Here's the big problem:  BaseAST implies a data-structure (
parent-children) because it has an implementation.  AST does
not imply a data-structure, because it is an implementation-less

How can you get around this?  Here is a suggestion:
   Make AST into a class (rather than an interface).
   Basically renaming BaseAST to AST.  Then whoever whats to do
   their own AST, can just extend AST, and override the methods
   that they want.  They may need to you want to make AST a class
   with default behavior.

   On the plus side, you can quickly access (package local) fields
   rather than calling accessor methods getFirstChild() and

   The problems that will arise is that custom AST will get bulky
   (because of creating the AST object), and the methods are 
   interrelated, so the custom AST would likely have to override
   all the methods so that the custom-AST data-structure is properly
   accessed.  For all that work, might as well implement an interface
   and save the cost of creating an (inherited) AST object.

Anyway, this is something that someone close (in understanding/
developing) the code should sort out.  If you leave it, then some
documentation (at the very least) of what might break would be

- Gidado


Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 

More information about the antlr-interest mailing list