ANTLR AST tree - searching for specific nodes

I have an AST built 开发者_如何学运维based on a parser grammar. Now I want to search the tree to determine if specific nodes are present in the tree or not. What is the best way to do this?

a) Write a tree grammar with associated actions to traverse the tree to mark presence of specific nodes. The problem with this is that I have to write a tree grammar for every node type that I may be interested in searching for

b) Problematically traverse CommonTree by recursively getting children and checking Token.Text to determine if a specific node type is encountered. Any utilities available for this?

Thanks

Vijay

Both are valid options. If you're going to write a tree grammar for other purposes (evaluating?), you could simply copy that grammar and give it a different name and check in that tree grammar for the presence of specific nodes.

AFAIK, there are no utilities available for manually "walking" (a small part of) the tree , nor is there much need for it since it is a trivial operation (pseudo code):

walk(Tree) {

  if Tree is null {
    return
  }

  inspect the Tree (node) type

  for every Child in Tree.getChildren() {
    walk(Child)
  }
}

EDIT

After thinking a bit more about it, I remembered some new feature that more or less does what you want. The ANTLR term you're looking for is "tree pattern matching".

Quote: "Instead of specifying an entire tree grammar, a tree pattern matcher lets us focus on just those subtrees we care about. -- http://www.antlr.org/wiki/display/ANTLR3/Tree+pattern+matching "

Be aware that you need ANTLR 3.2+ for this.