第3章：上下文无关文法与语法分析

文法与歧义

上下文无关文法用非终结符和产生式定义递归结构。文法 E → E+E | E*E | id 对 a+b*c 有不同语法树，因此需要优先级规则或改写文法。

可改为：

text

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id

乘法位于更深的结构层。消除左递归后的文法形状不自动保证 AST 采用所需结合性；递归下降实现通常用循环累积左侧节点，构造左结合的加法树。

FIRST 集合记录串可能以哪些终结符开头；FOLLOW 记录某非终结符后可能出现的终结符。对含空产生式的分支，需要借助 FOLLOW 决定何时选空。

上述文法中 $FIRST(T)=\{(,id\}$ ， $E'$ 的非空分支由 + 开始，而空分支在 ) 或输入结束等 FOLLOW 符号下选择。LL(1) 要求同一非终结符的预测表项不冲突。

不是所有 CFG 都能通过简单消左递归变成 LL(1)。有些语言结构需要更多前看、其他文法表达或不同分析算法。

LR 分析从左到右读取输入，栈中保存状态和已识别结构；移进消费一个终结符，归约把某产生式右部替换成左部。状态编码“已经识别到产生式的什么位置”及适用的前看信息。

移进/归约冲突表示当前表信息不能唯一决定行动。经典悬挂 else 问题可用语言规则绑定到最近未匹配 if，但这是语言语义选择，不能只靠随意删除冲突解决。

完整语法树包含括号和辅助非终结符，AST 通常去掉这些只服务解析的节点，只保留语义结构。对 a+b*c，AST 是 Add(a,Mul(b,c))，无需保留每一层 E'。

错误恢复可跳过输入直到分号等同步点，再继续报告更多问题。恢复后的树可能含错误节点，后续阶段必须知道它不代表完整合法程序。