算法的名称 - AST中的匹配子树

Question

我有一组S"小"树S[i] ,我需要找到它们在更大的内部的位置, 这些树被用作模式以在更大的树中找到匹配的子树T.我知道S在开始构建之前T(这是一个解析树),所以我正在考虑使用切割平面方法来匹配节点(因为解析器生成CST).

中的树S不是相同的AST T- 想想XPath与XML - S保存XPath 的树表示,T而是源代码的实际AST - 我需要映射i和匹配节点的向量T.

但是我不确定我会使用的算法的名称.

基本上我知道我想要做的,感觉就像一个" 分而治之的树"用栈,我持有可能的候选人进行匹配,在LALR解析器每班我重复堆栈的顶部,消除考生i从S[i]其中无论如何都不会匹配,并且在减少后我从堆栈中弹出.最初,所有成员S都是可能的候选人.

请注意:这只是AST,ASG是另一个故事......

附录

这是一个解析树T.

解析函数将以规范形式(也表示为树)存储在其中,知道我称之为"树路径"的列表S.但它们看起来不像parsetree,它们有自己的语言可供表示,类似于XPath.

用于获取具有变量返回值的所有函数的树路径示例:

function[body[return[expr[@type="variable"]]]]]

1. 那么我应该在现有文献中寻找什么呢？
2. 还有其他任何建议吗？
3. 是否已有可以查询元注释树的语言？开源C(而不是C++)库是理想的.

Answer 1

1）你的S树作为XPath对应于一些T树。为什么不提前构造T树，然后进行模式匹配呢？

2）如果您想将模式与结构进行匹配，您可以想象将模式编译为某种状态机，当树的给定部分进行匹配时，状态机就会进行转换。如果状态机进入接受状态，则您已找到匹配项。如果您有多个模式，则每个模式都可以视为状态机，并且您可以“并行”运行它们（通过模拟）。为了提高效率，请计算所有状态机的叉积；现在只有一个，并且每个输入仅发生一次转换。我将这个想法称为“模式产品”，您会在各种高效匹配器中看到类似的东西。与您想要做的最接近的一种算法是Rete 算法，它会在输入的数据发生变化时跟踪哪些“模式”是实时的。