编译原理——语法分析

复习材料，不建议阅读

语法分析

确定的自顶向下分析思想

确定的自顶向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构造一棵相应的语法树。

1. 正规情况

$$S → pA | qB \\ A → cAd | a \\ B → dB | b$$

文法右部始终由终结符号开始；相同左部时，右部是不同终结符号开始。

就可以直接根据当前输入符号决定产生式。

2. 一般情况

$$S → Ap | Bq \\ A → a | cA \\ B → dB | b$$

右部不全由终结符开始；相同左部时，右部是不同符号开始；没有空产生式。

问题 A：当输入符号是 $c$ 时，从 $S$ 出发选择 $Ap$ 还是 $Bq$ 能推出 $c$ 开头串？

3. 舍空产生式

$$S → aA | d \\ A → bAS | ε$$

有空产生式了。

问题B：如果有一个输入串 $W=abd$，推导过程：$S \Rightarrow aA \Rightarrow abAS \Rightarrow abS \Rightarrow abd$；在 $abAS \Rightarrow abS$ 的时候，$A$ 的产生式右部开始符号集都不包含 $d$ 只有 $ε$ 产生式，就可以认为 $d$ 的匹配实际依赖于 $A$ 后面的符号 $S$。

FIRST 集

FIRST(a) 是符号串 $a$ 可以推导出的所有串的首终结符号集合，称为 $a$ 的开始符号集或首符号集。

$FIRST(a)=\{\alpha |a \overset{*}{\Rightarrow} \alpha \beta,\alpha \in V_T ,\beta \in V^∗ \}$

$a$ 能推导出空的时候，$ε \in FIRST(a)$。

由此解决问题 A，求 $Ap$ 与 $Bq$ 的 $FIRST$ 集（且它们恰好不相交）就可以得出输入符号选择哪个产生式。

FOLLOW 集

$FOLLOW(A)$ 是在所有句型中紧跟在非终结符 $A$ 后面的终结符号集合。# 是输入串的结束符，也称输入串括号。

$FOLLOW(A)=\{a|S \overset{∗}{\Rightarrow} \dots Aa \dots,a \in V_T\}$

$S$ 能推导出 $\dots A$ 的时候，$\# \in FOLLOW(A)$。

结合 $SELECT$ 由此解决问题 B，$A、S$ 不能同时推导出空，替换仍是唯一确定的。

SELECT 集

$SELECT(A \to \alpha)$ 是产生式 $A \to \alpha$ 的选择符号集，表示当遇到这些输入符号时应该选择该产生式进行推导。

• 若 $ε \notin FIRST(\alpha)$，则 $SELECT(A \to \alpha) = FIRST(\alpha)$。
• 若 $ε \in FIRST(\alpha)$，则 $SELECT(A \to \alpha) = (FIRST(\alpha) - \{ε\}) \cup FOLLOW(A)$。

简单来说就是，$FIRST$ 不含空选 $FIRST$，含空就 $FIRST$ 去掉空并 $FOLLOW$。

$LL(1)$ 文法

概念

一个上下文无关文法是 $LL(1)$ 文法的充分必要条件是，对每个非终结符 $A$ 的两个不同产生式 $A \to \alpha$ 和 $A \to \beta$，满足：$SELECT(A \to \alpha) ∩ SELECT(A \to \beta) = ∅$。

其中 $\alpha$ 和 $\beta$ 不同时能推导出 $ε$。

判别

1. 求能推出 ε 的非终结符

建立标志位数组（“未定”/“是”/“否”），扫描产生式：

• 右部含终结符 → 标记"否"
• 右部为 ε → 标记"是"
• 重复扫描直到标志不再变化

2. 计算 FIRST 集

对每个符号 X：

• 若 $X \in V_T$，则 $FIRST(X) = \{X\}$
• 若 $X \in V_N$ 且 $X \to a\alpha$，则 $a \in FIRST(X)$
• 若 $X \in V_N$ 且 $X \to \varepsilon$，则 $\varepsilon \in FIRST(X)$
• 若 $X \in V_N$ 且 $X \to Y_1...Y_n$，则将 $FIRST(Y_i)$（除 $\varepsilon$）加入 $FIRST(X)$

