如何在JavaScript中构造树模式匹配算法？

Question

好吧，这是一个有点复杂的问题，但 tl;dr 它基本上是 你如何使用“模式树”解析“实际树”？你如何检查特定树实例是否与特定模式树匹配？

首先，我们有模式树的结构。模式树一般可以包含这些类型的节点：

sequence 节点：匹配项目序列（零个或多个）。
optional节点：匹配一个或零个项目。
class节点：委托给另一个模式树去匹配。
first 节点：匹配它从集合中找到的第一个子模式。
interlace节点：以任意顺序匹配任意子模式。
text节点：匹配直接文本。

对于这个问题，这应该足够好了。还有一些节点类型，但这些是主要的。本质上它就像一个正则表达式或语法树。

我们可以从一个简单的模式树开始：

<sequence>
  <text value="foo">
    <text value="bar" />
  </text>
</sequence>

这应该匹配以下任何 tree 文本。

<foo><bar/></foo><foo><bar/></foo><foo><bar/></foo>
<foo><bar/></foo>
<foo><bar/></foo><foo><bar/></foo>

更具体地说，您应该将其想象为 JSON，将模式树想象为 JSON。

{
  "tag": "foo",
  "children": [
    { "tag": "bar" }
  ]
}

而序列模式树是这样的：

{
  "type": "sequence",
  "children": [
    {
      "type": "text",
      "value": "foo",
      "children": [
        {
          "type": "text",
          "value": "bar"
        }
      ]
    }
  ]
}

对于模式树，更复杂的示例如下所示：

matchThing = <text name="thing">
  <text />
  <sequence>
    <first>
      <class name="value"/>
      <class name="function"/>
    </first>
  </sequence>
</text>

matchFunction = <text name="function">
  <text />
  <sequence>
    <text name="input">
      <text />
    </text>
  </sequence>
  <sequence>
    <text name="call">
      <text />
    </text>
  </sequence>
</text>

matchValue = <text name="value">
  <text />
</text>

它将匹配这样的文本：

<thing>
  <call-me-anything />
  <function>
    <input><foo/></input>
    <input><bar/></input>
    <call><foo/></call>
    <call><foo/></call>
    <call><bar/></call>
    <call><bar/></call>
  </function>
  <function>
    <call><baz/></call>
  </function>
  <value>
    <hello/>
  </value>
  <function>
    <input><hello/></input>
    <call><world/></input>
  </function>
</thing>

所以想象一下 JSON 也是如此。

想知道您是如何为此创建算法的。我一开始就卡住了，但它似乎需要某种类似递归下降的东西，但在树上而不是在序列上。

所以你有一个函数：

function checkIfMatch(actualTree, patternTree) {
  for (node in actualTree) {
    if (!checkIfMatchesSubtree(node, patternTree)) {
      return false
    }
  }
  return true
}

我真的不知道如何开始这个，正在 Google 搜索“tree pattern matching algorithms" or "arbology”。将花费大量时间尝试将这些数学抽象转化为代码，即使我朝着正确的方向前进。想知道您是否可以帮助为这种情况构建一个简单的算法。很难弄清楚您应该如何遍历实际树，同时还遍历模式树，并跟踪您在每棵树中的位置。

https://dml.cz/bitstream/handle/10338.dmlcz/147190/Kybernetika_54-2018-2_1.pdf

花很多时间在上面并没有让我走得太远：

function parse(patternTree, textTree) {
  let state = { ti: 0, pi: 0 }
  while (state.ti < textTree.length) {
    let pattern = patternTree[state.pi]
    let result = parsePattern(pattern, textTree[state.ti])
    if (!result) {
      return
    }
  }
}

function parsePattern(patternNode, textNode, state) {
  if (patternNode.type == 'sequence') {
    return parseSequencePattern(patternNode, textNode, state)
  }
}

function parseSequencePattern(patternNode, textNode, state) {
  while (true) {
    let i = 0
    while (i < patternNode.children.length) {
      let childPattern = patternNode.children[i++]
      let result = parsePattern(childPattern, textNode)
      if (!result) {
        return false
      }

    }
  }
}


while (stack.length) {
  let {
    parents,
    node,
  } = stack.shift()

  stack.push({
    parents: [node, ...parents]
  })
}

Answer 1

最简单的方法 - 只需将 'pattern tree' 转换为正则表达式，然后使用该正则表达式检查 'actual tree' 的文本表示。

