语法分析概述

语法分析（Syntax Analysis 或 Parsing）是编译器的第二个阶段，它接收词法分析器产生的单词符号序列，检查这些单词符号的组合是否符合语言的语法规则（由文法定义），并构造出语法树（或抽象语法树）。

语法分析的任务

  1. 检查语法正确性：判断输入的程序是否符合语言的语法规则
  2. 构造语法树：为正确的程序构造语法树（推导树或抽象语法树）
  3. 报告语法错误：对于错误的输入，指出错误位置和可能的原因

语法分析的分类

根据构造语法树的方向，语法分析分为两大类：

1. 自顶向下分析（Top-Down Parsing）

  • 方向：从文法的开始符号 $S$ 出发，推导输入串
  • 推导方式：最左推导
  • 构造语法树：从根节点开始，逐步向下扩展叶节点
  • 代表方法：
    • 递归下降分析（Recursive Descent Parsing）
    • LL(k) 分析（LL：Left-to-right, Leftmost derivation）

思想：尝试为输入串构造一个最左推导序列。

2. 自底向上分析（Bottom-Up Parsing）

  • 方向：从输入串出发，归约到开始符号 $S$
  • 推导方式：最右推导的逆过程（规范归约）
  • 构造语法树：从叶节点开始，逐步向上归约到根节点
  • 代表方法：
    • LR(k) 分析（LR：Left-to-right, Rightmost derivation）
    • LALR、SLR 等变体

思想：尝试为输入串构造一个最右推导的逆序列。

对比

特性 自顶向下 自底向上
构造方向 从根到叶 从叶到根
推导方式 最左推导 最右推导的逆
实现难度 较简单（递归下降易于手工实现） 较复杂（通常使用工具生成）
适用文法范围 较窄（LL(k) 文法） 较广（LR(k) 文法）
错误处理 较容易 较困难
应用 手工编写的编译器、教学 工业级编译器（Yacc、Bison）

自顶向下分析概述

基本思想

自顶向下分析：从文法的开始符号 $S$ 出发，反复使用产生式对当前句型中的非终结符进行替换，直到得到与输入串匹配的句型。

分析过程示例

文法 $G[E]$：

$$
\begin{aligned}
E &\rightarrow E + T\ |\ T \newline
T &\rightarrow T * F\ |\ F \newline
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

输入串：$\text{id} + \text{id} * \text{id}$

最左推导过程：

$$
\begin{aligned}
E &\Rightarrow_{lm} E + T \newline
&\Rightarrow_{lm} T + T \newline
&\Rightarrow_{lm} F + T \newline
&\Rightarrow_{lm} \text{id} + T \newline
&\Rightarrow_{lm} \text{id} + T * F \newline
&\Rightarrow_{lm} \text{id} + F * F \newline
&\Rightarrow_{lm} \text{id} + \text{id} * F \newline
&\Rightarrow_{lm} \text{id} + \text{id} * \text{id}
\end{aligned}
$$

每一步选择最左边的非终结符进行替换。

面临的关键问题

1. 选择问题（Choice Problem）

对于非终结符 $A$，可能有多个产生式：$A\rightarrow\alpha_1\ |\ \alpha_2\ |\ …\ |\ \alpha_n$

如何选择正确的产生式？

  • 不确定的分析：尝试所有可能的选择（回溯）
  • 确定的分析：根据当前输入符号，唯一确定选择哪个产生式

2. 左递归问题（Left Recursion Problem）

如果文法中有左递归产生式（如 $A\rightarrow A\alpha$），自顶向下分析会陷入无限循环。

例如：$E\rightarrow E + T$

  • 从 $E$ 出发：$E\Rightarrow E + T\Rightarrow E + T + T\Rightarrow…$（无限展开）

解决方法：消除左递归。

3. 左公因子问题（Left Factoring Problem）

如果多个产生式有相同的前缀（左公因子），难以决定选择哪个。

例如：$A\rightarrow\alpha\beta_1\ |\ \alpha\beta_2$

看到输入符号属于 $\alpha$ 时，无法确定是 $\beta_1$ 还是 $\beta_2$。

解决方法：提取左公因子。

文法转换：为自顶向下分析做准备

要使文法适合自顶向下分析，需要进行两种关键的文法转换。

消除左递归

左递归的定义

直接左递归：产生式形如 $A\rightarrow A\alpha\ |\ \beta$

间接左递归：存在推导链 $A\Rightarrow^+A\alpha$

例如：

$$
\begin{aligned}
S &\rightarrow Aa\ |\ b \newline
A &\rightarrow Sc\ |\ d
\end{aligned}
$$

有 $S\Rightarrow Aa\Rightarrow Sca$（间接左递归）

消除直接左递归

原文法：

$$
A\rightarrow A\alpha_1\ |\ A\alpha_2\ |\ …\ |\ A\alpha_m\ |\ \beta_1\ |\ \beta_2\ |\ …\ |\ \beta_n
$$

其中 $\beta_i$ 都不以 $A$ 开头。

改写后的文法：
I
$$
\begin{aligned}
A &\rightarrow \beta_1A’\ |\ \beta_2A’\ |\ …\ |\ \beta_nA’ \newline
A’ &\rightarrow \alpha_1A’\ |\ \alpha_2A’\ |\ …\ |\ \alpha_mA’\ |\ \varepsilon
\end{aligned}
$$

核心思想：将左递归改为右递归，引入新的非终结符 $A’$。

示例：消除表达式文法的左递归

原文法（有左递归）：

$$
\begin{aligned}
E &\rightarrow E + T\ |\ T \newline
T &\rightarrow T * F\ |\ F \newline
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

步骤 1：消除 $E$ 的左递归

  • 识别：$A = E$，$\alpha = +T$，$\beta = T$
  • 改写：
    $$
    \begin{aligned}
    E &\rightarrow TE’ \newline
    E’ &\rightarrow +TE’\ |\ \varepsilon
    \end{aligned}
    $$

