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

[Terence Parr]

Ok, i see the problem now.  You are asking it to walk the sibling list 
and then each visit walks the same sibling list.

See the antlr tree classes for things like toStringList and 
toStringTree; they should be doing the tree walk properly. :)

Ter

On Monday, May 5, 2003, at 03:45 PM, jw9315 wrote:

> Hi All,
> I'm pretty sure that my tree is a tree and not a Directed Acyclic
> Graph, because I am using the tree grammars from the example
> directory in ANTLR, so I have not coded it myself, I am just running
> the algorithm below on the AST in memory from the example program,
> but I can't figure out why it goes over itself so many times before
> stopping? Should it not do each branch of the tree just once? This is
> messing up the interpretation that I am trying to do in the tree...
> Thanks in advance,
> Jon
>
> --- In antlr-interest at yahoogroups.com, Terence Parr <parrt at j...>
> wrote:
>> 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/
>
>


 

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