语法分析基础：上下文无关文法（CFG）、推导与规约、语法分析树与抽象语法树（AST）、二义性文法的处理
各位同学，欢迎来到语法分析的世界。
词法分析我们搞定了，把源代码切成了一个个 token。但 token 本身没有结构，就像一堆散落的砖头。语法分析要做的，就是把这些砖头砌成墙——检查它们是否符合语言的语法规则。
说白了，语法分析就是回答一个问题：这段代码，语法上对不对？
我个人习惯把语法分析比作「搭积木」。你拿到一堆形状各异的积木（token），要按照说明书（文法）把它们拼成指定的造型（语法树）。如果拼错了，编译器就会告诉你：这里不对。
上下文无关文法（CFG）
先聊聊最核心的概念：上下文无关文法，简称 CFG。
为什么叫「上下文无关」？因为一个非终结符的展开，不依赖于它周围的符号。比如表达式 a + b 中的 a 怎么展开，跟它前面有没有 + 没关系。这一点跟自然语言不同——中文里「行」字，在「银行」和「行走」中读音不同，这就是上下文相关。但编程语言的设计者刻意避开了这种复杂性。
一个 CFG 由四部分组成：
- 终结符：不可再分的基本符号，比如关键字
if、运算符+、标识符id。说白了就是词法分析产出的 token。 - 非终结符：需要被定义的语法成分，比如
Expr、Stmt。它们可以继续展开。 - 产生式：定义非终结符如何展开的规则。比如
Expr → Expr + Term。 - 开始符号：整个文法的入口，通常是一个特殊的非终结符，比如
Program。
举个例子，一个简单的算术表达式文法：
Expr → Expr + Term
Expr → Expr - Term
Expr → Term
Term → Term * Factor
Term → Term / Factor
Term → Factor
Factor → ( Expr )
Factor → id
Factor → num嗯，这里要注意：这个文法是有左递归的。实际做语法分析时，左递归会导致无限循环。我早期写递归下降解析器时就踩过这个坑——程序直接栈溢出了。后面我们会讲怎么消除左递归。
推导与规约
有了文法，我们怎么判断一个句子是否合法？两个方向：推导和规约。
推导是从开始符号出发，不断用产生式替换非终结符，直到得到目标句子。就像从根节点往下生长出一棵树。
举个例子，推导 id + id * id：
Expr
→ Expr + Term
→ Term + Term
→ Factor + Term
→ id + Term
→ id + Term * Factor
→ id + Factor * Factor
→ id + id * Factor
→ id + id * id每次只替换最左边的非终结符，这叫最左推导。反过来，每次替换最右边的，叫最右推导。这两种推导方式，在自顶向下和自底向上分析中分别扮演重要角色。
规约是推导的逆过程。从句子出发，不断把产生式的右部替换成左部的非终结符，直到归约到开始符号。这就像从叶子节点往上合并，最终回到根节点。
我在项目中遇到过一个问题：规约时怎么选择「句柄」？句柄就是当前可以规约的最左子串。选错了，规约就会卡住。这其实就是 LR 分析器要解决的核心问题。
核心要点：推导是自上而下，规约是自下而上。前者对应递归下降分析，后者对应 LR 分析。两种思路，殊途同归。
语法分析树与抽象语法树（AST）
推导过程可以直观地表示为一棵树——语法分析树（也叫具体语法树）。
语法分析树的每个内部节点是一个非终结符，叶子节点是终结符。它完整保留了推导的每一步信息，包括那些「辅助性」的非终结符，比如 Term、Factor。
但说实话，语法分析树太「啰嗦」了。你想想看，一个简单的 a + b，语法分析树里会多出好几层 Term、Factor 节点。这些对后续的语义分析和代码生成来说，完全是冗余信息。
所以我们引入了抽象语法树（AST）。AST 只保留对语义有意义的节点，去掉了那些纯语法辅助节点。
比如 id + id * id 的 AST 大概是这样的：
+
/ \
id *
/ \
id id你看，Term、Factor 这些中间节点全没了，只剩下运算符和操作数。AST 更紧凑，也更接近代码的「意图」。
我个人习惯在语法分析阶段直接生成 AST，而不是先生成语法分析树再转换。这样能省一次遍历，性能更好。当然，调试的时候会麻烦一点——AST 的信息不如语法分析树完整。
我的经验：如果你刚开始写编译器，建议先显式生成语法分析树，等调试通过后再优化成直接生成 AST。一步到位容易出 bug，而且很难定位。
二义性文法的处理
什么是二义性？同一个句子，能画出两棵不同的语法分析树。这就叫二义性。
经典的例子：id + id * id。如果文法写成这样：
Expr → Expr + Expr
Expr → Expr * Expr
Expr → id那么 id + id * id 可以有两种推导方式：
- 先加后乘：
(id + id) * id - 先乘后加：
id + (id * id)
这两种结果在数学上不等价。编译器必须明确选择一种，否则程序的行为就不确定。
处理二义性有三种常见方法：
- 改写文法：引入优先级和结合性，消除二义性。比如前面那个带
Term、Factor的文法，就是通过分层来强制乘法的优先级高于加法。 - 指定优先级和结合性：很多解析器生成器（如 YACC、Bison）允许你直接声明运算符的优先级和结合性，而不必改写文法。这样代码更简洁。
- 使用语义规则：在语法分析过程中，通过额外的规则来消除歧义。比如 C 语言的「悬垂 else」问题，就通过规定 else 匹配最近的 if 来解决。
我曾经在做一个脚本语言时，偷懒没有处理 if-else 的二义性。结果写测试用例时，一个嵌套的 if-else 行为完全不符合预期。嗯，从那以后我再也不敢跳过二义性检查了。
避坑指南：二义性文法不一定是「错误」的，但必须被明确处理。如果你用解析器生成器，记得检查它是否报告了冲突。我曾经忽略了一个 shift/reduce 冲突警告，结果生成的解析器在特定输入下行为诡异，调试了整整两天。
知识体系总览
下面这张图总结了本章的核心脉络：
这张图把四个核心概念串在了一起。CFG 是基础，推导和规约是操作方式，语法树是结果，二义性是需要解决的问题。它们共同构成了语法分析的骨架。
好了，这一章就到这里。语法分析是编译器的「骨架」，搞懂了它，后面的语义分析和中间代码生成就会顺畅很多。
可可精品资料库