步骤 2：消除 $T$ 的左递归

  • 识别：$A = T$，$\alpha = *F$，$\beta = F$
  • 改写：
    $$
    \begin{aligned}
    T &\rightarrow FT’ \newline
    T’ &\rightarrow *FT’\ |\ \varepsilon
    \end{aligned}
    $$

改写后的文法（无左递归）：

$$
\begin{aligned}
E &\rightarrow TE’ \newline
E’ &\rightarrow +TE’\ |\ \varepsilon \newline
T &\rightarrow FT’ \newline
T’ &\rightarrow *FT’\ |\ \varepsilon \newline
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

消除间接左递归

算法（适用于消除所有左递归，包括直接和间接）：

输入：文法 G，其非终结符为 A₁, A₂, ..., Aₙ

for i = 1 to n:
    for j = 1 to i-1:
        将每个形如 Aᵢ → Aⱼγ 的产生式
        替换为 Aᵢ → δ₁γ | δ₂γ | ... | δₖγ
        其中 Aⱼ → δ₁ | δ₂ | ... | δₖ 是 Aⱼ 的所有产生式

    消除 Aᵢ 的直接左递归（如果有）

输出：等价的无左递归文法

关键思想：

  1. 按顺序处理非终结符 $A_1, A_2, …, A_n$
  2. 对于 $A_i$，消除它对 $A_1, …, A_{i-1}$ 的依赖（代入）
  3. 消除 $A_i$ 的直接左递归

提取左公因子

左公因子的定义

如果产生式有相同的前缀，称为左公因子：

$$
A\rightarrow\alpha\beta_1\ |\ \alpha\beta_2\ |\ …\ |\ \alpha\beta_n\ |\ \gamma
$$

其中 $\alpha\neq\varepsilon$，且 $\gamma$ 不以 $\alpha$ 开头。

为什么要提取左公因子？

在自顶向下分析中，看到输入符号属于 $\alpha$ 时，无法确定后续是 $\beta_1$、$\beta_2$ 还是 $\beta_n$，导致需要回溯或无法确定选择。

提取左公因子的方法

改写为：

$$
\begin{aligned}
A &\rightarrow \alpha A’\ |\ \gamma \newline
A’ &\rightarrow \beta_1\ |\ \beta_2\ |\ …\ |\ \beta_n
\end{aligned}
$$

先匹配公共前缀 $\alpha$，再通过 $A’$ 区分后续的不同选择。

示例

原文法：

$$
S\rightarrow \text{if}\ E\ \text{then}\ S\ |\ \text{if}\ E\ \text{then}\ S\ \text{else}\ S\ |\ \text{other}
$$

左公因子：$\text{if}\ E\ \text{then}\ S$

改写后：

$$
\begin{aligned}
S &\rightarrow \text{if}\ E\ \text{then}\ S\ S’\ |\ \text{other} \newline
S’ &\rightarrow \text{else}\ S\ |\ \varepsilon
\end{aligned}
$$

注意：这里 $S’$ 可以是 $\varepsilon$（没有 else）或 $\text{else}\ S$（有 else）。

FIRST 和 FOLLOW 集合

为了实现确定的自顶向下分析，需要计算两个关键的集合：FIRST 和 FOLLOW。

FIRST 集合

定义

对于文法符号串 $\alpha$（$\alpha\in V^*$），$\text{FIRST}(\alpha)$ 定义为：

$$
\text{FIRST}(\alpha)={a\ |\ \alpha\Rightarrow^a…,\ a\in V_T}\cup{\varepsilon\ |\ \alpha\Rightarrow^\varepsilon}
$$

通俗理解：$\text{FIRST}(\alpha)$ 是从 $\alpha$ 推导出的所有符号串的第一个终结符的集合（如果 $\alpha$ 能推导出 $\varepsilon$，则 $\varepsilon$ 也在其中）。

计算方法

1. 对于终结符 $a$

$$
\text{FIRST}(a)={a}
$$

2. 对于非终结符 $A$

初始化：$\text{FIRST}(A)=\emptyset$

对于每个产生式 $A\rightarrow X_1X_2…X_n$：

  • 如果 $X_1$ 是终结符 $a$：

    $$
    \text{FIRST}(A)\leftarrow\text{FIRST}(A)\cup{a}
    $$

  • 如果 $X_1$ 是非终结符：

    • 将 $\text{FIRST}(X_1)-{\varepsilon}$ 加入 $\text{FIRST}(A)$
    • 如果 $X_1$ 可以推导出 $\varepsilon$（即 $\varepsilon\in\text{FIRST}(X_1)$），继续考察 $X_2$：
      • 将 $\text{FIRST}(X_2)-{\varepsilon}$ 加入 $\text{FIRST}(A)$
      • 如果 $X_2$ 也可推导出 $\varepsilon$，继续考察 $X_3$…
    • 如果 $X_1, X_2, …, X_n$ 都可以推导出 $\varepsilon$：
      $$
      \text{FIRST}(A)\leftarrow\text{FIRST}(A)\cup{\varepsilon}
      $$

  • 特殊情况：$A\rightarrow\varepsilon$：
    $$
    \text{FIRST}(A)\leftarrow\text{FIRST}(A)\cup{\varepsilon}
    $$

算法伪码：

for each 非终结符 A:
    FIRST(A) = {}

repeat:
    for each 产生式 A → X₁X₂...Xₙ:
        i = 1
        while i <= n:
            if Xᵢ 是终结符 a:
                FIRST(A).add(a)
                break
            else:  # Xᵢ 是非终结符
                FIRST(A).add(FIRST(Xᵢ) - {ε})
                if ε not in FIRST(Xᵢ):
                    break
                i += 1

        if i > n:  # 所有 X₁...Xₙ 都能推导出 ε
            FIRST(A).add(ε)
