大部分程序员接触 CFG，通常是从编译原理课开始的：BNF、乔姆斯基体系、LL/LR 分析。那时候很容易觉得，语法解析已经是一个“标准答案很成熟”的领域。

但真到自己写 parser，就会发现 CFG 并没有那么省心：歧义、移入/归约冲突、优先级和结合性编码、给自顶向下分析器消左递归。这时很多人会第一次注意到 PEG，因为它换了一个思路：不再把“多个候选同时成立”视为正常情况，而是把选择写成带顺序的匹配过程。

本文的目标不是把 PEG 吹成银弹，而是把几个最容易混淆的问题讲清楚：PEG 到底是什么，它和 CFG 的本质区别在哪里，它解决了什么，又放弃了什么。

CFG 是什么

上下文无关文法（Context-Free Grammar）是乔姆斯基体系里 Type-2 的形式文法。一个 CFG 由四元组组成：

• 终结符集合（terminals）：词法单元，如 if、while、123
• 非终结符集合（non-terminals）：语法变量，如 Expression、Statement
• 产生式规则（productions）：从非终结符到终结符/非终结符的推导
• 开始符号（start symbol）：推导的起点

一个简单的 CFG：

Expression ::= Expression "+" Expression | Number
Number     ::= Digit+
Digit      ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

问题来了："1+2+3" 可以有两种推导方式：

((1+2)+3)  // 左结合
(1+(2+3))  // 右结合

这就是歧义（ambiguity）。CFG 本身允许歧义存在；如果你不想要歧义，就得额外编码优先级、结合性，或者拆出更多非终结符来消除它。

CFG 的解析算法

CFG 的解析算法有很多种，主流的有：

LR 系列算法本质上是在做状态机驱动的归约：给定一个 token 流，用自动机判断它能不能由开始符号推导出来。对于无歧义、适配该算法族的 grammar，这套方法非常高效；如果 grammar 含糊或写法不适合，就会在构表阶段体现为冲突（shift-reduce conflict / reduce-reduce conflict）。

PEG 是什么

PEG（Parsing Expression Grammar）由 Bryan Ford 在 2004 年提出（《Parsing Expression Grammars: A Recognition-Based Syntactic Foundation》）。它和 CFG 长得很像，但语义完全不同。

一个典型的 PEG grammar：

Expression ← AddExpr
AddExpr    ← MulExpr (("+" / "-") MulExpr)*
MulExpr    ← Atom (("*" / "/") Atom)*
Atom       ← Number / "(" Expression ")"
Number     ← [0-9]+

看起来和 CFG 很像，但关键区别在 /：它表示有序选择（ordered choice），不是“无序并列的多个候选”。

核心区别：并行 vs 顺序

这是 PEG 和 CFG 本质上的不同。

CFG 的选择是无序的

A ::= B | C

在 CFG 里，这条规则的意思是：B 和 C 都是 A 的合法展开方式。如果某个输入既能按 B 解释，也能按 C 解释，那 grammar 就有歧义。是否接受这种歧义、如何消解它，是 grammar 设计和解析算法共同面对的问题。

PEG 的选择是有序的

A ← B / C

在 PEG 里，规则的意思是：先尝试匹配 B，如果成功就用 B；如果失败，才尝试 C。没有歧义——因为顺序已经决定了优先级。

这意味着 PEG 更接近一个按顺序执行的递归下降识别器。它可以在“某个备选分支失败”时回到同一选择点尝试下一个分支，但不会像正则引擎那样为了让后续表达式成功而任意回吐已经确认消费的输入。也正因为选择顺序已经写进 grammar，PEG 没有 LR 意义上的“冲突表”问题。

PEG 解决了 CFG 的哪些问题

左递归

CFG 里，左递归 grammar 对自顶向下的 LL 解析器是致命的，会直接导致无限递归：

Expr ← Expr "+" Term | Term

LL 解析器看到 Expr 会先去匹配 Expr，于是永远递归不出去。

在 PEG 的原始形式里，左递归同样不可用，因为 PEG 也是按自顶向下的方式解释规则的。实际写法通常是把左递归改写成迭代形式：

Expr ← Term (("+" / "-") Term)*

这样既保留了左结合结构，也避免了左递归本身。

需要补一句：有些现代 PEG 实现确实扩展了语义，支持直接或间接左递归；但那是实现层面的扩展，不是 PEG 形式主义里通用的基本能力，也不是靠 & / ! 这样的谓词就能自动“开启”的。

歧义

如果你把表达式 grammar 写得过于扁平，CFG 下的 1+2*3 可能出现多种解释，比如 (1+2)*3 和 1+(2*3)。

在 PEG 里，你直接写清楚优先级就行了：

Add ← Mul (("+" / "-") Mul)*
Mul ← Atom (("*" / "/") Atom)*

