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

核心实现思路 #

你要做的模式树匹配本质是带量词的树结构正则匹配，核心设计思路是「返回消耗长度的递归匹配」：每个匹配函数不直接返回布尔值，而是返回{ matched: boolean, consumed: number }结构，matched标识是否匹配成功，consumed标识当前匹配在当前层级消耗了多少个实际节点，这样无需维护全局遍历状态，天然支持回溯，也能同时跟踪模式树和实际树的遍历进度。

前置约定 #

我们统一使用JSON结构的树做实现，class节点依赖的外部模式统一存在全局patternRegistry对象中，key为class的name属性，value为对应的模式树。

完整可运行代码 #

入口与通用分发函数 #

// 全局注册class对应模式树
const patternRegistry = {}

/**
 * 入口函数：校验实际树是否匹配指定模式树
 * @param actualTree 待校验的实际树根节点
 * @param patternTree 模式树根节点
 * @returns 是否匹配成功
 */
function matchTree(actualTree, patternTree) {
  const result = matchNode(patternTree, [actualTree], 0)
  // 要求匹配成功且消耗完所有实际节点
  return result.matched && result.consumed === 1
}

/**
 * 通用匹配分发函数
 * @param patternNode 模式树当前节点
 * @param actualSiblings 实际树当前层级的兄弟节点数组
 * @param startIndex 当前层级开始匹配的下标
 * @returns 匹配结果与消耗节点数
 */
function matchNode(patternNode, actualSiblings, startIndex) {
  switch(patternNode.type) {
    case 'text': return matchText(patternNode, actualSiblings, startIndex)
    case 'sequence': return matchSequence(patternNode, actualSiblings, startIndex)
    case 'optional': return matchOptional(patternNode, actualSiblings, startIndex)
    case 'first': return matchFirst(patternNode, actualSiblings, startIndex)
    case 'interlace': return matchInterlace(patternNode, actualSiblings, startIndex)
    case 'class':
      const delegatePattern = patternRegistry[patternNode.name]
      if (!delegatePattern) throw new Error(`未注册的class模式：${patternNode.name}`)
      return matchNode(delegatePattern, actualSiblings, startIndex)
    default: return { matched: false, consumed: 0 }
  }
}

各类型节点匹配逻辑 #

1. text节点

匹配当前节点标签，再递归匹配子节点：

function matchText(patternNode, actualSiblings, startIndex) {
  if (startIndex >= actualSiblings.length) return { matched: false, consumed: 0 }
  const actualNode = actualSiblings[startIndex]
  // 有value则校验标签，无value则任意标签都匹配（对应通配<text/>）
  if (patternNode.value && actualNode.tag !== patternNode.value) {
    return { matched: false, consumed: 0 }
  }
  // 匹配子节点
  let childConsumed = 0
  const actualChildren = actualNode.children || []
  const patternChildren = patternNode.children || []
  for (const childPattern of patternChildren) {
    const childRes = matchNode(childPattern, actualChildren, childConsumed)
    if (!childRes.matched) return { matched: false, consumed: 0 }
    childConsumed += childRes.consumed
  }
  // 子节点必须全部消耗完才算匹配成功
  if (childConsumed !== actualChildren.length) return { matched: false, consumed: 0 }
  return { matched: true, consumed: 1 }
}

2. sequence节点

循环匹配子模式序列，直到匹配失败为止，支持匹配0次或多次：

function matchSequence(patternNode, actualSiblings, startIndex) {
  let totalConsumed = 0
  let currentPos = startIndex
  while (currentPos < actualSiblings.length) {
    let roundConsumed = 0
    // 匹配一轮完整的子模式序列
    for (const childPattern of patternNode.children) {
      const res = matchNode(childPattern, actualSiblings, currentPos + roundConsumed)
      if (!res.matched) {
        // 本轮匹配失败，返回之前已匹配的长度
        return { matched: true, consumed: totalConsumed }
      }
      roundConsumed += res.consumed
    }
    totalConsumed += roundConsumed
    currentPos += roundConsumed
  }
  return { matched: true, consumed: totalConsumed }
}

3. optional节点

尝试匹配一次子模式，失败则消耗0个节点，永远匹配成功：

function matchOptional(patternNode, actualSiblings, startIndex) {
  const res = matchNode(patternNode.children[0], actualSiblings, startIndex)
  return res.matched ? res : { matched: true, consumed: 0 }
}

4. first节点

逐个尝试子模式，返回第一个匹配成功的结果，全部失败则匹配失败：

function matchFirst(patternNode, actualSiblings, startIndex) {
  for (const childPattern of patternNode.children) {
    const res = matchNode(childPattern, actualSiblings, startIndex)
    if (res.matched) return res
  }
  return { matched: false, consumed: 0 }
}

5. interlace节点

按任意顺序匹配所有子模式（每个子模式匹配1次，若需要支持重复匹配可移除usedPatterns标记）：

function matchInterlace(patternNode, actualSiblings, startIndex) {
  const usedPatterns = new Array(patternNode.children.length).fill(false)
  let currentPos = startIndex
  let matchedCount = 0
  while (matchedCount < patternNode.children.length && currentPos < actualSiblings.length) {
    let found = false
    for (let i = 0; i < patternNode.children.length; i++) {
      if (usedPatterns[i]) continue
      const res = matchNode(patternNode.children[i], actualSiblings, currentPos)
      if (res.matched) {
        usedPatterns[i] = true
        currentPos += res.consumed
        matchedCount++
        found = true
        break
      }
    }
    if (!found) break
  }
  return matchedCount === patternNode.children.length 
    ? { matched: true, consumed: currentPos - startIndex }
    : { matched: false, consumed: 0 }
}

使用示例 #

// 注册你给出的简单sequence模式
patternRegistry.fooBarSeq = {
  "type": "sequence",
  "children": [
    {
      "type": "text",
      "value": "foo",
      "children": [ { "type": "text", "value": "bar" } ]
    }
  ]
}

// 测试实际树
const testTree = {
  "tag": "foo",
  "children": [ { "tag": "bar" } ]
}

console.log(matchTree(testTree, patternRegistry.fooBarSeq)) // 输出true

内容的提问来源于stack exchange，提问作者Lance Pollard