until FIRST 集合不再变化

3. 对于符号串 $\alpha=X_1X_2…X_n$

计算 $\text{FIRST}(\alpha)$：

FIRST(α) = {}
i = 1
while i <= n:
    FIRST(α).add(FIRST(Xᵢ) - {ε})
    if ε not in FIRST(Xᵢ):
        break
    i += 1

if i > n:  # 所有符号都能推导出 ε
    FIRST(α).add(ε)

示例

文法：

$$
\begin{aligned}
E &\rightarrow TE’ \newline
E’ &\rightarrow +TE’\ |\ \varepsilon \newline
T &\rightarrow FT’ \newline
T’ &\rightarrow *FT’\ |\ \varepsilon \newline
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

计算 FIRST 集合：

  1. $\text{FIRST}(F)$：

    • $F\rightarrow(E)$：加入 ${(}$
    • $F\rightarrow\text{id}$：加入 ${\text{id}}$
    • 结果：$\text{FIRST}(F)={(,\ \text{id}}$

  2. $\text{FIRST}(T’)$：

    • $T’\rightarrow FT’$：加入 ${}$
    • $T’\rightarrow\varepsilon$：加入 ${\varepsilon}$
    • 结果：$\text{FIRST}(T’)={*,\ \varepsilon}$

  3. $\text{FIRST}(T)$：

    • $T\rightarrow FT’$：先加入 $\text{FIRST}(F)={(,\ \text{id}}$
    • $F$ 不能推导出 $\varepsilon$，停止
    • 结果：$\text{FIRST}(T)={(,\ \text{id}}$

  4. $\text{FIRST}(E’)$：

    • $E’\rightarrow +TE’$：加入 ${+}$
    • $E’\rightarrow\varepsilon$：加入 ${\varepsilon}$
    • 结果：$\text{FIRST}(E’)={+,\ \varepsilon}$

  5. $\text{FIRST}(E)$：

    • $E\rightarrow TE’$：先加入 $\text{FIRST}(T)={(,\ \text{id}}$
    • $T$ 不能推导出 $\varepsilon$，停止
    • 结果：$\text{FIRST}(E)={(,\ \text{id}}$

FOLLOW 集合

定义

对于非终结符 $A$，$\text{FOLLOW}(A)$ 定义为：

$$
\text{FOLLOW}(A)={a\ |\ S\Rightarrow^…Aa…,\ a\in V_T}\cup{$\ |\ S\Rightarrow^…A}
$$

通俗理解：$\text{FOLLOW}(A)$ 是在某个句型中，紧跟在 $A$ 之后可能出现的终结符的集合（如果 $A$ 可以出现在句型末尾，则包含 $$$，表示输入结束符）。

计算方法

初始化：

  1. $\text{FOLLOW}(S)={$}$（$S$ 是开始符号，$$$ 表示输入结束）
  2. 对于其他非终结符 $A$，$\text{FOLLOW}(A)=\emptyset$

迭代规则：

对于每个产生式 $A\rightarrow\alpha B\beta$（其中 $B$ 是非终结符）：

  1. 规则 1：将 $\text{FIRST}(\beta)-{\varepsilon}$ 加入 $\text{FOLLOW}(B)$

  2. 规则 2：如果 $\beta=\varepsilon$ 或 $\varepsilon\in\text{FIRST}(\beta)$（即 $\beta$ 可以推导出 $\varepsilon$），则将 $\text{FOLLOW}(A)$ 加入 $\text{FOLLOW}(B)$

重复迭代，直到所有 FOLLOW 集合不再变化。

算法伪码：

FOLLOW(S) = {$}  # S 是开始符号
for each 非终结符 A (A ≠ S):
    FOLLOW(A) = {}

repeat:
    for each 产生式 A → α₁α₂...αₙ:
        for i = 1 to n:
            if αᵢ 是非终结符 B:
                β = αᵢ₊₁αᵢ₊₂...αₙ
                FOLLOW(B).add(FIRST(β) - {ε})

                if ε ∈ FIRST(β):  # β 可以推导出 ε
                    FOLLOW(B).add(FOLLOW(A))
until FOLLOW 集合不再变化

示例

使用前面的文法：

$$
\begin{aligned}
E &\rightarrow TE’ \newline
E’ &\rightarrow +TE’\ |\ \varepsilon \newline
T &\rightarrow FT’ \newline
T’ &\rightarrow *FT’\ |\ \varepsilon \newline
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

计算 FOLLOW 集合：

初始化：

  • $\text{FOLLOW}(E)={$}$（$E$ 是开始符号）

规则应用：

  1. $E\rightarrow TE’$：

    • $\text{FOLLOW}(T)\leftarrow\text{FIRST}(E’)-{\varepsilon}={+}$
    • $\varepsilon\in\text{FIRST}(E’)$，所以 $\text{FOLLOW}(T)\leftarrow\text{FOLLOW}(E)={$}$
    • 结果：$\text{FOLLOW}(T)={+,\ $}$
    • $E’$ 在末尾，$\text{FOLLOW}(E’)\leftarrow\text{FOLLOW}(E)={$}$

  2. $E’\rightarrow +TE’$：

    • $\text{FOLLOW}(T)\leftarrow\text{FIRST}(E’)-{\varepsilon}={+}$（已有）
    • $\varepsilon\in\text{FIRST}(E’)$，所以 $\text{FOLLOW}(T)\leftarrow\text{FOLLOW}(E’)={$}$（已有）
    • $E’$ 在末尾，$\text{FOLLOW}(E’)\leftarrow\text{FOLLOW}(E’)$（无新增）

  3. $T\rightarrow FT’$：

    • $\text{FOLLOW}(F)\leftarrow\text{FIRST}(T’)-{\varepsilon}={*}$
    • $\varepsilon\in\text{FIRST}(T’)$，所以 $\text{FOLLOW}(F)\leftarrow\text{FOLLOW}(T)={+,\ $}$
    • 结果：$\text{FOLLOW}(F)={*,\ +,\ $}$
    • $T’$ 在末尾，$\text{FOLLOW}(T’)\leftarrow\text{FOLLOW}(T)={+,\ $}$

  4. $T’\rightarrow *FT’$：

    • $\text{FOLLOW}(F)\leftarrow\text{FIRST}(T’)-{\varepsilon}={*}$（已有）
    • $\varepsilon\in\text{FIRST}(T’)$，所以 $\text{FOLLOW}(F)\leftarrow\text{FOLLOW}(T’)={+,\ $}$（已有）
    • $T’$ 在末尾，$\text{FOLLOW}(T’)\leftarrow\text{FOLLOW}(T’)$（无新增）

  5. $F\rightarrow(E)$：

    • $\text{FOLLOW}(E)\leftarrow{)}$
    • 更新：$\text{FOLLOW}(E)={$,\ )}$

最终结果：

非终结符 FOLLOW 集合
$E$ ${$,\ )}$
$E’$ ${$,\ )}$
$T$ ${+,\ $,\ )}$
$T’$ ${+,\ $,\ )}$
$F$ ${*,\ +,\ $,\ )}$

