3.1 上下文无关文法

3.1 上下文无关文法

本节摘要：上下文无关文法是四元组（终结符、非终结符、产生式、开始符号），每条产生式规定一个非终结符可以展开成什么。本节围绕主线语句构造表达式文法，讲清推导与归约两种读法、最左最右的规范次序，以及二义性文法如何靠分层改写消除——运算符优先级正是分层的产物。

阅读完本节，你应当能够：

1. 写出识别赋值语句的分层表达式文法并逐条解释
2. 对主线单元流执行一次完整最左推导
3. 用分层文法解释乘法为什么先于减法结合
4. 识别悬空 else 等经典二义性并给出改写方案

文法是一张展开说明书

先给主线语句配一份完整文法。竖线分隔候选式，箭头读作"可以展开为"：

G = (V, T, P, S)
V  非终结符： {语句, 表达式, 项, 因子}
T  终结符：   {ID, NUM, ASSIGN, ADDOP, MULOP, LPAREN, RPAREN, SEMI}
S  开始符号： 语句

P  产生式：
(1) 语句   → ID ASSIGN 表达式 SEMI
(2) 表达式 → 表达式 ADDOP 项
(3) 表达式 → 项
(4) 项     → 项 MULOP 因子
(5) 项     → 因子
(6) 因子   → ID
(7) 因子   → NUM
(8) 因子   → LPAREN 表达式 RPAREN
​

为什么拆成表达式、项、因子三层？这不是学术洁癖，是优先级的编码。加法产生式的operand是"项"，乘法产生式的operand是"因子"——乘法比加法低一层，意味着乘法必须先在"项"这一层里结合完，才轮到加法把整个项当作操作数。运算符优先级表在文法里变成了层级深度，这是文法设计最漂亮的把戏之一。

推导：从根到叶的展开

推导从开始符号出发，反复把非终结符替换成产生式右部。对主线单元流做最左推导（每次替换最左边的非终结符）：

输入单元流： ID total ASSIGN ID price MUL ID qty SUB ID discount SEMI

语句
 → ID ASSIGN 表达式 SEMI                      用产生式 (1)，ID 已匹配
 → ID ASSIGN 表达式 ADDOP 项 SEMI             先按减法展开？注意方向
 → ID ASSIGN 项 ADDOP 项 SEMI                 表达式 → 项
 → ID ASSIGN 项 MULOP 因子 ADDOP 项 SEMI      项 → 项 MULOP 因子
 → ID ASSIGN 因子 MULOP 因子 ADDOP 项 SEMI
 → ID ASSIGN ID MULOP 因子 ADDOP 项 SEMI      因子 → ID，匹配 price
 → ID ASSIGN ID MULOP ID ADDOP 项 SEMI        匹配 qty
 → ID ASSIGN ID MULOP ID ADDOP 因子 SEMI
 → ID ASSIGN ID MULOP ID ADDOP ID SEMI        匹配 discount

全终结符序列与输入单元流逐一吻合：推导成功
​

把这次推导的过程"倒着放"，就是归约：从单元流出发，反复把产生式右部收缩成左部非终结符，最后收缩到开始符号。推导是自顶向下路线的直觉，归约是自底向上路线的直觉，3.2 与 3.3 两节分别把这两种直觉写成算法。

二义性：一棵树还是两棵

换一份偷懒的文法试试：表达式 → 表达式 ADDOP 表达式，表达式 → 表达式 MULOP 表达式，表达式 → ID。它也能推出主线语句，但推法不止一种——减法可以先结合，乘法也可以先结合，对应两棵不同的树。一个文法对同一串存在两棵不同分析树，就叫有二义性。树不唯一，语义就不唯一（先减后乘还是先乘后减，结果天差地别），所以二义文法不可用于编译器。

消解靠改写分层，也就是本节开头那份三层文法。另一个经典二义是悬空 else：

问题文法：
S → if E then S
S → if E then S else S
S → other

输入： if a then if b then s1 else s2
疑问： else 配内层 if 还是外层 if？两棵树都合法。
约定： else 与最近的未配对 then 结合（最近匹配原则）
改写：把语句分成 匹配语句 与 开放语句 两类，产生式上强制
     else 只能出现在匹配语句里，文法层面排除远配对树
​

消歧的两条路——改文法或加约定（优先级声明）——工程上后者更常见：yacc 的优先级声明本质上就是往分析表生成算法里塞裁决规则，省去手改文法的繁琐。

图 分层文法与优先级：每层管一级结合

文法之外的一点分寸

不是所有"合法与否"的问题都归文法管。"变量先声明后使用"查不出来的——ID total 里的 total 声明过没有，取决于它前面出现了什么，这正是"上下文有关"的性质，超出上下文无关文法的能力，留给第 4 章的符号表。同理，"函数调用参数个数对不对"也归语义分析。文法管形状，语义管意义，这条界线在第 1 章的流水线图里已画过，现在你有了具体的例子。

⚠️ 常见坑：消除二义性时把左递归改成右递归来"修复"左结合。表达式 → 项 加 项 加…… 的右递归写法确实无二义，但把减法的左结合变成了右结合，a-b-c 会被算成 a-(b-c)，语义悄悄错了。消歧只能改层级，不能改结合方向。

💡 关键直觉：把优先级表、结合性表、文法产生式三者看成同一件事的三种视图——设计语言时通常先写优先级表，再机械翻译成分层文法；读别人的文法时反向翻译回优先级表，一层一个心眼。

语法树之外的追问

问：抽象语法树和分析树是一回事吗？ 不是。分析树（推导树）保留全部细节，包括每个非终结符节点与每个括号；抽象语法树只留运算与操作数——括号完成了结合使命后退场，单产生式链（表达式 → 项 → 因子）也被压缩。第 4 章语义分析作业的对象是抽象语法树，这一步瘦身通常在分析过程中顺带完成。

问：文法等价是什么意思？ 两个文法识别同一语言即等价，但分析效率与可读性可以天差地别。消除左递归后的文法与原版等价，却能为递归下降所用；分层文法与优先级声明文法等价，规模差好几倍。换个等价文法是语法分析这门手艺里最常用的招式，变换方向由目标分析器决定。

本节要点回顾

• 四元组：非终结符、终结符、产生式、开始符号；产生式是展开说明书
• 两种读法：推导（根到叶，自顶向下路线）与归约（叶到根，自底向上路线）
• 优先级即层级：乘法在更深的产生式层，天然先结合
• 结合性即递归方向：左递归产生左结合，改方向会悄悄改语义
• 二义性：一串两树即非法，靠分层改写或裁决约定消解；悬空 else 是经典案例

规则备好，下一节把推导直觉写成代码：递归下降分析器，一个函数一层文法，亲手分析主线语句。