3. 计算 FOLLOW 集

对每个非终结符 A：

• 开始符号 S：$\# \in FOLLOW(S)$
• 产生式 $A \to \alpha B\beta$：$FIRST(\beta)$（非空）加入 $FOLLOW(B)$
• 若 $\varepsilon \in FIRST(\beta)$：$FOLLOW(A)$ 加入 $FOLLOW(B)$

4. 计算 SELECT 集并判别

对每个产生式 $A \to \alpha$：

• 若 $\varepsilon \notin FIRST(\alpha)$，则 $SELECT(A \to \alpha) = FIRST(\alpha)$
• 若 $\varepsilon \in FIRST(\alpha)$，则 $SELECT(A \to \alpha) = (FIRST(\alpha) - \{\varepsilon\}) \cup FOLLOW(A)$

LL(1) 条件：对每个非终结符 A 的不同产生式，SELECT 集的交集为空集。

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

当文法不满足 LL(1) 时，不能用确定的自顶向下分析，但可用不确定的自顶向下分析（带回溯的自顶向下分析）。

引起回溯的原因是：在文法中当关于某个非终结符的产生式有多个候选时，而面临当前的输入符无法确定选用唯一的产生式，从而引起回溯。

回溯分析

1. 由于相同左部的产生式的右部 FIRST 集交集不为空而引起回溯

$$\begin{aligned} S &\to xAy \\ A &\to ab \mid a \end{aligned}$$

输入串 xay，先选 A → ab，xa 匹配后当前符 y 与 b 不匹配，回溯改选 A → a，匹配成功。

2. 由于相同左部非终结符的右部存在 ε 的产生式，且该非终结符的 FOLLOW 集中含有其他产生式右部 FIRST 集的元素

$$\begin{aligned} S &\to aA \mid b \\ A &\to cA \mid \varepsilon \end{aligned}$$

输入串 ab#，先选 S → aA，a 匹配后 A 选 A → cA，但 c 与 b 不匹配，回溯改选 A → ε，b 与 S 的 FOLLOW 集中的 b 匹配，匹配成功。

3. 由于文法含有左递归而引起回溯

$$\begin{aligned} S &\to Sa \mid b \end{aligned}$$

输入串 baa#，先选 S → b，输入串未分析完，回溯改选 S → Sa，再选 S → b，得到 ba，但输入串还有 a#，继续回溯，最终得到 baa，匹配成功。

带回溯分析代价很高，效率很低，在实用编译程序中几乎不用。

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

左递归消除

文法中含有左递归时不能采用确定的自顶向下分析法。左递归分为直接左递归和间接左递归。

直接左递归消除

形如 $A \to A\alpha$ 的产生式称为直接左递归。

例：文法 $G_5$ 含有直接左递归：

$$\begin{aligned} S &\to Sa \\ S &\to b \end{aligned}$$

该文法产生的语言 $L = \{ba^n | n \geq 0\}$。输入串 baaa# 应是该语言的句子，但用自顶向下分析时，当输入符为 b 时，为与 S 匹配则应选用 $S \to b$ 推导，但这样就推不出后边部分；而若用 $S \to Sa$ 推导则无法确定到什么时候才用 $S \to b$ 替换。

消除方法：把直接左递归改写为右递归。对文法 $G_5$ 可改写为：

$$\begin{aligned} S &\to bS' \\ S' &\to aS' | \varepsilon \end{aligned}$$

改写后的文法和原文法产生的语言句子集都为 $\{ba^n | n \geq 0\}$，且改写后的文法为 LL(1) 文法。

一般情况下，假定关于 $A$ 的全部产生式是：

$$A \to A\alpha_1 | A\alpha_2 | \dots | A\alpha_n | \beta_1 | \beta_2 | \dots | \beta_m$$

