3.1 CFG、推导树与二义性：让嵌套结构只有一种解释

对任意深度的括号嵌套，有限状态不够用。先从描述规则入手：怎样用有限产生式表示 (())()，又让 1 + 2 * 3 按约定结合？同一串 token 如果能长出两棵树，后面的计算可就有分歧了。

本课目标

• 写出上下文无关文法并完成推导；
• 区分句型、句子、推导与语法树；
• 识别文法二义性；
• 用文法层次表达优先级和结合性。

1. 上下文无关文法

上下文无关文法仍是四元组：

$$G=(V,\mathrm{\Sigma },P,S),$$

但每条产生式左侧必须是单个非终结符：

$$A\to \alpha ,A\in V,\alpha \in (V\cup \mathrm{\Sigma }{)}^{\ast }.$$

“上下文无关”表示只要出现 $A$，规则就能替换它，不需要检查 $A$ 左右是什么。它不是说程序结构没有上下文，更不是说语义分析不需要环境。

平衡圆括号可由下列文法生成：

S → ( S ) S | ε

第一段 S 负责括号内部，第二段 S 负责后续相邻括号串：

S ⇒ (S)S ⇒ ((S)S)S ⇒ (()S)S ⇒ (())S
  ⇒ (())(S)S ⇒ (())()S ⇒ (())()

2. 句型、句子与推导顺序

从开始符号经过零步或多步得到的串叫句型，其中可以含终结符或非终结符；不再含非终结符的句型叫句子。

若每一步总替换最左侧非终结符，称为最左推导；总替换最右侧非终结符，称为最右推导。不同替换顺序可能只是同一棵语法树的不同遍历顺序，并不自动意味着二义性。

例如：

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

id + id * id 的最左推导为：

E ⇒ E + T
  ⇒ T + T
  ⇒ F + T
  ⇒ id + T
  ⇒ id + T * F
  ⇒ id + F * F
  ⇒ id + id * F
  ⇒ id + id * id

3. 语法树保留结构

语法树根节点是开始符号，内部节点是非终结符，叶节点从左到右组成输入字符串，表示空产生式的 $\epsilon$ 叶不贡献字符。上面的分层文法会把乘法放在更深的 T 子树中，从而得到：

       E
     / | \
    E  +  T
    |    /|\
    T   T * F
    |   |   |
    F   F   id
    |   |
   id  id

解析器通常不会把完整具体语法树原样交给后续阶段。括号、分号和中间非终结符对识别有用，但未必都需保留；第 6 章会把它压缩为 AST。

4. 二义性属于文法

若同一个句子存在两棵不同语法树，或等价地存在两个不同最左推导，文法就是二义的。

E → E + E | E * E | id

对 id + id * id，既能解释为：

id + (id * id)

也能解释为：

(id + id) * id

这不是解析器“随便选一个”就能可靠解决的问题。语言规范应规定优先级与结合性，文法或解析器配置再准确实现。

语言和文法要分开：同一种语言可能既有二义文法，也有无二义文法；还有一些上下文无关语言是固有二义的，不存在任何无二义 CFG。

5. 用层次表达优先级

分层文法：

Expr   → Expr + Term | Term
Term   → Term * Factor | Factor
Factor → ( Expr ) | id

Factor 表示标识符或括号表达式，Term 只能在这一层连接乘法，因而乘法比加法结合得更紧；这描述树的结构，不要求解析器先执行哪一步。左递归还让连续减法自然形成左结合结构：

Expr → Expr - Term | Term

a - b - c 解析为 (a - b) - c。若幂运算要右结合，可设计为：

Power → Primary ^ Power | Primary

文法结构表达的是语言规范，不应为了迎合某个解析器而悄悄改变语义。若递归下降不能直接处理左递归，需要做保持语言与结合性的变换，或改用循环实现对应层级。

6. 悬空 else

文法：

Stmt → if ( Expr ) Stmt
     | if ( Expr ) Stmt else Stmt
     | other

输入：

if (a) if (b) x else y

else 可以与内层或外层 if 配对。多数语言规定它绑定最近的未匹配 if。可以用 matched/unmatched 非终结符编码该规则，也可以让 LR 解析器通过明确的冲突解决规则实现。关键是规范、文法、解析器行为和格式化工具必须一致。

一种经典改写是：

Stmt      → Matched | Unmatched
Matched   → if ( Expr ) Matched else Matched | other
Unmatched → if ( Expr ) Stmt
          | if ( Expr ) Matched else Unmatched

7. 文法变换不等于消除二义性

递归下降常需消除直接左递归：

A → A α | β

当 $\alpha$ 非空，且这些 $\beta$ 分支不以 $A$ 开头时，可改写为：

A  → β A'
A' → α A' | ε

有共同前缀时可提取左公因子：

A → α β | α γ

改为：

A  → α A'
A' → β | γ

这只处理所列的直接左递归；间接左递归、空产生式带来的隐藏递归，以及 FIRST/FOLLOW 冲突仍要继续检查。

这些变换主要改善预测分析条件。它们不会自动消除所有二义性，也可能改变语法树形状；若 AST 构造依赖原结构，需要同步调整语义动作。

8. 通用 CFG 解析与工程子集

CFG 的成员资格是可判定的。CYK 可在文法转为 Chomsky 范式后用动态规划解析，固定文法时的经典时间复杂度为 $O(n^3)$，若同时计入产生式数量 $|P|$，常见实现为 $O(|P|n^3)$；空输入需按开始符号能否生成 $\epsilon$ 单独处理；Earley 对一般 CFG 也能工作，并会根据文法性质表现得更快。

工程中可选 LL/LR 文法与对应算法，或采用 PEG 及其有序选择语义。PEG 是另一种形式体系，不能直接当作 CFG 的一个子类；改用有序选择也可能改变接受语言。不能笼统地说“所有 CFG 都能线性解析”；线性行为依赖文法类别、算法和冲突处理。

常见误区

• 不同推导顺序就是二义性：要比较语法树或最左推导，而不是任意替换顺序。
• 消除左递归就消除了二义性：二者是不同性质。
• 运算符优先级只属于词法阶段：token 相同，树的结构由语法规则决定。
• CFG 包含类型规则：名称绑定和类型检查通常需要额外环境与语义规则。

练习

1. 为列表 [id, id, ...] 写 CFG，并允许空列表。
2. 分别写出左结合减法和右结合幂运算的文法。
3. 为 id + id * id 画分层文法的语法树。
4. 使用 matched/unmatched 文法推导一个嵌套 if，确认 else 的绑定位置。

小结

CFG 用递归产生式描述嵌套结构，语法树把字符串恢复为层次关系。二义性意味着同一输入存在不同结构解释，必须由语言规则而不是偶然的解析顺序解决。

下一课给这种递归结构配上一台机器：有限状态负责控制，栈保存尚未完成的嵌套。