TypeScript中如何用Chevrotain递归解析表达式构建正确AST

你当前实现的右递归规则虽然能输出可用结果，但存在三个明显缺陷：

• 优先级逻辑隐式依赖分支声明顺序与右递归特性，语法层面没有明确体现优先级设计，后续新增运算符、调整分支顺序时极易破坏解析逻辑，维护成本高。
• 生成的CST是深度嵌套的右递归结构，需要额外遍历转换才能匹配你定义的OrNode/AndNode结构，多了一层性能损耗。
• 右递归在处理超长表达式时存在不必要的函数调用开销，极端场景下有栈溢出风险。

按照运算符优先级分层设计规则，直接在解析阶段组装目标AST节点，无需后处理，逻辑清晰可维护。

注：优先级规则的设计原则是低优先级规则放在外层，调用高优先级规则。如果你描述的「OR优先级高于AND」是准确的，只需要调换下文两层规则的顺序即可；如果实际业务是按OR拆分条件块（即AND优先级更高，和常规逻辑运算规则一致，也匹配你给出的OrNode包含AndNode列表的接口设计），直接使用下文代码即可。

第一步：调整类型定义 #

你原来的AndNode接口类型定义无法适配连续运算符的嵌套场景，先修正类型：

interface OrNode {
  type: "OrNode",
  operator: "OR",
  orOperatorChild: (AndNode | Expression)[]
}

interface AndNode {
  type: "AndNode",
  operator: "AND",
  left: Expression | AndNode,
  right: Expression | AndNode
}

interface Expression {
  type: "Expression",
  fullPart?: string,
  mainTerm?: string,
  valueMatch?: string,
}

如果要保留原字段名leftExpression/rightExpression，只需要把字段类型调整为Expression | AndNode即可。

第二步：分层实现解析规则 #

三层规则从外到内对应优先级从低到高，解析过程中直接组装目标AST，拿到结果即可使用：

// 顶层入口规则：返回OrNode，自动适配单表达式无运算符的场景
public extractExpressions = this.RULE(RULES.extractExpressions, () => {
  const childNodes: (AndNode | Expression)[] = [];
  // 先匹配第一个AND块/原子表达式
  childNodes.push(this.SUBRULE(this.andExpression));
  // 循环匹配所有后续OR连接的块
  this.MANY(() => {
    this.CONSUME(Or, { LABEL: TERMINAL_LABELS.OR_BETWEEN_GLOBAL_TERMS });
    childNodes.push(this.SUBRULE(this.andExpression));
  });

  return {
    type: "OrNode",
    operator: "OR",
    orOperatorChild: childNodes
  } as OrNode;
});

// 第二层规则：处理AND连接的表达式，返回AndNode或原子Expression
public andExpression = this.RULE(RULES.andExpression, () => {
  let leftNode: Expression | AndNode = this.SUBRULE(this.atomicExpression);
  // 循环匹配所有后续AND连接的表达式，组装左嵌套的AndNode
  this.MANY(() => {
    this.CONSUME(And, { LABEL: TERMINAL_LABELS.AND_BETWEEN_GLOBAL_TERMS });
    const rightNode = this.SUBRULE(this.atomicExpression);
    leftNode = {
      type: "AndNode",
      operator: "AND",
      left: leftNode,
      right: rightNode
    } as AndNode;
  });

  return leftNode;
});

// 第三层规则：匹配原子表达式（TERM:MATCH_TERM），直接返回Expression节点
public atomicExpression = this.RULE(RULES.atomicExpression, () => {
  const termPart = this.SUBRULE(this.extractGenericTerm);
  const matchPart = this.SUBRULE(this.extractMatchTerm);
  
  return {
    type: "Expression",
    mainTerm: termPart.image,
    valueMatch: matchPart.image,
    fullPart: `${termPart.image}:${matchPart.image}`
  } as Expression;
});

// 保留原有的词法匹配规则即可
public extractGenericTerm = this.RULE(RULES.extractGenericTerm, () => {
  // 原有TERM匹配逻辑
});
public extractMatchTerm = this.RULE(RULES.extractMatchTerm, () => {
  // 原有MATCH_TERM匹配逻辑
});

方案优势 #

• 逻辑透明：规则分层严格对应优先级设计，不需要依赖隐式的分支顺序或递归特性，后续新增NOT、括号等运算符时，只需要在对应层级插入规则即可，不会破坏现有逻辑。
• 性能更高：用迭代的MANY替代递归，减少函数调用开销，同时解析过程直接组装AST，省去了CST遍历转换的步骤。
• 天然适配边界场景：不管输入是单个表达式、连续AND、连续OR还是任意组合，都能正确输出以OrNode为顶层的结构，不需要额外处理「首个表达式前无OR」「无运算符单表达式」的边界情况。

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