其中 $\beta_i$（$1 \leq i \leq m$）不以 $A$ 开头，消除直接左递归后改写为：

$$\begin{aligned} A &\to \beta_1 A' | \beta_2 A' | \dots | \beta_m A' \\ A' &\to \alpha_1 A' | \alpha_2 A' | \dots | \alpha_n A' | \varepsilon \end{aligned}$$

间接左递归消除

形如 $A \to B\alpha$，$B \to A\beta$ 等可以形成推导 $A \Rightarrow^+ A$ 的产生式称为间接左递归。

例：文法 $G_6$ 含有间接左递归：

$$\begin{aligned} A &\to aB \\ A &\to Bb \\ B &\to Ac \\ B &\to d \end{aligned}$$

若有输入串为 adbcbcbc#，当分析过程至 $A \Rightarrow aB \Rightarrow aAc \Rightarrow aBbc$ 时，$B$ 若用产生式 $B \to d$ 替换，则分析过程终止，不能推出 adbcbcbc#；而若选用产生式 $B \to Ac$，则会出现无法确定何时终止的情况。

消除方法：先通过产生式非终结符置换，将间接左递归变为直接左递归，然后再按消除直接左递归的方法处理。

以文法 $G_6$ 为例，用产生式 $A \to aB$ 和 $A \to Bb$ 的右部置换产生式 $B \to Ac$ 中的非终结符 $A$，得到左部为 $B$ 的产生式：

$$\begin{aligned} B &\to aBc \\ B &\to Bbc \\ B &\to d \end{aligned}$$

消除左递归后得：

$$\begin{aligned} B &\to aBcB' | dB' \\ B' &\to bcB' | \varepsilon \end{aligned}$$

再把原来其余的产生式 $A \to aB$ 和 $A \to Bb$ 加入，最终文法为：

$$\begin{aligned} A &\to aB \\ A &\to Bb \\ B &\to aBcB' | dB' \\ B' &\to bcB' | \varepsilon \end{aligned}$$

该文法与 $G_6$ 等价，即它们产生相同的句子集。

消除一切左递归的算法

对文法中一切左递归的消除要求文法中不含回路，即无 $A \overset{+}{\Rightarrow} A$ 的推导。满足这个要求的充分条件是，文法中不包含形如 $A \to A$ 的有害规则和 $A$ 的空产生式。

算法步骤如下：

1. 把文法的所有非终结符按某一顺序排序，例如：$A_1, A_2, \dots, A_n$
2. FOR i = 1 TO n DO
   • FOR j = 1 TO i-1 DO
     • 若 $A_i$ 的所有产生式为 $A_i \to \delta_1 | \delta_2 | \dots | \delta_k$
     • 将其替换形如 $A_i \to A_j\gamma$ 的产生式得到 $A_i \to \delta_1' | \delta_2' | \dots | \delta_m'$
   • 消除 $A_i$ 中的一切直接左递归
3. 去掉无用产生式

例：按上述方法消除如下文法的一切左递归：

$$\begin{aligned} S &\to Qc \\ Q &\to Rb | b \\ R &\to Sa | a \end{aligned}$$

若非终结符排序为 $S, Q, R$：

• 左部为 $S$ 的产生式 $S \to Qc$ 无直接左递归
• 左部为 $Q$ 的产生式 $Q \to Rb | b$ 中右部不含 $S$
• 把产生式 $S \to Qc$ 的右部代入产生式 $R \to Sa$ 得：$R \to Qca | a$
• 再将产生式 $Q \to Rb | b$ 的右部代入得：$R \to Rbca | bca | a$
• 对产生式消除直接左递归得：

$$\begin{aligned} R &\to bcaR' | aR' \\ R' &\to bcaR' | \varepsilon \end{aligned}$$

最终文法变为：

$$\begin{aligned} S &\to Qc \\ Q &\to Rb | b \\ R &\to bcaR' | aR' \\ R' &\to bcaR' | \varepsilon \end{aligned}$$

