Go Participle 左递归语法为什么无法直接解析

我第一次把表达式语法搬进 Go Participle 时，最容易产生的错觉是：结构体可以引用自己的类型，那么把 Expression 放在自己的第一个字段里，应该就能自然表达“表达式由表达式和运算符组成”。实际结果却相反——左递归语法不是普通的递归，它让解析器在还没有消费任何输入之前就回到同一个产生式。

官方地址：https://github.com/alecthomas/participle

Participle 官方资料明确说明，它内部是带回溯的递归下降解析器，不支持左递归；左递归需要通过重构语法消除。理解这句话的关键，不是记住一个限制，而是看清解析入口有没有机会向前移动。

左递归真正卡住的是哪个入口

先把问题缩小到最常见的二元表达式。概念上，左递归写法是“表达式等于表达式、运算符和项”，它的左侧第一项仍然是自己：

// 这段结构只用于展示左递归形状，不应直接作为 Participle 语法使用。
type Expression struct {
	// 第一个字段就是自己，解析 Expression 时会立即再次进入 Expression。
	Left *Expression `@@`
	// 只有左侧返回后才可能读取运算符，但此时还没有消费输入。
	Operator string `@("+" | "-")`
	// 运算符右侧是一个基础项。
	Right *Term `@@`
}

type Term struct {
	// 基础项负责真正消费一个整数 token。
	Value string `@Int`
}

当输入从 1+2 开始时，解析器进入 Expression，先处理 Left；Left 又要求先解析一个新的 Expression。这个调用链在触碰 1 之前就重复了，运算符和右侧项也没有机会被读取。

这就是“无法直接解析”的核心，不是 @@ 不能引用另一个结构体，也不是回溯开关少配了一个参数，而是产生式的首项没有给递归调用留下输入推进点。

为什么回溯也不能替它解决

我起初还尝试过把希望放在回溯上：既然 Participle 会尝试分支，遇到左递归时是不是可以退回来换一条路径？回溯解决的是“某个分支已经有机会匹配，但后来失败”的问题；左递归发生在分支真正消费 token 之前，解析器甚至还没有形成可回退的进展。

可以把两者分开看：

因此不要把“支持回溯”理解成“支持任意递归”。递归下降解析器需要一个能先吃掉输入的基础项，递归部分应放在基础项之后，或者被明确的分隔符包住。

把表达式改写成基础项加重复尾部

解决方案不是删掉表达式递归，而是把它从“首项递归”改成“首项先匹配，后面再重复匹配运算符和操作数”。这种改写常见于手写递归下降语法，也很适合映射到 Participle 的结构体标签。

package main

import (
	"fmt"

	"github.com/alecthomas/participle/v2"
)

// Expression 先匹配一个基础项，再收集任意多个运算尾部。
type Expression struct {
	First *Term  `@@`
	Rest  []*Tail `@@*`
}

// Tail 的首项是运算符，保证进入 Tail 时已经有明确的输入边界。
type Tail struct {
	Operator string `@("+" | "-")`
	Right    *Term `@@`
}

// Term 负责消费最小的整数项；复杂语法可以在这里继续拆分。
type Term struct {
	Value string `@Int`
}

func main() {
	// Build 只构建语法；实际输入由 ParseString 交给同一棵 AST。
	parser, err := participle.Build[Expression]()
	if err != nil {
		// 构建失败应立即返回，避免把无效解析器交给服务运行。
		panic(err)
	}
	ast, err := parser.ParseString("expression", "1+2-3")
	if err != nil {
		// 解析失败保留错误位置，便于调用方定位输入边界。
		panic(err)
	}
	// First 保存第一个操作数，Rest 保存后续运算符和操作数。
	fmt.Printf("first=%s tails=%d\\n", ast.First.Value, len(ast.Rest))
}

改写后的关键不是某个固定字段名，而是这两个边界：First 必须能够先匹配一个 Term，Rest 的每一项必须由运算符开头并继续匹配右侧项。这样解析器进入 Expression 后可以先消费整数，再决定后面是否存在更多尾部。

改写后 AST 和原语义如何对应

改写语法后，AST 的形状会从一棵天然向左嵌套的树，变成一个首项加列表。对输入 1+2-3，First 是 1，Rest 依次保存 (+, 2) 和 (-, 3)。如果后续需要构造二叉树，可以在解析完成后用一个小的归约函数按顺序把列表折叠回去；解析阶段不必承担左递归。

这也解释了为什么“消除左递归”不会改变用户看到的表达式含义：它改变的是语法承载方式，不是运算符和操作数的业务顺序。若运算符有优先级，就把 Term、Factor 等层级继续拆开，让每一层都先匹配基础项，再处理自己的尾部。

// foldExpression 将线性尾部按出现顺序还原为业务层需要的节点。
func foldExpression(expr *Expression) string {
	result := expr.First.Value
	for _, tail := range expr.Rest {
		// 这里示意语义归约位置，真实项目可返回 BinaryExpr 节点而非字符串。
		result = "(" + result + tail.Operator + tail.Right.Value + ")"
	}
	return result
}

上面的归约函数属于 AST 处理，不是 Participle 的解析语法。把两层职责分开后，解析器只负责把 token 放进结构体，业务层再决定是否建立带优先级的表达式树。

哪些写法看起来像修复，其实没有解决问题

有三种调整很容易让代码变复杂，却没有触及左递归本身。

• 只增加回溯深度：回溯数量影响替代分支的尝试范围，不能让首项递归自动获得消费输入的能力。
• 只把指针改成值：*Expression 换成 Expression 只改变 Go 字段表示，不改变产生式仍然以自己为首项的事实。
• 把所有层级都塞进一个结构体：运算符优先级、括号和一元运算混在一个左递归结构中，既难读，也很难为每层找到明确的基础项。

如果语法确实是表达式语言，优先把优先级层级拆成多个非左递归结构；如果语法包含大量上下文敏感规则、缩进或需要复杂语义反馈，则应评估专门的解析策略，而不是强行让一个结构体标签承担全部工作。

我会用这张清单判断是否该改写

现在遇到 Participle 构建失败或递归行为异常时，我会按下面的顺序看，而不是先改一堆标签：

1. 检查产生式的第一个字段是否直接或间接引用自身。
2. 确认递归调用前是否已经匹配了一个 token、字面量或明确分隔符。
3. 把首项抽成基础结构，把重复部分抽成带边界的尾部结构。
4. 如果有运算符优先级，按优先级拆成多层，而不是依靠回溯猜测。
5. 最后再决定 AST 是否保留线性列表，或在解析后归约成二叉表达式树。

结论很简单：Go Participle 不能直接解析左递归，是因为它选择了递归下降加回溯，而这类解析器要求递归在输入推进之后发生。把“自己作为首项”改成“基础项加重复尾部”，既符合 Participle 的限制，也让 AST 的边界更容易被后续业务代码理解。

常见问题

右递归一定比左递归更适合 Participle 吗？

是否适合取决于语法边界，但递归出现在已经匹配基础项之后，通常更符合递归下降的推进要求。仍然要留意是否存在空匹配导致的无限递归。

消除左递归后，运算符优先级会自动保留吗？

不会自动保留。优先级需要通过多层非左递归结构或解析后的归约逻辑明确表达，不能只依赖字段顺序。

一定要把线性列表还原成二叉树吗？

不一定。如果后续只需按顺序执行或生成 SQL，列表可能更直接；只有语义分析、优化或需要保留优先级时，才值得构造更具体的表达式树。