先匹配 Mul，再在 Add 层组合，所以 2*3 会先成组，1+2*3 自然被识别为 1+(2*3)。更准确地说，这里是 grammar 的分层结构编码了优先级；PEG 的有序选择则负责在多个候选规则之间给出确定解释。

冲突

LR 解析器遇到经典的悬空 else 问题时，往往会出现 shift-reduce conflict。

PEG 不会以“冲突表”的形式暴露这个问题，因为选择是顺序的。你可以把更长的规则写在前面：

Statement ← "if" Expr "then" Statement "else" Statement
          / "if" Expr "then" Statement
          / ...

先尝试完整匹配，失败才尝试短的。

PEG 的代价

PEG 不是银弹。它带来的确定性，也伴随着一些明确的代价。

时间复杂度最坏是指数级

如果用朴素的递归下降方式实现 PEG，而 grammar 又写得不合理，同一位置可能被重复尝试很多次，比如：

A ← B / C
B ← A "x"
C ← A "y"

这类写法会导致非常糟糕的回溯行为。很多 PEG 解析器会使用 memoization，也就是 Packrat Parsing：把“某条规则在某个输入位置上的结果”缓存起来。这样在固定 grammar 的前提下，最坏时间复杂度可以做到线性，但代价是更高的内存占用。

它描述识别器，而不是生成器

这是 PEG 最重要的哲学差异。CFG 是一个生成式文法：它定义一个语言里哪些字符串可以被推导出来。PEG 则是识别式文法：它定义一个输入串应该如何被尝试、匹配和接受。

CFG 更像“这个语言能生成什么”，PEG 更像“这个识别器按什么顺序尝试并接受输入”。

这也是为什么 PEG 和 CFG 看起来很像，语义却并不等价。PEG 不是 CFG 的简单“无歧义版”，两者的表达能力关系也不能粗暴地概括成“谁包含谁”。Bryan Ford 在原始论文里指出，PEG 能表达所有 deterministic LR(k) 语言，也能表达一些非上下文无关语言；因此 PEG 与 CFG 的整体关系更适合理解成不是一个简单的包含关系，而不是“PEG 就是 CFG 的真子集”。

Pest：Rust 里的 PEG 工具

Pest 是 Rust 生态里最成熟的 PEG 解析器生成器。它把 grammar 写在一个独立的 .pest 文件里，用 Rust 宏生成解析器代码。

一个 Pest grammar 文件长这样：

alpha = { ('a'..'z')+ }
digit = { ('0'..'9')+ }

expr = { term ~ (("+" | "-") ~ term)* }
term = { atom ~ (("*" | "/") ~ atom)* }
atom = { digit | "(" ~ expr ~ ")" }

start = { expr }

需要注意，pest 的具体记号和很多 PEG 论文不完全一样：

• ~ 是顺序连接
• | 是有序选择
• * + ? 是重复
• ! 是否定断言
• & 是肯定断言

rule = { ... } 里的 {} 只是 pest 的语法边界，表示“这是一条规则的主体”。如果要写原子规则（atomic），才会用修饰符写成 rule = @{ ... }；类似地，还有静默规则 _{ ... }、复合原子规则 ${ ... } 等。

Rust 端通过 derive 宏拿到解析器：

use pest::Parser;

#[derive(Parser)]
#[grammar = "calc.pest"]
struct CalcParser;

let pairs = CalcParser::parse(Rule::expr, "1+2*3").unwrap();

.pest 里不能像 yacc/ANTLR 那样内嵌 Rust 语义动作；通常的做法是先让 pest 产出 Pair / Pairs，再在 Rust 代码里遍历它们并构造 AST。上面说的 @ 只是声明原子规则，例如：

num = @{ digit+ }

表示 digit+ 这一段按原子方式匹配，主要影响隐式空白和 token 切分行为；不是“把匹配结果直接当作代码块执行”。

pest 的设计思路很清晰：grammar 文件只写识别规则，解析器由 derive 宏生成；它和 nom 这种“组合子直接写在 Rust 代码里”的路线是两种不同风格。

总结

从这个对比里可以看到，PEG 和 CFG 并不是“新旧替代”关系，而是两套语义不同的语法描述体系。PEG 把选择顺序直接写进 grammar，换来确定性的识别过程；CFG 则保留生成式文法的传统表达方式，并发展出了完整的 LL/LR/GLR 算法谱系。

因此，实际 parser 工具的实现路线也并不统一。有些工具采用 PEG 或 PEG 风格的识别模型，也有些工具采用 LR、GLR 或它们的变体；例如 Tree-sitter 采用的就是增量 LR 路线。

参考资料：Parsing Expression Grammars: A Recognition-Based Syntactic Foundation - Bryan Ford (2004) / What is Packrat Parsing?