若非终结符的排序为 $R, Q, S$，则把产生式 $R \to Sa | a$ 代入产生式 $Q \to Rb | b$ 得：$Q \to Sab | ab | b$，再将此代入产生式 $S \to Qc$ 得：$S \to Sabc | abc | bc$。消除该产生式的左递归后，文法变为：

$$\begin{aligned} S &\to abcS' | bcS' \\ S' &\to abcS' | \varepsilon \end{aligned}$$

由于 $Q, R$ 为不可到达的非终结符，所以以 $Q, R$ 为左部及包含 $Q, R$ 的产生式应删除。

当非终结符的排序不同时，最后结果的产生式形式不同，但它们是等价的。

提取左公因子

若文法中含有形如 $A \to \alpha\beta_1 | \alpha\beta_2$ 的产生式，会导致相同左部产生式的 FIRST 集相交，不满足 LL(1) 条件。

可将产生式等价变换为：

$$\begin{aligned} A &\to \alpha A' \\ A' &\to \beta_1 | \beta_2 \end{aligned}$$

写成一般形式：$A \to \alpha\beta_1 | \alpha\beta_2 | \dots | \alpha\beta_n | \gamma$（其中 $\gamma$ 不以 $\alpha$ 开头）

提取左公共因子后变为：

$$\begin{aligned} A &\to \alpha A' | \gamma \\ A' &\to \beta_1 | \beta_2 | \dots | \beta_n \end{aligned}$$

若 $\beta_i$ 中仍含有左公共因子，可再次提取，直到无左公共因子为止。

例 1：文法 $G_1$ 的产生式为

$$\begin{aligned} S &\to Sb \\ S &\to Sa \\ S &\to \varepsilon \end{aligned}$$

对产生式(1)、(2)提取左公共因子后得：

$$\begin{aligned} S &\to S(b | a) \\ S &\to \varepsilon \end{aligned}$$

进一步变换为：

$$\begin{aligned} S &\to SA' \\ A' &\to b \\ A' &\to a \\ S &\to \varepsilon \end{aligned}$$

例 2：文法 $G_2$ 的产生式为

$$\begin{aligned} A &\to ad \\ A &\to Bc \\ B &\to aA \\ B &\to b \end{aligned}$$

产生式(2)的右部以非终结符 $B$ 开始，左公共因子可能是隐式的。用产生式(3)、(4)的右部替换产生式(2)中的 $B$，可得：

$$\begin{aligned} A &\to ad \\ A &\to aAc \\ A &\to bc \end{aligned}$$

提取产生式(1)、(2)的左公共因子得：

$$\begin{aligned} A &\to a(d | Ac) \\ A &\to bc \end{aligned}$$

引进新非终结符 $A'$ 后得 $G_2$ 为：

$$\begin{aligned} A &\to aA' \\ A &\to bc \\ A' &\to d \\ A' &\to Ac \end{aligned}$$

注意事项：

1. 提取左公共因子后，可能使某些产生式变成无用产生式，需要对文法重新压缩。

2. 某些文法不能在有限步骤内提取完左公共因子。例如文法 $G_4$：

$$\begin{aligned} S &\to Apl | Ba \\ A &\to aAp | d \\ B &\to aBq | e \end{aligned}$$

用产生式(2)、(3)的右部替换产生式(1)中的 $A$、$B$，再提取左公共因子，只能使文法的产生式越来越多，无限增加下去，而不能得到提取左公共因子的预期结果。

3. 一个文法提取了左公共因子后，只解决了相同左部产生式右部的 FIRST 集不相交的问题。当改写后的文法不含空产生式，且无左递归时，则改写后的文法是 LL(1) 文法；若还有空产生式时，则还需用 LL(1) 文法的判别方式进行判断才能确定是否为 LL(1) 文法。

LL(1) 分析的实现

递归下降分析

核心思想：为每个非终结符编写一个递归函数,函数内根据当前输入符号查 SELECT 集选择产生式,递归调用对应函数。

构造方法：

