4.2 推导、解析树与二义性
CFG 通过改写非终结符来定义语言。一次次改写组成推导（derivation）；把这些改写关系画成树，就是解析树（parse tree）。它们不仅是形式语言中的数学对象，也直接解释了语法分析器（parser）为什么接受某个词法单元（token）序列、文法为什么会产生多种含义，以及编译器为何要把语法结构和源码文本分开处理。
设有文法：
E -> E + T | T
T -> idid + id 的一个推导是：
E
=> E + T
=> T + T
=> id + T
=> id + id符号 => 表示“一步推导”。它的传递闭包写作 =>*，意思是零步或多步推导。因此：
E =>* id + id表示 id + id 属于从 E 生成的语言。
句型、左最推导与右最推导
推导过程中，所有由终结符和非终结符混合组成的中间结果叫做句型。即使最终解析树相同，推导顺序也不一定唯一。在 E => E + T 之后，你可以先展开左边的 E，也可以先展开右边的 T。
左最推导每一步总是展开最左边的非终结符：
E
=> E + T
=> E + T + T
=> T + T + T
=> id + T + T
=> id + id + T
=> id + id + id右最推导每一步总是展开最右边的非终结符：
E
=> E + T
=> E + id
=> E + T + id
=> E + id + id
=> T + id + id
=> id + id + id两者生成相同终结符串，但选择的展开顺序不同。这个差异会在后面的语法分析器算法中变得重要。自顶向下分析通常用左最推导来解释；自底向上 LR 分析可以理解成“反向构造右最推导”。现在不必死记这句话，但它说明同一份文法会被不同算法从不同方向使用。
解析树保存层次结构
解析树是一棵有根、有序树：
- 根节点是开始符号。
- 每个内部节点都是非终结符。
- 一个内部节点的孩子依次对应它使用的产生式右部。
- 从左到右读取所有叶子，得到最终终结符句子。
对于 id + id * id，解析树记录的是乘法究竟作为加法右侧子树出现，还是加法作为乘法左侧子树出现。这不是排版差异，而是程序含义的差异。
解析树中还会保留许多后续阶段并不关心的语法脚手架，例如括号、分号、文法辅助非终结符、递归列表节点。抽象语法树（AST）通常会删除这些细节，只留下真正有语义意义的结构：
解析树中的层级：
Expr -> Expr + Term
Term -> Term * Factor
Factor -> id
可能的 AST：
Add(Identifier("a"), Multiply(Identifier("b"), Identifier("c")))解析树回答“文法是怎么应用的”；AST 回答“程序的结构和操作是什么”。第 7 章会详细讨论 AST 节点设计和源码范围。
解析树不等于运行时求值顺序
不要把分组关系和执行顺序混为一谈。解析树通常决定语法结合方式，例如 a + (b * c)；它并不自动规定所有运行时细节。函数参数求值顺序、短路布尔逻辑、溢出规则、副作用顺序，都需要语言语义进一步定义。编译器可以构造完全正确的解析树，但仍需语义规则才能知道某段程序究竟允许什么行为。
二义性意味着同一句子有多棵解析树
如果某个终结符串有两棵不同的解析树，等价地有两个不同的左最推导，那么这个文法就是二义的。经典例子：
E -> E + E | E * E | id它对：
id + id * id至少允许两种含义：
id + (id * id)或：
(id + id) * id如果语言规范没有选定其中之一，不同语法分析器或语法分析器生成器的冲突解决策略就可能得到不同结果。这是语言设计错误，而不只是语法分析器实现不够聪明。
常见的优先级编码方法是分层写文法：
Expr -> Expr + Term | Term
Term -> Term * Factor | Factor
Factor -> id | ( Expr )* 位于更深的 Term 层，因此它比 + 绑定得更紧。左递归形状还会编码左结合性：a - b - c 被解释为 (a - b) - c。如果语言要求像幂运算那样右结合，则文法形状必须换一种写法。
另一个著名的二义例子是悬空 else（dangling else）：
Stmt -> if Expr then Stmt
| if Expr then Stmt else Stmt
| other对于嵌套 if，一个 else 可以连接到不止一个 if。很多语言规定“连接到最近的尚未匹配的 if”；也可以通过已匹配/未匹配语句分类，把这个规则直接编码进无二义文法。
用见证看见二义性
a-b-c 是好见证（witness）：(a-b)-c 与 a-(b-c) 容易画出，也可能算出不同结果。若文法允许两棵树，它就描述了两个程序。优先级声明与文法层级因而是在定义源语言含义，不只是压掉语法分析器警告。
文法可疑时，先写最小输入的推导并画树，再改代码。词法单元序列本身看不出文法本应负责的层次结构。
写语法分析器前如何审查文法
在实现语法分析器前，先对文法提出具体问题：
1. 同一个词法单元序列会不会有多棵解析树？
2. 文法是否准确编码了优先级和结合性？
3. 可选与重复结构的边界是否清楚？
4. 开始符号是否要求完整读到 EOF？
5. 后续语义分析需要区分的语法结构，是否已经显式出现在树中？
不要只看产生式“感觉合理”。应当主动写小反例：a-a-a、a+b*c、嵌套条件语句、空参数列表、尾逗号、未匹配分隔符。对每个输入画树或枚举推导。看似简短的文法，也可能藏着影响整个语言含义的二义性。