ANTLR AST树-寻找特定节点

Question

我有一个基于解析器语法构建的AST。现在我想搜索树来确定树中是否存在特定节点。最好的方法是什么？

a) 编写带有关联操作的树形语法以遍历树来标记特定节点的存在。问题是我必须为可能感兴趣的每个节点类型编写一棵树形语法。

b) 通过递归获取子节点并检查 Token.Text，来深入遍历 CommonTree，以确定是否遇到特定节点类型。有没有可用的工具来实现这个？

谢谢 Vijay

- user389913

Answer 1

这两种方法都是有效的。如果要为其他目的编写一棵树形语法（如求值），可以直接复制该语法并为其命名，然后在该树形语法中检查特定节点的存在。

据我所知，没有可用于手动“遍历”（树形结构的）一小部分的实用程序，因为它是一个琐碎的操作（伪代码）：

walk(Tree) {

  if Tree is null {
    return
  }

  inspect the Tree (node) type

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

编辑

经过一番思考，我想起了一些新的功能，它们或多或少可以满足您的需求。您要查找的ANTLR术语是“树模式匹配”。

引用："与指定整个树语法不同，树模式匹配器让我们专注于我们关心的子树。-- http://www.antlr.org/wiki/display/ANTLR3/Tree+pattern+matching "

请注意，您需要使用ANTLR 3.2+才能使用此功能。

- Bart Kiers

---

虽然微不足道，但是如此常见，我很惊讶居然没有一个“实用程序”。我的程序转换工具有一组“FindFirstNode”、“WhereConditionDo”等函数，它们接受一棵树、一个谓词来检测所需的节点以及一个在找到这些节点时要执行的操作函数。这些函数非常方便。 - Ira Baxter

@Ira，是的，稍微考虑了一下，我可以看出这样的东西有用。请注意，使用ANTLR在解析器语法的AST创建过程中重写/插入标记或树是可能的，但它不像你提到的那么灵活。 - Bart Kiers

@Ira，看一下编辑。毕竟还是有可能的。 - Bart Kiers