[antlr-interest] Re: AST algorithm stuck in infinite loop?

[Terence Parr]

Hi.  Most likely, your tree is not a tree, but a DAG ;)  It was perhaps 
improperly built and has a child or sibling "back" link. :)

Ter

On Monday, May 5, 2003, at 06:56  AM, jw9315 wrote:

> Apologies, the algorithm was not stuck in a loop, it was just taking
> so long to complete that I did not notice! It still seems to go
> through the same branch many times though, I was wondering if it was
> meant to do this, or it was an error in the implementation of the
> algorithm?
> Thanks,
> Jon
>
> --- In antlr-interest at yahoogroups.com, "jw9315" <jw9315 at b...> wrote:
>> Hi,
>> I implemented the following algorithm to walk an AST as suggested
> by
>> a member of this group:
>>
>> // Start
>> void visit( AST tree )
>>  {
>>          AST child = tree.getFirstChild();
>>          System.out.println("_" + child);
>>          // Test to see if node has a child
>>          if( child != null)
>> 	 {
>> 		 System.out.println(child);
>>                  // Call method recursively
>> 		 visit( child );
>> 	 }
>>          // Else there were no children
>>          AST sibling = tree.getNextSibling();
>>          while( sibling != null)
>> 	 {
>> 	 	System.out.println(sibling);
>> 		visit( sibling );
>> 		sibling = sibling .getNextSibling();
>>  }
>> // End
>>
>> However, I find that this enters an infinite loop and prints the
> tree
>> out over and over again. Have I implemented the algorithm
> correctly,
>> and if so, could someone tell me how to test for the fact that I
> have
>> walked the whole tree? Is there a special command for this?
>> Thanks in advance,
>> Jon
>
>
>
>
> Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/
>
>
>
--
Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org
Co-founder, http://www.peerscope.com link sharing, pure-n-simple
Lecturer in Comp. Sci., University of San Francisco


 

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