[antlr-interest] Bug in ASTFactory.cpp, version 2.7.3

Waldemar Sauer waldemarsauer at hotmail.com
Thu Dec 23 23:57:58 PST 2004


Hi there
 
I am bumping into some infinite loops in ASTFactory.cpp, and I was
wondering if this is a bug in that code, or if there is maybe something
about the antlr grammar that I'm not understanding. I think rather the
former, because the compiled compiler should never run into an infinite
loop, but rather cast exceptions if there are problems that it is
experiencing.
 
One grammar fragment that is causing this is as follows:
primaryExpr:
        literal_value 
      | id:ident (ap:actualParams)? {
            if (#ap.get() != NULL) {
                  #primaryExpr = #([MEM_CALL, "MEM_CALL"], #id, #ap);
            } else {
                  #primaryExpr = #id;
            } // if
        }
      // array index, post-increment, post-decrement, typeof, checked,
unchecked, and
      // new.
      //    new has it's own challenges, in that we have to call
"release" when
      //    the object goes out of scope.
      ;
 
actualParams!: LPAREN (apl:actualParamList)? RPAREN {
      #actualParams = #([APARAMS, "APARAMS"], #apl);
};
actualParamList: expression (COMMA^ expression)*
 
Like I said, I've seen this problem before, and usually there is a way I
can get out of it by redefining what I would like to be doing, just in
this case, I haven't found the workaround in the grammar yet.
 
It seems as though the "#primaryExpr = #([MEM_CALL ." expression is
generating a list of AST nodes by using the ASTArray::add function to
add AST nodes to itself as the compiled code of the above statement
demonstrates:
      primaryExpr_AST =
ANTLR_USE_NAMESPACE(antlr)RefAST(astFactory->make((new
ANTLR_USE_NAMESPACE(antlr)ASTArray(3))->add(astFactory->create(MEM_CALL,
"MEM_CALL"))->add(id_AST)->add(ap_AST)));
The right sibling of the id_AST node is the ap_AST node by the time
ASTFactory::make is called. ASTFactory::make then has code that turns
the nodes in the list (nodes parameter to ASTFactory::make) into
siblings of a tree node (local parameter 'root'). The problem is that
ap_AST becomes it's own right sibling, and the code that searches for
the last sibling in the list ("// RK: I cannot fathom why this missing
check didn't bite anyone else") then runs into an infinite loop.
 
I resolved the issue by patching the ASTFactory::make code to check for
this condition (see end of posting), but I need someone to look at the
code, and say if it is the right thing to do, or if there is an issue
with my definition of the grammar.
 
Thanks in advance
 - Waldemar
 
 
 
----------------- 8< -----------------------------------------
/** Make a tree from a list of nodes.  The first element in the
 * array is the root.  If the root is null, then the tree is
 * a simple list not a tree.  Handles null children nodes correctly.
 * For example, make(a, b, null, c) yields tree (a b c).  make(null,a,b)
 * yields tree (nil a b).
 */
RefAST ASTFactory::make(ANTLR_USE_NAMESPACE(std)vector<RefAST>& nodes)
{
      if ( nodes.size() == 0 )
            return RefAST(nullASTptr);
 
      RefAST root = nodes[0];
      RefAST tail = RefAST(nullASTptr);
 
      if( root )
            root->setFirstChild(RefAST(nullASTptr));  // don't leave any
old pointers set
 
      // link in children;
      for(unsigned int i = 1; i < nodes.size(); i++ )
      {
            if ( nodes[i] == 0 )          // ignore null nodes
                  continue;
 
            if ( root == 0 )              // Set the root and set it up
for a flat list
                  root = tail = nodes[i];
            else if ( tail == 0 )
            {
                  root->setFirstChild(nodes[i]);
                  tail = root->getFirstChild();
            }
            else
            {
                  tail->setNextSibling(nodes[i]);
                  tail = tail->getNextSibling();
            }
 
            if( tail )  // RK: I cannot fathom why this missing check
didn't bite anyone else...
            {
                  // Chase tail to last sibling, 
                  //    but stop if the tail's sibling is in nodes
                  RefAST node;
                  while (node = tail->getNextSibling()) {
                        bool found = false;
                        for (unsigned int j=0; j<nodes.size(); j++) {
                              if ((i != j) && (node == nodes[j])) {
                                    found = true;
                                    break;
                              } // if
                        } // for
                        if (found)
                              break; // stop further traversal. We
either have dealt with this node, or will still deal with it.
                        tail = node;
                  }
            }
      }
 
      return root;
}
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20041224/3031b591/attachment-0001.html


More information about the antlr-interest mailing list