LL(1) 文法

LL(1) 的含义

LL(1)：

  • 第一个 L：Left-to-right，从左到右扫描输入
  • 第二个 L：Leftmost derivation，最左推导
  • (1)：向前看 1 个输入符号

LL(1) 文法是一类能够通过向前看一个符号就能确定唯一的产生式进行最左推导的文法。

LL(1) 文法的定义

文法 $G$ 是 LL(1) 文法，当且仅当对于 $G$ 的任意两个不同的产生式：

$$
A\rightarrow\alpha\ \ |\ \ \beta
$$

满足以下条件：

条件 1

$$
\text{FIRST}(\alpha)\cap\text{FIRST}(\beta)=\emptyset
$$

即两个产生式右部的 FIRST 集合不相交。

条件 2

如果 $\varepsilon\in\text{FIRST}(\alpha)$（即 $\alpha$ 能推导出 $\varepsilon$），则：

$$
\text{FIRST}(\beta)\cap\text{FOLLOW}(A)=\emptyset
$$

（如果 $\varepsilon\in\text{FIRST}(\beta)$，也要满足 $\text{FIRST}(\alpha)\cap\text{FOLLOW}(A)=\emptyset$）

通俗理解：

  • 条件 1：看到某个输入符号，能唯一确定选择 $\alpha$ 还是 $\beta$
  • 条件 2：如果 $\alpha$ 可以为空（推导出 $\varepsilon$），那么 $A$ 后面跟的符号不能与 $\beta$ 的开始符号冲突

LL(1) 文法的判别

判别步骤

  1. 消除左递归（如果有）
  2. 提取左公因子（如果有）
  3. 计算所有非终结符的 FIRST 和 FOLLOW 集合
  4. 检查 LL(1) 条件：
    • 对于每个非终结符 $A$ 的所有产生式 $A\rightarrow\alpha_1\ |\ \alpha_2\ |\ …\ |\ \alpha_n$
    • 检查 $\text{FIRST}(\alpha_i)\cap\text{FIRST}(\alpha_j)=\emptyset$（$i\neq j$）
    • 如果某个 $\alpha_i$ 能推导出 $\varepsilon$，检查 $\text{FIRST}(\alpha_i)\cap\text{FOLLOW}(A)=\emptyset$

示例：判别 LL(1) 文法

文法：

$$
\begin{aligned}
E &\rightarrow TE’ \newline
E’ &\rightarrow +TE’\ |\ \varepsilon \newline
T &\rightarrow FT’ \newline
T’ &\rightarrow *FT’\ |\ \varepsilon \newline
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

