java - 在抽象语法树中搜索特定节点

Question

我正在尝试搜索 AST(抽象语法树)中的特定节点。基本思想是:

• 从源代码解析出一个 AST，包含大约 10000 个节点。
• 我想在 AST 中搜索 50 个项目的列表。

问题:在 AST 中搜索这 50 个项目的最佳方式是什么？

现在，我正在考虑使用包含这 50 个项目的 Arraylist。然后，遍历 AST 并使用循环将每个节点与 Arraylist 进行比较。就性能而言，这是个好主意吗？我希望手术尽快完成。还有其他方法可以解决这个问题吗？

Answer 1

我不会使用 Arralylist，因为它要求您每次都扫描它，而这只是开销。您可以轻松地将 50 个谓词编写为“p1 或 p2 或 ....”。

您可以搜索树一次，应用 50 个谓词来确定是否有感兴趣的节点，也可以搜索树 50 次，在每个单独的过程中应用一个谓词。在这两种情况下，您都必须运行谓词，因此它们不会以任何方式改变成本(请注意下面)。

如果搜索一次，则需要将 50 个谓词的答案“或”在一起，需要 49 个 or，因此额外成本为 49*[OR 成本][节点数]。如果搜索50，则额外成本为49[访问树节点的成本]*[节点数]。那么，问题是“或”的成本是否小于“访问树节点”的成本。 “或”在大多数机器上相当快，因为​​它只使用可能已经在缓存中的寄存器和值。访问树节点可能非常快，但可能需要多条指令；更糟糕的是，它触及内存。如果您的树足够大，无法放入缓存，并且谓词很便宜，那么您的 search-50 成本可能会由内存访问时间主导。

现在，我们可以用一些有趣的方式“作弊”。首先，可能是谓词之间存在某种关系；如果谓词 A 暗示谓词 B，我可以先检查 B，如果为假，我不必测试 A。这可以减少“或”的数量，但对树访问没有帮助。其次，谓词可能共享子测试，例如谓词A实际上是“a1和a2”，而B实际上是“a1和a2”；在这种情况下，您可以对谓词进行因式分解并评估子谓词更少的次数；每个节点只需评估“a1”一次。对于多次扫描技术来说，这并不是那么容易做到的。某些谓词失败可能意味着不需要搜索子树；这里，50 次搜索可能会更快，因为每次搜索只会检查必要的子树，其中搜索一次几乎需要搜索到所有谓词都同意作为停止点的节点。

但是，对于每个谓词，您的程序可能希望做出不同的 react 。所以你的程序结构实际上是一组“if p1(node) then a1(node)”。如果谓词成本低廉并且触发频率相对较高，则操作可能会成为主要成本(比导航树节点更昂贵)，那么无论哪种技术在性能方面都很好。

最后，如果谓词和操作很复杂，您可能无法轻松猜出哪个更便宜。很好，对这两个搜索进行编码(并不难)并根据实际数据进行测量。