1. 为每个非终结符 $A$ 编写函数 A()
2. 函数体结构：
   • 根据当前输入符号 lookahead 选择产生式
   • 对产生式右部的每个符号：
     • 终结符：匹配并读入下一符号
     • 非终结符：调用对应函数

示例：文法 $E \to E+T \mid T$，$T \to T*F \mid F$，$F \to (E) \mid \text{id}$

消除左递归后：$E \to TE'$，$E' \to +TE' \mid \varepsilon$，$T \to FT'$，$T' \to *FT' \mid \varepsilon$，$F \to (E) \mid \text{id}$

def E():
    T()
    E_prime()

def E_prime():
    if lookahead == '+':
        match('+')
        T()
        E_prime()
    # else: ε 产生式，什么都不做

def T():
    F()
    T_prime()

def T_prime():
    if lookahead == '*':
        match('*')
        F()
        T_prime()

def F():
    if lookahead == '(':
        match('(')
        E()
        match(')')
    elif lookahead == 'id':
        match('id')
    else:
        error()

def match(expected):
    global lookahead
    if lookahead == expected:
        lookahead = next_token()  # 读入下一符号
    else:
        error()

优点：代码结构清晰,易于理解和调试,可手工编写。

缺点：每个文法需单独编程,修改文法需重写代码。

表驱动分析

核心思想：用一张预测分析表 $M[A, a]$ 存储"非终结符 $A$ 遇到输入符号 $a$ 时选择哪个产生式",用栈模拟推导过程。

分析表构造：对每个产生式 $A \to \alpha$，对 $SELECT(A \to \alpha)$ 中的每个终结符 $a$，令 $M[A, a] = A \to \alpha$。

分析过程：