检查 LL(1) 条件：

  1. $E$ 的产生式：$E\rightarrow TE’$（只有一个，无需检查）

  2. $E’$ 的产生式：$E’\rightarrow +TE’\ |\ \varepsilon$

    • $\text{FIRST}(+TE’)={+}$
    • $\text{FIRST}(\varepsilon)={\varepsilon}$
    • ${+}\cap{\varepsilon}=\emptyset$ ✓
    • $\varepsilon\in\text{FIRST}(\varepsilon)$，检查 ${+}\cap\text{FOLLOW}(E’)={+}\cap{$,\ )}=\emptyset$ ✓

  3. $T$ 的产生式：$T\rightarrow FT’$（只有一个，无需检查）

  4. $T’$ 的产生式：$T’\rightarrow *FT’\ |\ \varepsilon$

    • $\text{FIRST}(FT’)={}$
    • $\text{FIRST}(\varepsilon)={\varepsilon}$
    • ${*}\cap{\varepsilon}=\emptyset$ ✓
    • $\varepsilon\in\text{FIRST}(\varepsilon)$，检查 ${}\cap\text{FOLLOW}(T’)={}\cap{+,\ $,\ )}=\emptyset$ ✓

  5. $F$ 的产生式：$F\rightarrow(E)\ |\ \text{id}$

    • $\text{FIRST}((E))={(}$
    • $\text{FIRST}(\text{id})={\text{id}}$
    • ${(}\cap{\text{id}}=\emptyset$ ✓

结论：该文法是 LL(1) 文法。

非 LL(1) 文法到 LL(1) 文法的等价变换

常见的非 LL(1) 情况

  1. 含有左递归
  2. 含有左公因子
  3. FIRST 集合冲突
  4. FIRST-FOLLOW 冲突

转换策略

策略 1：消除左递归

如前所述，使用左递归消除算法。

策略 2：提取左公因子

如前所述，提取公共前缀。

策略 3：改写文法消除 FIRST 冲突

示例：

原文法（非 LL(1)）：

$$
S\rightarrow iEtS\ |\ iEtSeS\ |\ a
$$

其中 $i$ 表示 if，$E$ 表示表达式，$t$ 表示 then，$e$ 表示 else，$S$ 表示语句，$a$ 表示其他语句。

问题：$\text{FIRST}(iEtS)={i}$，$\text{FIRST}(iEtSeS)={i}$，有冲突。

提取左公因子后：

$$
\begin{aligned}
S &\rightarrow iEtSS’\ |\ a \newline
S’ &\rightarrow eS\ |\ \varepsilon
\end{aligned}
$$

现在：

  • $\text{FIRST}(eS)={e}$
  • $\text{FIRST}(\varepsilon)={\varepsilon}$
  • ${e}\cap{\varepsilon}=\emptyset$ ✓
  • 检查 FIRST-FOLLOW：${e}\cap\text{FOLLOW}(S’)={e}\cap{$,\ e}={e}\neq\emptyset$ ✗

仍然不是 LL(1)！这是悬挂 else 问题。

解决方法：引入”匹配”和”未匹配”语句的概念（更复杂的文法改写，或使用优先级规则）。

策略 4：使用语义信息或优先级

有些语法冲突（如悬挂 else）无法通过单纯的文法改写完全消除。实际编译器通常采用：

  • 优先级规则：else 匹配最近的 if
  • 语义动作：在语法分析中嵌入额外的判断逻辑

确定的自顶向下分析思想

确定的自顶向下分析（Deterministic Top-Down Parsing）是指在分析过程中，不需要回溯，能够通过向前看有限个输入符号（通常是 1 个），唯一确定应该使用哪个产生式进行推导。

核心思想

对于非终结符 $A$，假设有多个产生式：

$$
A\rightarrow\alpha_1\ |\ \alpha_2\ |\ …\ |\ \alpha_n
$$

当需要展开 $A$ 时，根据当前输入符号 $a$，选择唯一的产生式 $A\rightarrow\alpha_i$：

$$
a\in\text{FIRST}(\alpha_i)\ \ \text{或}\ \ (\varepsilon\in\text{FIRST}(\alpha_i)\ \text{且}\ a\in\text{FOLLOW}(A))
$$

预测分析表（LL(1) Parsing Table）

预测分析表是实现确定自顶向下分析的核心数据结构。

构造方法

对于文法 $G$ 的每个产生式 $A\rightarrow\alpha$：

  1. 对于 $\text{FIRST}(\alpha)$ 中的每个终结符 $a$（$a\neq\varepsilon$）：

    $$
    M[A,\ a]=A\rightarrow\alpha
    $$

  2. 如果 $\varepsilon\in\text{FIRST}(\alpha)$，对于 $\text{FOLLOW}(A)$ 中的每个符号 $b$（包括 $$$）：
    $$
    M[A,\ b]=A\rightarrow\alpha
    $$

示例：构造预测分析表

使用前面的文法：

$$
\begin{aligned}
E &\rightarrow TE’ \newline
E’ &\rightarrow +TE’\ |\ \varepsilon \newline
T &\rightarrow FT’ \newline
T’ &\rightarrow *FT’\ |\ \varepsilon \newline
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

构造过程：

  1. $E\rightarrow TE’$：

    • $\text{FIRST}(TE’)={(,\ \text{id}}$
    • $M[E,\ (]=E\rightarrow TE’$
    • $M[E,\ \text{id}]=E\rightarrow TE’$

  2. $E’\rightarrow +TE’$：

    • $\text{FIRST}(+TE’)={+}$
    • $M[E’,\ +]=E’\rightarrow +TE’$

  3. $E’\rightarrow\varepsilon$：

    • $\varepsilon\in\text{FIRST}(\varepsilon)$
    • $\text{FOLLOW}(E’)={$,\ )}$
    • $M[E’,\ $]=E’\rightarrow\varepsilon$
    • $M[E’,\ )]=E’\rightarrow\varepsilon$

  4. $T\rightarrow FT’$：

    • $\text{FIRST}(FT’)={(,\ \text{id}}$
    • $M[T,\ (]=T\rightarrow FT’$
    • $M[T,\ \text{id}]=T\rightarrow FT’$

  5. $T’\rightarrow *FT’$：

    • $\text{FIRST}(FT’)={}$
    • $M[T’,\ *]=T’\rightarrow *FT’$

  6. $T’\rightarrow\varepsilon$：

    • $\varepsilon\in\text{FIRST}(\varepsilon)$
    • $\text{FOLLOW}(T’)={+,\ $,\ )}$
    • $M[T’,\ +]=T’\rightarrow\varepsilon$
    • $M[T’,\ $]=T’\rightarrow\varepsilon$
    • $M[T’,\ )]=T’\rightarrow\varepsilon$

  7. $F\rightarrow(E)$：

    • $\text{FIRST}((E))={(}$
    • $M[F,\ (]=F\rightarrow(E)$

  8. $F\rightarrow\text{id}$：

    • $\text{FIRST}(\text{id})={\text{id}}$
    • $M[F,\ \text{id}]=F\rightarrow\text{id}$

预测分析表：

id + * ( ) $
E $E\rightarrow TE’$ $E\rightarrow TE’$
E’ $E’\rightarrow +TE’$ $E’\rightarrow\varepsilon$ $E’\rightarrow\varepsilon$
T $T\rightarrow FT’$ $T\rightarrow FT’$
T’ $T’\rightarrow\varepsilon$ $T’\rightarrow *FT’$ $T’\rightarrow\varepsilon$ $T’\rightarrow\varepsilon$
F $F\rightarrow\text{id}$ $F\rightarrow(E)$

LL(1) 文法的充要条件

文法 $G$ 是 LL(1) 文法 $\Leftrightarrow$ 预测分析表 $M$ 中每个条目最多包含一个产生式

如果某个 $M[A,\ a]$ 包含多个产生式，说明有冲突，文法不是 LL(1)。

LL(1) 分析的实现

LL(1) 分析有两种主要实现方式：递归下降分析和表驱动分析。

递归下降 LL(1) 分析程序

基本思想

为每个非终结符 $A$ 编写一个递归函数 A()，函数内部根据当前输入符号选择相应的产生式进行展开。

构造方法

对于非终结符 $A$ 的产生式：

$$
A\rightarrow\alpha_1\ |\ \alpha_2\ |\ …\ |\ \alpha_n
$$

编写函数：

void A() {
    switch (lookahead) {  // lookahead 是当前输入符号
        case a₁:  // a₁ ∈ FIRST(α₁)
            // 匹配 α₁
            break;
        case a₂:  // a₂ ∈ FIRST(α₂)
            // 匹配 α₂
            break;
        // ...
        case aₖ:  // aₖ ∈ FOLLOW(A) 且 ε ∈ FIRST(某个αᵢ)
            // 使用 ε 产生式（不消耗输入）
            break;
        default:
            error("语法错误");
    }
}

示例：为表达式文法编写递归下降分析程序

文法：

$$
\begin{aligned}
E &\rightarrow TE’ \newline
E’ &\rightarrow +TE’\ |\ \varepsilon \newline
T &\rightarrow FT’ \newline
T’ &\rightarrow *FT’\ |\ \varepsilon \newline
F &\rightarrow (E)\ |\ \text{id}
\end{aligned}
$$

C 语言实现：

#include <stdio.h>
#include <stdlib.h>

char lookahead;  // 当前输入符号

void error(const char *msg) {
    fprintf(stderr, "错误: %s\n", msg);
    exit(1);
}

void match(char t) {
    if (lookahead == t) {
        lookahead = getchar();  // 读取下一个符号
    } else {
        error("字符不匹配");
    }
}

void E();   // 前向声明
void Ep();
void T();
void Tp();
void F();

void E() {
    // E → TE'
    T();
    Ep();
}

void Ep() {
    // E' → +TE' | ε
    if (lookahead == '+') {
        match('+');
        T();
        Ep();
    }
    // else: ε 产生式，不做任何操作
}

void T() {
    // T → FT'
    F();
    Tp();
}

void Tp() {
    // T' → *FT' | ε
    if (lookahead == '*') {
        match('*');
        F();
        Tp();
    }
    // else: ε 产生式
}

void F() {
    // F → (E) | id
    if (lookahead == '(') {
        match('(');
        E();
        match(')');
    } else if (lookahead == 'i') {  // 用 'i' 表示 id
        match('i');
    } else {
        error("期望 ( 或 id");
    }
}

int main() {
    printf("输入表达式（用 i 表示 id，以换行结束）：\n");
    lookahead = getchar();
    E();
    if (lookahead == '\n') {
        printf("分析成功！\n");
    } else {
        error("输入未结束");
    }
    return 0;
}

测试：

  • 输入：i+i*i（回车）
  • 输出：分析成功！

递归下降分析的优缺点

优点：

  • 实现简单，易于理解
  • 易于手工编写
  • 便于嵌入语义动作（如构造抽象语法树、生成中间代码）
  • 错误处理灵活

缺点：

  • 需要为每个非终结符编写一个函数，文法较大时代码量大
  • 递归调用可能导致栈溢出（对于深度嵌套的表达式）

表驱动的 LL(1) 分析程序

基本思想

使用一个显式的栈和预测分析表 $M$，模拟最左推导过程。

数据结构

  1. 输入缓冲区：存储输入符号串（以 $$$ 结束）
  2. 分析栈：存储文法符号（初始时包含 $$$ 和开始符号 $S$）
  3. 预测分析表 $M$：$M[A,\ a]$ 给出当栈顶为 $A$、输入为 $a$ 时应该使用的产生式

算法

输入：字符串 w$ 和预测分析表 M
输出：如果 w ∈ L(G)，输出最左推导；否则报错

初始化：
    栈 = [$, S]  // S 是开始符号，$ 在栈底
    输入指针 ip 指向 w 的第一个符号

repeat:
    X = 栈顶符号
    a = ip 指向的符号

    if X 是终结符 or X == $:
        if X == a:
            栈.pop()
            ip++  // 匹配成功，继续
        else:
            error("字符不匹配")

    else if X 是非终结符:
        if M[X, a] == X → Y₁Y₂...Yₖ:
            栈.pop()
            栈.push(Yₖ, Yₖ₋₁, ..., Y₁)  // 逆序入栈
            输出: X → Y₁Y₂...Yₖ
        else if M[X, a] == X → ε:
            栈.pop()
            输出: X → ε
        else:
            error("语法错误")

until X == $ and a == $

示例：表驱动分析过程

输入：id + id * id $

文法和预测分析表同前

分析过程：

步骤 栈 输入 动作
1 $ E id + id * id $ $M[E,\ \text{id}]=E\rightarrow TE’$
2 $ E' T id + id * id $ $M[T,\ \text{id}]=T\rightarrow FT’$
3 $ E' T' F id + id * id $ $M[F,\ \text{id}]=F\rightarrow\text{id}$
4 $ E' T' id id + id * id $ 匹配 id
5 $ E' T' + id * id $ $M[T’,\ +]=T’\rightarrow\varepsilon$
6 $ E' + id * id $ $M[E’,\ +]=E’\rightarrow +TE’$
7 $ E' T + + id * id $ 匹配 +
8 $ E' T id * id $ $M[T,\ \text{id}]=T\rightarrow FT’$
9 $ E' T' F id * id $ $M[F,\ \text{id}]=F\rightarrow\text{id}$
10 $ E' T' id id * id $ 匹配 id
11 $ E' T' * id $ $M[T’,\ *]=T’\rightarrow *FT’$
12 $ E' T' F * * id $ 匹配 *
13 $ E' T' F id $ $M[F,\ \text{id}]=F\rightarrow\text{id}$
14 $ E' T' id id $ 匹配 id
15 $ E' T' $ $M[T’,\ $]=T’\rightarrow\varepsilon$
16 $ E' $ $M[E’,\ $]=E’\rightarrow\varepsilon$
17 $ $ 接受

C 语言实现

#include <stdio.h>
#include <string.h>

#define MAX_STACK 100

char stack[MAX_STACK];
int top = -1;

void push(char c) {
    if (top < MAX_STACK - 1) {
        stack[++top] = c;
    }
}

char pop() {
    if (top >= 0) {
        return stack[top--];
    }
    return '\0';
}

char peek() {
    if (top >= 0) {
        return stack[top];
    }
    return '\0';
}

// 预测分析表（简化版，用字符串表示产生式右部）
// M[非终结符][终结符] = 产生式右部（逆序）
const char* M[5][6] = {
    // E, E', T, T', F 对应索引 0, 1, 2, 3, 4
    // id, +, *, (, ), $ 对应索引 0, 1, 2, 3, 4, 5
    {"TE'", NULL, NULL, "TE'", NULL, NULL},      // E
    {NULL, "+TE'", NULL, NULL, "ε", "ε"},        // E'
    {"FT'", NULL, NULL, "FT'", NULL, NULL},      // T
    {NULL, "ε", "*FT'", NULL, "ε", "ε"},         // T'
    {"id", NULL, NULL, "(E)", NULL, NULL}        // F
};

int non_terminal_index(char c) {
    switch (c) {
        case 'E': return 0;
        case '\'': return 1;  // E'
        case 'T': return 2;
        case '\"': return 3;  // T'
        case 'F': return 4;
        default: return -1;
    }
}

int terminal_index(char c) {
    switch (c) {
        case 'i': return 0;  // id
        case '+': return 1;
        case '*': return 2;
        case '(': return 3;
        case ')': return 4;
        case '$': return 5;
        default: return -1;
    }
}

void parse(const char *input) {
    push('$');
    push('E');
    int ip = 0;

    while (top >= 0) {
        char X = peek();
        char a = input[ip];

        if (X == '$' && a == '$') {
            printf("分析成功！\n");
            return;
        }

        if (X == a) {  // 匹配
            pop();
            ip++;
        } else if (non_terminal_index(X) >= 0) {  // 非终结符
            int ni = non_terminal_index(X);
            int ti = terminal_index(a);
            const char *prod = M[ni][ti];

            if (prod == NULL) {
                printf("错误：语法错误在位置 %d\n", ip);
                return;
            }

            pop();
            if (strcmp(prod, "ε") != 0) {
                // 逆序入栈
                for (int i = strlen(prod) - 1; i >= 0; i--) {
                    push(prod[i]);
                }
            }
        } else {
            printf("错误：字符不匹配\n");
            return;
        }
    }
}

int main() {
    char input[100];
    printf("输入表达式（用 i 表示 id）：\n");
    scanf("%s", input);
    strcat(input, "$");
    parse(input);
    return 0;
}

表驱动分析的优缺点

优点：

  • 通用性强，只需修改预测分析表即可适应不同文法
  • 易于自动生成（如使用 ANTLR、JavaCC 等工具）
  • 便于理解 LL(1) 分析原理

缺点：

  • 预测分析表可能较大（非终结符数 × 终结符数）
  • 不如递归下降分析灵活（难以嵌入复杂的语义动作）

不确定的自顶向下分析思想

不确定的自顶向下分析（Nondeterministic Top-Down Parsing）是指在分析过程中，当有多个产生式可选时，无法唯一确定应该使用哪个，需要尝试所有可能的选择（回溯）。

回溯（Backtracking）

基本思想

当选择某个产生式失败（无法匹配输入）时，撤销之前的选择，尝试另一个产生式。

示例

文法（非 LL(1)）：

$$
S\rightarrow aAd\ |\ aBc
$$

$$
A\rightarrow ab\ |\ a
$$

$$
B\rightarrow ac\ |\ b
$$

输入：aad

分析过程：

  1. $S\Rightarrow aAd$（选择第一个产生式）
  2. $S\Rightarrow aAd\Rightarrow aabd$（选择 $A\rightarrow ab$）
  3. 失败（aad $\neq$ aabd）
  4. 回溯：撤销 $A\rightarrow ab$，尝试 $A\rightarrow a$
  5. $S\Rightarrow aAd\Rightarrow aad$ ✓ 成功

回溯的问题

  • 效率低：可能需要尝试大量的组合（指数级复杂度）
  • 实现复杂：需要保存分析状态以便回溯

适用场景

  • 文法简单，产生式数量少
  • 输入串较短
  • 教学演示

实际编译器：几乎不使用回溯，而是通过文法转换（消除左递归、提取左公因子）将文法改写为 LL(1) 文法。

LL(1) 分析中的出错处理

在语法分析过程中遇到错误时，除了报告错误位置和信息外，还应该尝试恢复，继续分析后续代码，以便一次发现多个错误。

错误检测

在 LL(1) 分析中，错误发生在：

  • 预测分析表为空：$M[A,\ a]$ 为空，无法选择产生式
  • 字符不匹配：栈顶是终结符 $t$，但输入是 $a\neq t$

错误恢复策略

1. 应急恢复（Panic Mode Recovery）

基本思想

跳过输入符号，直到遇到一个同步符号（Synchronizing Token），然后继续分析。

同步符号的选择

对于非终结符 $A$，常用的同步符号集合：

  • FOLLOW(A)：$A$ 后面可能跟的符号
  • FIRST(A)：$A$ 开始的符号
  • 特殊符号：如 ;、}、end 等语句结束符

算法

当 M[A, a] 为空时（错误）：
    1. 报告错误
    2. 从栈中弹出 A
    3. 跳过输入符号，直到遇到 FOLLOW(A) 中的符号
    4. 继续分析

示例

文法：

$$
S\rightarrow\text{begin}\ L\ \text{end}
$$

$$
L\rightarrow S\ L’
$$

$$
L’\rightarrow;\ S\ L’\ |\ \varepsilon
$$

输入：begin S ; S end（假设第二个 $S$ 写错了）

如果在分析 $S$ 时发现错误：

  • 同步符号：$\text{FOLLOW}(S)={;,\ \text{end}}$
  • 跳过输入，直到遇到 ; 或 end
  • 继续分析

优缺点

优点：

  • 实现简单
  • 能够跳过大段错误代码

缺点：

  • 可能跳过太多代码，导致后续错误被掩盖
  • 恢复质量不高

2. 短语层恢复（Phrase-Level Recovery）

基本思想

在检测到错误时，局部修改输入（插入、删除、替换），使分析能够继续。

修改策略

  1. 插入缺失的符号（如缺少 ; 或 )）
  2. 删除多余的符号
  3. 替换错误的符号
  4. 交换相邻的两个符号

示例

输入：if (x > 0 then y = 1;（缺少 )）

检测到错误后：

  • 插入 )
  • 继续分析

实现

在预测分析表中，除了正常的产生式，还可以填入错误处理动作：

栈顶 输入 动作
$A$ $a$ 插入 ) 并继续
$A$ $b$ 删除 $b$ 并继续
… … …