关于递归下降。递归下降本身足以执行语法检查，但不是很有效，因为有时您需要多次从头开始检查模式。要制作单程语法检查器，您还需要状态机，这就是 Regexp 的功能。

因此无需重新发明轮子，只需将您的 'pattern' 指定为正则表达式（将您的模式表示转换为正则表达式）

你的

<sequence>
  <text value="foo">
    <text value="bar" />
  </text>
</sequence>

将转换为

/<foo><bar\/><\/foo>/gm

与此完美匹配

<foo><bar/></foo><foo><bar/></foo><foo><bar/></foo>
<foo><bar/></foo>
<foo><bar/></foo><foo><bar/></foo>

我假设转换模式的算法 -> 正则表达式很简单

Answer 2

尝试将您的模式 p 与树 t 匹配时，您必须首先将 p 的根及其 children 与 p 的根匹配t和t的child仁。如果 p 在根部不匹配，则必须遍历 t 的 children，并且每个 child 值都与 p 匹配。

根据您发布的输入和节点类型，递归模式匹配函数必须处理三种主要的输入场景：

p(object) 和 t(object)。在这里，模式是一个带有 type 和 child 键的 object。输入树也是一个 object，至少有 tag 和 children 键。模式匹配函数委托给一个辅助函数来执行 p 的 object.type.
p(object) 和 t(Array)。在这种情况下，树是 object 的 Array，并且基于模式的 object，代码必须决定如何处理树的 Array（sequence、first、等等）。
p(Array) 和 t(Array)。这里，p和t都是序列的形式，匹配操作就是查找，对于p的Array中的每一个a , t 的 Array 中相应的 a1 使得 pattern_match(a, a1) 产生 true.

作为开始，下面的代码实现了一个支持基础节点 text 和 sequence 的 find_match 函数：

//object that stores node match handlers
node_types = {'sequence':sequence_match, 'text':text_match}
//main find_match function
function find_match(pattern, tree_root, tree_children=null){
    var tree = tree_children === null? tree_root.children : tree_children;
    if (!Array.isArray(pattern)){ 
        //pattern is an object - delegate to handler for node type
        if (node_types[pattern.type](pattern, tree_root, tree)){
            return true
        }
        //no match at the root - check the children
        return tree.some(x => find_match(pattern, x, null));
    }
    //pattern is an array - delegate to sequence
    return sequence_match({'children':pattern}, tree_root, tree)
}
//text match handler
function text_match(pattern, tree_root, tree_children){
    if (!('value' in pattern) && !('name' in pattern)){
        //empty text node found
        return true
    }
    if (tree_root.tag === pattern['value' in pattern ? 'value' : 'name']){
        //match found at the root - continue match with pattern and tree children
        return find_match(pattern.children, null, tree_root.children)
    } 
    //no match - check the tree's children
    return (tree_children === null ? tree_root.children : tree_children).some(x => find_match(pattern, x))

}
//sequence match handler
function sequence_match(pattern, tree_root, tree_children){
    var tree = tree_children === null ? tree_root.children : tree_children;
    //copy the pattern and tree objects, as "p" is mutated as part of the match process
    var p = JSON.parse(JSON.stringify(pattern))
    var t = JSON.parse(JSON.stringify(tree))
    while (p.children.length){
        if (!t.length){
            return false
        }
        var f = false;
        var f_seq = p.children.shift();
        for (var _n_t of t){
            //compare sub-pattern and sub-tree
            if (find_match(f_seq, _n_t, t)){
                f = true
                break;
            }
        }
        //no match found for sub-pattern in sequence, return false
        if (!f){
            return false
        }
    }
    //matches found for all sub-patterns in the sequence, return true
    return true
}

tree = [{'tag': 'foo', 'children': [{'tag': 'bar', 'children': []}]}, {'tag': 'foo', 'children': [{'tag': 'bar', 'children': []}]}, {'tag': 'foo', 'children': [{'tag': 'bar', 'children': []}]}]
pattern = {'type': 'text', 'name': 'thing', 'children': [{'type': 'text', 'children': []}, {'type': 'sequence', 'children': [{'type': 'first', 'children': [{'type': 'class', 'name': 'value', 'children': []}, {'type': 'class', 'name': 'function', 'children': []}]}]}]}
console.log(find_match(pattern, {'tag':null, 'children':tree}))
//prints "true"

如何在JavaScript中构造树模式匹配算法？

How to construct tree pattern matching algorithm in JavaScript?

javascript

algorithm

parsing

tree

recursive-descent