4、语法分析概述：上下文无关文法，推导与规约，二义性处理
好，咱们进入第四章。说实话，语法分析是整个编译器前端里最「硬核」的部分之一。我当年刚学的时候，被上下文无关文法绕得晕头转向，后来在做一个表达式解析器时踩了坑，才真正理解这些东西的价值。今天咱们就把这块掰开揉碎，讲清楚。
4.1 上下文无关文法（CFG）——语法分析的基石
先问个问题：为什么词法分析用正则表达式就够了，到了语法分析就得换一套工具？
原因很简单——正则表达式没法处理嵌套结构。你想想看，像 if (a > b) { if (c > d) { ... } } 这种嵌套的 if-else，正则根本搞不定。它没有「记忆」能力，不知道当前在第几层括号里。
上下文无关文法（Context-Free Grammar，简称 CFG）就是来解决这个问题的。它由四部分组成：
- 终结符（Terminal）：词法分析产出的 token，比如数字、运算符、关键字
- 非终结符（Non-terminal）：语法结构的概念，比如「表达式」、「语句」
- 产生式（Production）：描述非终结符如何展开的规则
- 开始符号（Start Symbol）：整个文法的入口
举个例子，一个简单的算术表达式文法：
Expr → Expr '+' Term | Expr '-' Term | Term
Term → Term '*' Factor | Term '/' Factor | Factor
Factor → '(' Expr ')' | number嗯，这里要注意：每个产生式左边只有一个非终结符，这就是「上下文无关」的含义——不管这个非终结符出现在什么上下文中，展开规则都一样。
核心要点：CFG 的能力恰好覆盖了大多数编程语言的语法结构。它比正则表达式强，又比上下文有关文法简单，是编译器前端的最佳选择。
4.2 推导与规约——语法树的两条建造路径
有了文法，怎么用它来解析代码呢？有两条路：
4.2.1 推导（Derivation）——自顶向下
推导是从开始符号出发，不断用产生式替换非终结符，直到全部变成终结符。这个过程就像搭积木——从顶层结构开始，一步步细化到具体 token。
比如解析 3 + 4 * 5：
Expr
→ Expr '+' Term （用第一条产生式）
→ Term '+' Term （把左边的 Expr 展开为 Term）
→ Factor '+' Term （Term 展开为 Factor）
→ 3 '+' Term （Factor 展开为数字 3）
→ 3 '+' Term '*' Factor （Term 展开为 Term '*' Factor）
→ 3 '+' Factor '*' Factor（Term 展开为 Factor）
→ 3 '+' 4 '*' Factor （Factor 展开为 4）
→ 3 '+' 4 '*' 5 （Factor 展开为 5）每一步都选择最左边的非终结符展开，这叫最左推导。反过来，每次都展开最右边的，叫最右推导。这两种推导方式对应着不同的解析策略。
4.2.2 规约（Reduction）——自底向上
规约是推导的逆过程。从 token 序列开始，不断把匹配产生式右部的符号序列替换成左部的非终结符，直到归约成开始符号。
还是 3 + 4 * 5：
3 + 4 * 5
→ Factor + 4 * 5 （3 规约为 Factor）
→ Term + 4 * 5 （Factor 规约为 Term）
→ Expr + 4 * 5 （Term 规约为 Expr）
→ Expr + Factor * 5 （4 规约为 Factor）
→ Expr + Term * 5 （Factor 规约为 Term）
→ Expr + Term * Factor （5 规约为 Factor）
→ Expr + Term （Term * Factor 规约为 Term）
→ Expr （Expr + Term 规约为 Expr）个人经验：我在项目中遇到过一个问题——用自顶向下解析时，左递归会导致无限循环。比如 Expr → Expr '+' Term 这种产生式，如果从左到右匹配，会一直调用 Expr 自身，永远停不下来。解决办法是改写文法，消除左递归。这个坑我踩过，后来写解析器时都会先检查一遍文法有没有左递归。
4.3 二义性——同一个句子，两种解释
如果一个文法对同一个句子能产生两棵不同的语法树，那它就是二义性的。说白了，就是编译器不知道该按哪种方式理解代码。
最经典的例子是悬空 else（dangling-else）问题：
if (a) if (b) c = 1; else d = 2;这个 else 到底匹配哪个 if？C 语言规定匹配最近的 if，但文法本身并没有体现这个规则。
另一个常见例子是运算符优先级：
3 + 4 * 5如果文法写成 Expr → Expr '+' Expr | Expr '*' Expr | number，那 3 + 4 * 5 可以有两种解释：
(3 + 4) * 5—— 先加后乘3 + (4 * 5)—— 先乘后加
这显然不行。数学上乘法优先级高于加法，编译器必须按第二种方式解析。
4.3.1 处理二义性的三种方法
我总结了一下，主要有三种处理方式：
| 方法 | 说明 | 优缺点 |
|---|---|---|
| 改写文法 | 引入优先级层次，消除二义性 | 文法变复杂，但解析器实现简单 |
| 附加规则 | 在解析器中硬编码优先级和结合性 | 文法保持简洁，但解析器逻辑变复杂 |
| 使用二义性文法 | 接受二义性，用额外规则消除歧义 | 适合某些特定场景，如自然语言处理 |
大多数编译器采用第一种方法。比如上面的表达式文法，通过引入 Term 和 Factor 两个层次，自然就解决了优先级问题。
避坑指南：我曾经在写一个脚本语言的解析器时，偷懒用了二义性文法，想着在语义分析阶段再处理。结果调试时发现，同一个表达式在不同上下文中解析结果不一样，查了两天才找到原因。后来老老实实改写了文法，一劳永逸。所以我的建议是——尽量在文法层面消除二义性，别把问题往后推。
4.4 知识体系总览
下面这张图把本章的核心概念串起来了，你可以对照着理解：
你看，整个知识体系其实就围绕这三块：CFG 是基础，推导和规约是两种构建语法树的方式，二义性则是需要特别关注的问题。搞懂了这些，后面学具体的解析算法（LL、LR 等）就会轻松很多。
嗯，这一章就到这里。记住一句话：好的文法设计，能让解析器实现事半功倍。别急着写代码，先把文法设计清楚。
公众号：蓝海资料掘金营，微信 deep3321