优缺点

优点：

  • 恢复质量较高，能够精确定位错误
  • 可以给出有用的错误提示

缺点：

  • 实现复杂，需要为每种错误设计恢复策略
  • 可能”修复”了正确的代码（误判）

3. 错误产生式（Error Productions）

基本思想

在文法中显式添加常见错误的产生式，使分析器能够识别并报告这些错误。

示例

常见错误：赋值语句用 = 而不是 :=

添加错误产生式：

$$
\text{stmt}\rightarrow\text{id}\ =\ \text{expr}
$$

当识别到这个产生式时：

  • 报告错误：”赋值语句应使用 := 而不是 =“
  • 继续分析（将 = 视为 :=）

优缺点

优点：

  • 能够给出针对性的错误提示
  • 不影响后续分析

缺点：

  • 增加文法复杂度
  • 需要预知常见错误类型

4. 全局修正（Global Correction）

基本思想

寻找对输入的最小修改（插入、删除、替换的符号数最少），使其成为文法的句子。

算法

使用动态规划或图搜索算法，计算输入串到合法句子的最小编辑距离。

优缺点

优点：

  • 理论上最优，修改最少
  • 能够处理复杂的错误组合

缺点：

  • 计算代价极高（指数级或多项式高次）
  • 实际编译器中几乎不使用

