算法的名称

 

我有一组S “小”的树S[i] ，我需要找到它们的位置在一个更大的内部，用作模式来在更大的树T 找到匹配的子树。 在开始构造T （它是一个分析树）之前，我知道S ，因此我正在考虑采用切平面方法来匹配节点（因为解析器会生成CST）。

S中的树与T不相同 - 考虑XPath与XML - S保存XPath的树形表示，而T是源代码的实际AST - 我需要在i和匹配节点的向量之间映射T

不过，我不确定我将使用的算法的名称。

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

请注意：这只是关于AST，ASG是另一个故事......

附录

这里是一个分析树T

T - 分析树

解析函数将会知道我称之为“树路径”的列表，这是一种规范形式，也被表示为树，存储在S 。 但它们看起来不像分析树，它们有自己的语言来表示，类似于XPath。

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

function[body[return[expr[@type="variable"]]]]]
  • 那么在现有文献中我应该寻找什么？
  • 任何其他建议？
  • 是否有语言可以查询这样的元注释树？ 一个开源的C（而不是C ++）库是理想的。

    • 1）您的S树作为XPath对应于某些T树。 为什么不提前构建T树，然后模式匹配它们？

    2）如果你想匹配一个结构的模式，你可以想象将模式编译成某种状态机，当给定的树被匹配时，这种状态机会转换。 如果状态机曾经进入接受状态，你已经找到了一个匹配。 如果您有多个模式，则每个模式都可以视为状态机，并且可以“并行”（通过模拟）运行它们。 为了达到这个效率，计算所有状态机的交叉乘积; 现在只有一个，每个输入只发生一次转换。 我称之为“模式产品”这个想法，你会看到类似于各种高效匹配器的东西。 一个接近你想要做的是Rete算法，它跟踪随着馈送给它的数据的变化，哪些“模式”是活的。

    这可能是值得研究JXPath的：http://commons.apache.org/jxpath/我不确定你的目标语言是什么，但它可能值得拍摄。

    无论如何，如果我不得不尝试实现类似的东西，我的第一个冲动是找到一种方法来“序列化”两棵树，并将问题简化为简单字符串匹配之一。

    链接地址: http://www.djcxy.com/p/49995.html

    上一篇: Algorithm's name

    下一篇: What's happening here? What kind of member is "Optional"?