[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