错误处理的实践建议

  1. 应急恢复：作为默认策略，简单有效
  2. 短语层恢复：针对常见错误（如缺少 ;、)）设计局部修正
  3. 错误产生式：对于特定的常见错误，提供友好的错误提示
  4. 不使用全局修正：计算代价太高

错误信息的设计

好的错误信息应该包含：

  • 位置：行号、列号
  • 期望：期望看到的符号
  • 实际：实际看到的符号
  • 建议：可能的修复方法

示例：

错误：第 10 行，第 15 列
期望: ';' 或 'end'
实际: 'begin'
建议: 检查是否缺少语句结束符 ';'

总结与实践建议

自顶向下分析的核心知识

  1. 基本概念：

    • 最左推导、语法树构造
    • 确定与不确定分析

  2. 文法转换：

    • 消除左递归
    • 提取左公因子

  3. LL(1) 文法：

    • FIRST 和 FOLLOW 集合的计算
    • LL(1) 条件的判别
    • 预测分析表的构造

  4. 实现方法：

    • 递归下降分析（手工实现）
    • 表驱动分析（工具生成）

  5. 错误处理：

    • 应急恢复
    • 短语层恢复

学习建议

  1. 动手计算：

    • 为给定文法计算 FIRST 和 FOLLOW 集合
    • 判别文法是否为 LL(1)
    • 构造预测分析表

  2. 手工编写分析器：

    • 用递归下降方法为简单语言（如算术表达式）编写分析器
    • 嵌入语义动作（如计算表达式的值）

  3. 使用工具：

    • 学习 ANTLR、JavaCC 等工具生成 LL(k) 分析器
    • 理解工具生成的代码

  4. 理解局限性：

    • LL(1) 文法的表达能力有限
    • 某些语法结构（如悬挂 else）难以处理
    • 了解何时需要使用自底向上分析（LR）

  5. 对比 LL 和 LR：

    • LL：简单，适合手工，表达能力较弱
    • LR：复杂，依赖工具，表达能力更强
    • 实际编译器：前端（词法+简单语法）用 LL，后端（复杂语法）用 LR

本章小结：

自顶向下语法分析是编译原理中的重要方法，特别是 LL(1) 分析是最常用的确定性自顶向下分析技术。通过：

  • 文法转换（消除左递归、提取左公因子）
  • FIRST/FOLLOW 集合计算
  • 预测分析表构造
  • 递归下降或表驱动实现

我们可以为符合 LL(1) 条件的文法构造高效的语法分析器。虽然 LL(1) 有其局限性（表达能力不如 LR），但由于其简单性和直观性，在实际编译器开发中仍然占有重要地位，特别适合手工编写的小型编译器和教学演示。

下一章将学习自底向上语法分析方法（LR 分析），它能够处理更广泛的文法，是现代编译器工具（如 Yacc、Bison）的理论基础。