[antlr-interest] Recursive Tree Walking C Target

Kenneth Domino kenneth.domino at domemtech.com
Fri Sep 10 09:14:48 PDT 2010


> Just wondering if anyone had any tips for recursively walking an
> ANTLR_BASE_TREE produced from a parser. I seem to be getting some memory
> issues.

FYI, I transform the Antlr tree into my own C++ data structure for tree 
walking.
E.g.,

#pragma once
#include <vector>
class TREE
{
public:
   int GetType();
   char * GetText();
   TREE * GetChild(int index);
   int GetChildCount();
   void SetText(char * text);
   void SetType(int type);
   void AddChild(TREE * child);
private:
   std::vector<TREE*> children;
   int type;
   char * text;
};

and,

// Convert an Antlr tree into TREE data structure.
TREE * convert(pANTLR3_BASE_TREE node)
{
   TREE * result = new TREE();
   char * text =
     CUDA_EMULATOR::Singleton()->StringTableEntry(
            (char*)node->getText(node)->chars);
   result->SetText(text);
   int type = node->getType(node);
   result->SetType(type);
   for (int i = 0; i < (int)node->getChildCount(node); ++i)
   {
      pANTLR3_BASE_TREE child = (pANTLR3_BASE_TREE)node->getChild(node, i);
      TREE * c = convert(child);
      result->AddChild(c);
   }
   return result;
}

...
   pANTLR3_BASE_TREE tree = langAST.tree;
   TREE * result = convert(tree);
...

With this conversion, I can now do things more easily, because I don't use
the Antlr C runtime data structures, which are hard for me to understand and
debug.  (I still cannot understand why the target isn't just C++.)  I can 
now
add an iterator for tree walking, or change the behavior of getText(), which
allocates a new copy of the string everytime it is called.
In addition, in my tree walker I need to associate associate some data
with each node. I could create a std::map<pANTLR3_BASE_TREE, DATA *>
but this was slow because of all the thousands of nodes.
Alternatively, I could have tried to modify the default node
type in tree construction, but I could not find an example to make my life
easier, and I am not motivated enough to read and understand
"newPoolTree (pANTLR3_ARBORETUM factory)" in antlr3commontree.c.
The examples in http://www.antlr.org/download/examples-v3.tar.gz, via
http://antlr.org/download.html, are not that useful.
And although there was some discussion of default node type construction in
the C target in the past (
http://antlr.markmail.org/message/cqhgi7dzc36ntl6n?q=%2Btree+%2Badaptor+c+target
http://antlr.markmail.org/message/eryizmbwlsxzlswf?q=%2Btree+node++default+c
http://antlr.markmail.org/message/nh5ws6vqxt3zjpwa?q=tree+node++default+c+custom
), it is not concrete enough for me.

Ken
 



More information about the antlr-interest mailing list