第4章 自顶向下的分析

自顶向下分析从根（开始符号）到叶（终结符），是最左推导的过程。分为递归下降分析（手写）和 LL(1) 分析（表驱动）两种。

4.1 递归下降分析（Recursive-Descent Parsing）

基本思想

• 为每个非终结符编写一个递归过程
• 过程体根据产生式右部的结构选择匹配策略
• 通过向前看（lookahead）决定选择哪个产生式

伪代码模板

// 非终结符 A → α1 | α2 | ... | αn
function A():
    if lookahead ∈ First(α1):
        处理 α1 的代码
    else if lookahead ∈ First(α2):
        处理 α2 的代码
    ...
    else:
        error()

回溯分析程序

• 尝试一种可能，失败则回溯
• 指数级时间复杂度，不实用

预测分析程序

• 基于向前看符号预测唯一选择
• 线性时间复杂度
• 需要无左递归、无二义性的文法

消除左递归

原始: A → Aα | β
改写: A → βA'
      A' → αA' | ε

提取左因子

原始: A → αβ | αγ
改写: A → αA'
      A' → β | γ

4.2 LL(1) 分析

LL(1) 含义

• L：从左到右扫描输入
• L：产生最左推导
• 1：使用 1 个向前看符号

LL(1) 分析表驱动算法

算法要点：
1. 维护分析栈，初始为 $S
2. 每步：
   - 若栈顶 = 当前输入符号 → 匹配弹出
   - 若栈顶为非终结符 A → 查表 Table[A, lookahead]，用产生式右部替换 A
   - 若查表为空 → 错误
   - 若栈顶 = $ 且输入 = $ → 接受

LL(1) 分析过程示例

文法 S → (S)S | ε，输入串 ()：

步骤 | 分析栈     | 输入串  | 动作
─────┼────────────┼─────────┼──────────────
  1  | $S         | ()$     | 查表 S → (S)S
  2  | $S)S(      | ()$     | 匹配 (
  3  | $S)S       | )$      | 查表 S → ε
  4  | $S)        | )$      | 匹配 )
  5  | $S         | $       | 查表 S → ε
  6  | $          | $       | 接受

LL(1) 文法判定条件

文法 G 是 LL(1) 的当且仅当对于任意两个产生式 A → α | β：

1. First(α) ∩ First(β) = ∅
2. 若 β ⇒ ε，则 First(α) ∩ Follow(A) = ∅*

SELECT 集合

SELECT 集合是构造 LL(1) 分析表的直接工具，来自课件内容：

SELECT(A → α) =
  - 若 α 不能推导出 ε: 则 SELECT = First(α)
  - 若 α ⇒* ε: 则 SELECT = (First(α) - {ε}) ∪ Follow(A)

LL(1) 判定条件（SELECT 集形式）：

• 对任意非终结符 A 的两个不同产生式 A → α, A → β：
  • SELECT(A → α) ∩ SELECT(A → β) = ∅

LL(1) 分析表构造规则：

• 对每个产生式 A → α：
  • 对每个终结符 a ∈ SELECT(A → α)（a ≠ ε）：
    • Table[A, a] = A → α
  • 若 ε ∈ SELECT(A → α)：
    • Table[A, $] = A → α

SELECT 集计算示例

文法：E → TE', E' → +TE' | ε, T → FT', T' → *FT' | ε, F → (E) | id

SELECT(E → TE')     = First(TE') = {(, id}
SELECT(E' → +TE')   = First(+TE') = {+}
SELECT(E' → ε)      = Follow(E') = {$, )}
SELECT(T → FT')     = First(FT') = {(, id}
SELECT(T' → *FT')   = First(*FT') = {*}
SELECT(T' → ε)      = Follow(T') = {$, +, )}
SELECT(F → (E))     = First((E)) = {(}
SELECT(F → id)      = First(id) = {id}

4.3 First 集合和 Follow 集合

First 集合定义

First(α) = 可以从 α 推导出的串的第一个终结符的集合（若 α ⇒* ε，则 ε ∈ First(α)）

First 集合计算算法

1. 若 X ∈ T，则 First(X) = {X}
2. 若 X → ε 是产生式，则 ε ∈ First(X)
3. 若 X → Y1Y2...Yk 是产生式：
   a. 将 First(Y1) 中非 ε 元素加入 First(X)
   b. 若 Y1 ⇒* ε，则将 First(Y2) 中非 ε 元素加入 First(X)
   c. 类似继续... 若所有 Yi ⇒* ε，则将 ε 加入 First(X)

Follow 集合定义

Follow(A) = 在推导中可能紧跟在 A 之后的终结符集合

• $ ∈ Follow(S)（S 为开始符号）
• 若 A → αBβ，则 First(β) 中非 ε 元素 ∈ Follow(B)
• 若 A → αB 或 A → αBβ 且 β ⇒* ε，则 Follow(A) ⊆ Follow(B)

Follow 集合计算算法

1. $ ∈ Follow(S)
2. 若 A → αBβ，则 First(β) - {ε} ⊆ Follow(B)
3. 若 A → αB 或 A → αBβ 且 ε ∈ First(β)，
   则 Follow(A) ⊆ Follow(B)
4. 重复 2~3 直到所有 Follow 不再变化

4.4 TINY 语言的递归下降分析程序

• 使用 EBNF 文法
• 语法树节点类型：StmtK（IfK, RepeatK, AssignK, ReadK, WriteK）、ExpK（OpK, ConstK, IdK）
• 实用程序过程：newStmtNode()、newExpNode()、copyString()

4.5 自顶向下分析中的错误校正

应急方式（Panic Mode）

• 为每个非终结符定义同步记号集合（Sync Set）
• 当发现错误时，跳过输入记号直到遇到同步记号
• 同步集合 ≈ Follow(A) ∪ First(A)

错误类型

• 栈顶非终结符无法匹配当前输入
• 匹配期待与实际输入不一致
• 栈提前空但输入未结束

考试重点

★★★ 第一梯队（必考）

★★☆ 第二梯队

常见陷阱

• 先计算 First，再计算 Follow
• ε 属于 First 但不属于 Follow（仅用于规则判定）
• 提取左因子后，Follow 可能变化
• 不要忘记 $ 号
• 不是所有左递归的消除都能得到 LL(1)