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

jw9315 jw9315 at bris.ac.uk
Mon May 5 15:45:14 PDT 2003


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/ 




More information about the antlr-interest mailing list