[antlr-interest] Complaints about BaseAST implementation

Andy Tripp atripp at jazillian.com
Wed Oct 12 07:02:24 PDT 2005


Akhilesh,

All ranting aside, I don't see how BaseAST can implement AST
and thus provide methods like getFirstChild() and getNextSibling() without
having any fields. Can you say specifically how that can be done?

You say:

  By putting fields, freedom is taken away from
  implementer how exactly the nodes will be connected to
  each other.

But BaseAST itself implements the tree relationships, not
your subclass. If you want to do that yourself, you shouldn't
be subclassing BaseAST.

Andy

Akhilesh Mritunjai wrote:

>Hi Andy
>
>Having the fields is wrong due to a primary reason
>that  adding fields violates the design principle with
>which the class was created.
>
>   BaseAST was clearly  created with the right
>decision to implement common algorithms.  Thats why
>its abstract. Algorithms, ideally, don't depend on how
>the data is stored and design is said to be solid if
>interface provides methods through which they can be
>implemented. The methods are there in AST interface!
>
>By putting fields, freedom is taken away from
>implementer how exactly the nodes will be connected to
>each other. eg. Some person may want to have constant
>time access to any given child of a node, which
>current  fields can't satisfy. So they are left unused
>(BAD!), when implementer adds the particular
>methods/fields.
>
>I am against the idea that a class meant to hold
>algorithms should dictate in any way how the data is
>supposed to be stored.
>
>So, either all classes deriving from BaseAST should
>implement get/set child/sibling AND get/set text/type,
>OR a minimal concrete class can be provided that
>derives from BaseAST (other classes derive from this
>concrete class) and implements node connectivity
>(right/down) and returns empty string and 0
>respectively for getText() and getType(). Again,
>implementing them in BaseAST is incorrect. It is an
>abstract class and *must not* have any say in things
>it  has no info about.
>
>Now about why having useless fields is bad (in case
>implementer decides to store connectivity info
>differently, for example) is that the 8 extra bytes
>(two fields, x86 32bit platform) start to matter when
>you have multi-million node tree and 8 bytes is like
>20% of total node size.
>
>Thanks for listening. You folks have done some damn
>good work. I'm ranting about this stuff because I feel
>ANTLR can and should be perfect. Its one of the very
>few softwares I've found to be so good!
>
>Thanks and Regards
>- Akhilesh
>
>
>
>--- Andy Tripp <atripp at jazillian.com> wrote:
>
>  
>
>>I guess I'm missing something here. How is it that
>>the BaseAST class doesn't
>>need "down" and "right" variables. It's the base
>>class for all ASTs, and it
>>needs to implement the various tree functions
>>functions (addChild, 
>>getNumberOfChildren,
>>etc). How can it provide that functionality without
>>having those fields?
>>
>>Andy
>>
>>Akhilesh Mritunjai wrote:
>>
>>    
>>
>>>Hi
>>>
>>>The problem is bit more than that. If the fields
>>>      
>>>
>>are
>>    
>>
>>>removed from BaseAST (there is no reason for them
>>>      
>>>
>>to
>>    
>>
>>>be there), following classes are affected:
>>>
>>>BaseAST
>>>CommonAST
>>>ParserTree
>>>ParseTreeRule
>>>ParseTreeToken
>>>
>>>I finally forked the code, and made changesin ANTLR
>>>rather than copying/pasting the algorithms and
>>>      
>>>
>>making
>>    
>>
>>>a new MyBaseAST class that I might need to update
>>>everytime a new release comes over. And I figured
>>>      
>>>
>>that
>>    
>>
>>>I can submit the diffs to Terence after I test it.
>>>
>>>In our testing so far, there haven't been any
>>>problems. The fix works like a charm and now our
>>>appliction handles multi-million node trees with
>>>default heap settings :-)
>>>
>>>- Akhilesh
>>>
>>>--- Andy Tripp <atripp at jazillian.com> wrote:
>>> 
>>>
>>>      
>>>
>>>>Looks to me that the only places where the "right"
>>>>and "down" fields are 
>>>>misused are in
>>>>the addChild() and getNumberOfChildren() methods
>>>>        
>>>>
>>of
>>    
>>
>>>>BaseAST.
>>>>Here is what they should look like:
>>>>
>>>>/**Add a node to the end of the child list for
>>>>        
>>>>
>>this
>>    
>>
>>>>node */
>>>>   public void addChild(AST node) {
>>>>       if (node == null) return;
>>>>       BaseAST t = getFirstChild();
>>>>       if (t != null) {
>>>>           while (t.right != null) {
>>>>               t = t.getNextSibling();
>>>>           }
>>>>           t.right = (BaseAST)node;
>>>>       }
>>>>       else {
>>>>           this.down = (BaseAST)node;
>>>>       }
>>>>   }
>>>>
>>>>   /** How many children does this node have? */
>>>>   public int getNumberOfChildren() {
>>>>       BaseAST t = getFirstChild();
>>>>       int n = 0;
>>>>       if (t != null) {
>>>>           n = 1;
>>>>           while (t.getNextSibling() != null) {
>>>>               t = t.getNextSibling();
>>>>               n++;
>>>>           }
>>>>           return n;
>>>>       }
>>>>       return n;
>>>>   }
>>>>
>>>>
>>>>   
>>>>
>>>>        
>>>>
>>>
>>>		
>>>__________________________________ 
>>>Yahoo! Music Unlimited 
>>>Access over 1 million songs. Try it free.
>>>http://music.yahoo.com/unlimited/
>>>
>>> 
>>>
>>>      
>>>
>
>
>
>		
>__________________________________ 
>Yahoo! Music Unlimited 
>Access over 1 million songs. Try it free.
>http://music.yahoo.com/unlimited/
>
>  
>


More information about the antlr-interest mailing list