栈初始化: [#, S]  (# 是栈底, S 是开始符号)
输入指针: 指向输入串首符号

循环:
  X = 栈顶符号
  a = 当前输入符号

  if X == a == #:
      分析成功
  elif X == a:
      弹栈, 输入指针前移
  elif X 是终结符:
      报错 (栈顶终结符与输入不匹配)
  elif M[X, a] 为空:
      报错 (无对应产生式)
  else:  # M[X, a] = X → Y₁Y₂...Yₖ
      弹出 X
      将 Yₖ...Y₂Y₁ 逆序压栈 (若 Yᵢ = ε 则不压栈)

示例：文法 $E \to TE'$，$E' \to +TE' \mid \varepsilon$，$T \to FT'$，$T' \to *FT' \mid \varepsilon$，$F \to (E) \mid \text{id}$

分析表（部分）：

非终结符	id	+	*	(	)	#
E	$E \to TE'$			$E \to TE'$
E’		$E' \to +TE'$			$E' \to \varepsilon$	$E' \to \varepsilon$
T	$T \to FT'$			$T \to FT'$
T’		$T' \to \varepsilon$	$T' \to *FT'$		$T' \to \varepsilon$	$T' \to \varepsilon$
F	$F \to \text{id}$			$F \to (E)$

分析 id+id 的过程：

栈              输入          动作
[#, E]          id+id#       M[E,id]=E→TE', 弹E压E'T
[#, E', T]      id+id#       M[T,id]=T→FT', 弹T压T'F
[#, E', T', F]  id+id#       M[F,id]=F→id, 弹F压id
[#, E', T', id] id+id#       匹配id, 弹栈前移
[#, E', T']     +id#         M[T',+]=T'→ε, 弹T'
[#, E']         +id#         M[E',+]=E'→+TE', 弹E'压E'T+
[#, E', T, +]   +id#         匹配+, 弹栈前移
[#, E', T]      id#          M[T,id]=T→FT', 弹T压T'F
[#, E', T', F]  id#          M[F,id]=F→id, 弹F压id
[#, E', T', id] id#          匹配id, 弹栈前移
[#, E', T']     #            M[T',#]=T'→ε, 弹T'
[#, E']         #            M[E',#]=E'→ε, 弹E'
[#]             #            接受

伪代码实现：

def LL1_parse(input_string, parse_table):
    stack = ['#', start_symbol]
    input_ptr = 0
    input_string += '#'

    while True:
        X = stack[-1]  # 栈顶
        a = input_string[input_ptr]  # 当前输入

        if X == a == '#':
            return "接受"
        elif X == a:
            stack.pop()
            input_ptr += 1
        elif X in terminals:
            return f"错误: 期望 {X}, 得到 {a}"
        elif parse_table[X][a] is None:
            return f"错误: 无产生式 M[{X}, {a}]"
        else:
            production = parse_table[X][a]  # X → Y₁Y₂...Yₖ
            stack.pop()
            if production != 'ε':
                for symbol in reversed(production):
                    stack.append(symbol)

优点：通用性强,修改文法只需重新生成分析表,适合自动化工具生成。

缺点：需要预先构造分析表,不如递归下降直观。

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

错误处理包含两个任务：报错（指出错误位置和类型）和错误恢复（使分析继续进行）。

错误发生的情况

LL(1) 分析中有两种错误情况：

1. 栈顶终结符与当前输入不匹配
2. 栈顶非终结符 $A$ 面临输入符号 $a$，但 $M[A, a]$ 为空

应急恢复 (Panic Mode)

核心思想：跳过输入符号直到遇到"同步符号"，使分析能继续。

同步符号选择：将 $FIRST(A)$ 或 $FOLLOW(A)$ 中的符号作为非终结符 $A$ 的同步符号。

恢复策略：

• 遇到 $FOLLOW(A)$ 中的符号：弹出栈顶的 $A$，继续分析
• 遇到 $FIRST(A)$ 中的符号：保留 $A$ 在栈顶，根据 $A$ 恢复分析

示例：若 $E$ 在栈顶，当前输入是 )，但 $M[E, )]$ 为空：

FOLLOW(E) = {), #}
策略: 跳过输入直到遇到 ) 或 #，弹出 E，继续分析

短语层恢复 (Phrase-Level)

核心思想：根据当前语法单位的上下文进行更精确的恢复。

流程：

1. 进入语法单位时：

   • 检查当前符号是否属于 $BeginSym$（通常取 $FIRST$ 集）
   • 若不属于，报错并跳过 $BeginSym \cup EndSym$ 之外的符号
   • 遇到 $BeginSym$ 中符号：重新分析该单位
   • 遇到 $EndSym$ 中符号：退出该单位

2. 离开语法单位时：

   • 检查当前符号是否属于 $EndSym$（基于 $FOLLOW$ 集）
   • 若不属于，报错并跳过 $BeginSym \cup EndSym$ 之外的符号

递归下降中的实现示例：

文法：$B \to [A] \mid (A)$，$A \to a$

def ParseB(EndSym):
    BeginSym = {'[', '('}  # FIRST(B)

    # 进入时检查
    if sym not in BeginSym:
        error("期望 [ 或 (")
        skip_until(BeginSym | EndSym)

    if sym == '[':
        match('[')
        ParseA(EndSym | {']'})  # 传入上下文相关的 EndSym
        match(']')
    else:
        match('(')
        ParseA(EndSym | {')'})  # 不同上下文使用不同参数
        match(')')

    # 离开时检查
    if sym not in EndSym:
        error("意外的符号")
        skip_until(BeginSym | EndSym)

关键点：不同上下文传入不同的 $EndSym$ 参数，体现"短语层"的含义。例如方括号内调用 ParseA 时传入 EndSym ∪ {]}，圆括号内传入 EndSym ∪ {)}。

两种方法对比

方法	优点	缺点
应急恢复	实现简单，通用	恢复不够精确，可能跳过过多符号
短语层恢复	考虑上下文，恢复更精确	实现复杂，需为每个语法单位设计

实际编译器（如 PL/0）通常采用短语层恢复，在进入和退出语法单位时调用检查函数，根据 $FIRST$ 和 $FOLLOW$ 集合进行错误检测和恢复。