第四章：语法分析 2

• 4.4 集和 集的计算
  • 4.4.1 文法符合 的 集
  • 4.4.2 计算文法符合 的 集
  • 4.4.3 计算串 的 集
  • 4.4.4 计算非终结符 的
  • 4.4.5 表达式文法各个产生式的 集
  • 4.4.6 文法的分析方法
• 4.5 递归的预测分析法
  • 4.5.1 递归的预测分析法定义
  • 4.5.2 示例分析
• 4.6 非递归的预测分析法
  • 4.6.1 下推自动机
  • 4.6.2 表驱动的预测分析法
  • 4.6.3 递归的预测分析法 VS 非递归的预测分析法
  • 4.6.4 预测分析的实现步骤
• 4.7 预测分析中的错误处理
  • 4.7.1 预测分析中的错误检测
  • 4.7.2 预测分析中的错误恢复

4.4 $FIRST$ 集和 $FOLLOW$ 集的计算

4.4.1 文法符合 $X$ 的 $FIRST$ 集

$FIRST(X)$ ：所有可以从 $X$ 推导的所有 串首终结符 构成的集合。

如果 $X \Rightarrow^* \varepsilon$ ，那么 $\varepsilon \in FIRST(X)$ 。

例如：

$$\begin{aligned} G:\; & E \;\rightarrow TE' \\ & E' \rightarrow +TE' \mid \varepsilon \\ & T \;\rightarrow FT' \\ & T' \rightarrow *FT' \mid \varepsilon \\ & F \;\rightarrow (E) \mid \text{id} \end{aligned}$$

推导一下 $FIRST$ 集

$$\begin{aligned} G:\; & E \;\rightarrow TE' & FIRST(E) &= \{(,\,\text{id}\} \\ & E' \rightarrow +TE' \mid \varepsilon & FIRST(E') &= \{+,\,\varepsilon\} \\ & T \;\rightarrow FT' & FIRST(T) &= \{(,\,\text{id}\} \\ & T' \rightarrow *FT' \mid \varepsilon & FIRST(T') &= \{*,\,\varepsilon\} \\ & F \;\rightarrow (E) \mid \text{id} & FIRST(F) &= \{(,\,\text{id}\} \end{aligned}$$

4.4.2 计算文法符合 $X$ 的 $FIRST$ 集

【算法】

---

不断应用下列规则，直到没有新的终结符或 $\varepsilon$ 可以被加入到任何 $FIRST$ 集合中为止。

• 如果 $X$ 是一个终结符，那么 $FIRST(X) = \{X\}$
• 如果 $X$ 是一个非终结符
  • 如果 $X \rightarrow Y_i\cdots Y_k \in P\,(k \ge 1)$ ，那么如果对于某个 $i$ ， $a$ 在 $FIRST(Y_i)$ 中且 $\varepsilon$ 在所有的 $FIRST(Y_1),\,\cdots,\,FIRST(Y_{i-1})$ 中（即 $Y_1\cdots Y_{i-1} \Rightarrow^* \varepsilon$ ），就把 $a$ 加入到 $FIRST(X)$ 中
  • 如果对于所有的 $j=1,\,2,\,\cdots,\,k$ ， $\varepsilon$ 在 $FIRST(Y_j)$ 中，那么将 $\varepsilon$ 加入到 $FIRST(X)$
• 如果 $X \rightarrow \varepsilon \in P$ ，那么将 $\varepsilon$ 加入到 $FIRST(X)$ 中

---

4.4.3 计算串 $X_1X_2\cdots X_n$ 的 $FIRST$ 集

• 向 $FIRST(X_1X_2\cdots X_n)$ 加入 $FIRST(X_1)$ 中所有的非 $\varepsilon$ 符号
• 如果 $\varepsilon$ 在 $FIRST(X_1)$ 中，再加入 $FIRST(X_2)$ 中所有非 $\varepsilon$ 符号
• 如果 $\varepsilon$ 在 $FIRST(X_1)$ 和 $FIRST(X_2)$ 中，再加入 $FIRST(X_3)$ 中的所有非 $\varepsilon$ 符号，以此类推
• 如果所有的 $i$ ， $\varepsilon$ 都在 $FIRST(X_i)$ 中，那么将 $\varepsilon$ 加入到 $FIRST(X_1X_2\cdots X_n)$ 中

4.4.4 计算非终结符 $A$ 的 $FOLLOW(A)$

$FOLLOW(A)$ 可能在某个句型中紧跟在 $A$ 后边的终结符 $a$ 的集合。

$$FOLLOW(A) = \{ a \mid S \Rightarrow^* \alpha a \beta,\,a\in V_T,\,\alpha,\,\beta \in (V_T \cup V_N)^* \}$$

如果 $A$ 是某个句型的最右符号，则将结束符 $\$$ 添加到 $FOLLOW(A)$ 中。

例如：

$$\begin{aligned} G:\; & E \;\rightarrow TE' & FIRST(E) = \{(,\,\text{id}\} & FOLLOW(E) = \{\$,\,)\} \\ & E' \rightarrow +TE' \mid \varepsilon & FIRST(E') = \{+,\,\varepsilon\} & FOLLOW(E') = \{\$,\,)\} \\ & T \;\rightarrow FT' & FIRST(T) = \{(,\,\text{id}\} & FOLLOW(T) = \{+,\,\$,\,)\} \\ & T' \rightarrow *FT' \mid \varepsilon & FIRST(T') = \{*,\,\varepsilon\} & FOLLOW(T') = \{+,\,\$,\,)\} \\ & F \;\rightarrow (E) \mid \text{id} & FIRST(F) = \{(,\,\text{id}\} & FOLLOW(F) = \{*,\,+,\,\$,\,)\} \end{aligned}$$

【算法】

---

不断应用下列规则，直到没有新的终结符可以被加入到任何 $FOLLOW$ 集合中为止

• 将 $\$$ 放入 $FOLLOW(S)$ 中，其中 $S$ 是开始符号， $\$$ 是输入右端的结束标记
• 如果存在一个产生式 $A \rightarrow \alpha B \beta$ ，那么 $FIRST(\beta)$ 中除 $\varepsilon$ 之外的所有符号都在 $FOLLOW(B)$ 中
• 如果存在一个产生式 $A \rightarrow \alpha B$ ，或存在产生式 $A \rightarrow \alpha B \beta$ 且 $FIRST(\beta)$ 包含 $\varepsilon$ ，那么 $FOLLOW(A)$ 中的所有符号都在 $FOLLOW(B)$ 中

---

4.4.5 表达式文法各个产生式的 $SELECT$ 集

$X$	$FIRST(X)$	$FOLLOW(X)$
$E$	$(,\,\text{id}$	$\$,\,)$
$E'$	$+,\,\varepsilon$	$\$,\,)$
$T$	$(,\,\text{id}$	$+,\,),\,\$$
$T'$	$*,\,\varepsilon$	$+,\,),\,\$$
$F$	$(,\,\text{id}$	$*,\,+,\,),\,\$$

产生式	$SELECT$ 集
$E \rightarrow TE'$	$SELECT(1) = \{ (,\,\text{id} \}$
$E' \rightarrow +TE'$	$SELECT(2) = \{ + \}$
$E' \rightarrow \varepsilon$	$SELECT(3) = \{ \$,\,) \}$
$T \rightarrow FT'$	$SELECT(4) = \{ (,\,\$ \}$
$T' \rightarrow *FT'$	$SELECT(5) = \{ * \}$
$T' \rightarrow \varepsilon$	$SELECT(6) = \{ +,\,),\,\$ \}$
$F \rightarrow (E)$	$SELECT(7) = \{ ( \}$
$F \rightarrow \text{id}$	$SELECT(8) = \{ \text{id} \}$

这是一个 $LL(1)$ 文法，可以根据产生式的 $SELECT$ 集构造预测分析表。

将每个非终结符作为行，每个输入符号作为列，那么每个产生式就是其元素。

预测分析表如下：

非终结符 / 输入符号	$\text{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)$

4.4.6 $LL(1)$ 文法的分析方法

• 递归的预测分析法
• 非递归的预测分析法

4.5 递归的预测分析法

4.5.1 递归的预测分析法定义

递归的预测分析法 是指在递归下降分析中，编写每一个非终结符对应的过程时，根据预测分析表进行产生式选择。

4.5.2 示例分析

$$\begin{aligned} 1.\;& \text{<PROGRAM>} &&\rightarrow \text{program <DECLIST>:<TYPE>:<STLIST> end} \\ 2.\;& \text{<DECLIST>} &&\rightarrow \text{id <DECLISTN>} \\ 3.\;& \text{<DECLISTN>} &&\rightarrow \text{,\,id <DECLISTN>} \\ 4.\;& \text{<DECLISTN>} &&\rightarrow \varepsilon \\ 5.\;& \text{<STLIST>} &&\rightarrow \text{s <STLISTN>} \\ 6.\;& \text{<STLISTN>} &&\rightarrow \text{; s <STLISTN>} \\ 7.\;& \text{<STLISTN>} &&\rightarrow \varepsilon \\ 8.\;& \text{<TYPE>} &&\rightarrow \text{real} \\ 9.\;& \text{<TYPE>} &&\rightarrow \text{int} \end{aligned}$$

$$\begin{aligned} SELECT(4) &= \{ : \} \\ SELECT(7) &= \{\text{end}\} \end{aligned}$$

各个分析过程的伪代码如下：

program DESCENT;
begin
    GETNEXT(TOKEN);
    PROGRAM(TOKEN);
    GETNEXT(TOKEN);
    if TOKEN != '$' then ERROR;
end

procedure PROGRAM(TOKEN);
begin
    if TOKEN != 'program' then ERROR;
    GETNEXT(TOKEN);
    DECLIST(TOKEN);

    if TOKEN != ':' then ERROR;

    GETNEXT(TOKEN);
    TYPE(TOKEN);

    GETNEXT(TOKEN);
    if TOKEN != ';' then ERROR;

    GETNEXT(TOKEN);
    STLIST(TOKEN);

    if TOKEN != 'end' then ERROR;
end

procedure DECLIST(TOKEN);
begin
    if TOKEN != 'id' then ERROR;
    GETNEXT(TOKEN);
    DECLISTN(TOKEN);
end

procedure DECLISTN(TOKEN);
begin
    if TOKEN = ',' then
        begin
            GETNEXT(TOKEN);
            if TOKEN != 'id' then ERROR;

            GETNEXT(TOKEN);
            DECLISTN(TOKEN);
        end
    else if TOKEN != ':' then ERROR;
end

procedure STLIST(TOKEN);
begin
    if TOKEN != 's' then ERROR;
    GETNEXT(TOKEN);
    STLISTN(TOKEN);
end

procedure STLISTN(TOKEN);
begin
if TOKEN = ';' then
    begin
        GETNEXT(TOKEN);
        if TOKEN != 's' then ERROR;

        GETNEXT(TOKEN);
        STLISTN(TOKEN);
    end
    else if TOKEN != 'end' then ERROR;
end

procedure TYPE(TOKEN);
begin
    if TOKEN != 'real' or TOKEN != 'int'
        then ERROR;
end

4.6 非递归的预测分析法

4.6.1 下推自动机

非递归的预测分析法 不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析。

这是一个 下推自动机（Push Down Automata, PDA），下推自动机比有穷自动机的识别能力更强，因为它的记忆功能更强。

例如：

$$L = \{a^nb^n \mid n \ge 1\}$$

有穷自动机不具备专门的存储器，有穷自动机不会知道语言 $L$ 中 $n$ 的值。有穷自动机无法识别这样的语言。

因为 $n$ 可以趋于无穷，而有穷自动机只有有穷个状态，这就产生了矛盾，故有穷自动机不能识别语言 $L$ 。

例如下面的预测分析表：

非终结符 / 输入符号	$\text{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)$

分析过程：

栈	剩余输入	输出
$E\$\;$	$\text{id}+\text{id}*\text{id}\$\;$
$TE'\$\;$	$\text{id}+\text{id}*\text{id}\$\;$	$E \rightarrow TE'$
$FT'E'\$\;$	$\text{id}+\text{id}*\text{id}\$\;$	$T \rightarrow FT'$
$\text{id}T'E'\$\;$	$\text{id}+\text{id}*\text{id}\$\;$	$F \rightarrow \text{id}$
$T'E'\$\;$	$+\text{id}*\text{id}\$\;$
$E'\$\;$	$+\text{id}*\text{id}\$\;$	$T' \rightarrow \varepsilon$
$+TE'\$\;$	$+\text{id}*\text{id}\$\;$	$E' \rightarrow +TE'$
$TE'\$\;$	$\text{id}*\text{id}\$\;$
$FT'E'\$\;$	$\text{id}*\text{id}\$\;$	$T \rightarrow FT'$
$\text{id}T'E'\$\;$	$\text{id}*\text{id}\$\;$	$F \rightarrow \text{id}$
$T'E'\$\;$	$*\text{id}\$\;$
$*FT'E'\$\;$	$*\text{id}\$\;$	$T' \rightarrow *FT'$
$FT'E'\$\;$	$\text{id}\$\;$
$\text{id}T'E'\$\;$	$\text{id}\$\;$	$F \rightarrow \text{id}$
$T'E'\$\;$	$\$\;$
$E'\$\;$	$\$\;$	$T' \rightarrow \varepsilon$
$\$\;$	$\$\;$	$E' \rightarrow \varepsilon$

4.6.2 表驱动的预测分析法

【输入】一个串 $w$ 和文法 $G$ 的分析表 $M$

【输出】如果 $w$ 在 $L(G)$ 中，输出 $w$ 的最左推导，否则给出错误指示

【算法】最初，语法分析器的格局如下：输入缓冲区中是 $w\$\,$ ， $G$ 的开始符号位于栈顶，其下面是 $\$\,$ 。下面的程序使用预测分析表 $M$ 生成了处理这个输入的预测分析过程

设置 ip 使他指向 w 的第一个符号，其中 ip 是输入指针;
X = 栈顶符号;
while (X != $) { /* 栈非空 */
    if (X == ip 所指向的符号 a)
        弹出栈，ip 向前移动一个位置;
    else if (X 是一个终结符号)
        throw ERROR;
    else if (M[X, a] 是一个报错条目)
        throw ERROR;
    else if (M[X, a] = X -> Y[1]Y[2]...Y[k] ) {
        输出产生式 X -> Y[1]Y[2]...Y[k];
        弹出栈顶符号;
        将 Y[k],Y[k+1]...Y[1] 入栈，其中 Y[1] 位于栈顶;
    }
    X = 栈顶符号;
}

4.6.3 递归的预测分析法 VS 非递归的预测分析法

-	递归的预测分析法	非递归的预测分析法
程序规模	程序规模较大，不需要载入分析表	主程序规模较小，需要载入分析表
直观性	较好	较差
效率	较低	分析时间大约正比于待分析程序的长度
自动生成	较难	较易

4.6.4 预测分析的实现步骤

步骤：

1. 构造文法
2. 改造文法：消除二义性、消除左递归、消除回溯
3. 求每个变量的 $FIRST$ 集和 $FOLLOW$ 集，从而求得每个候选式的 $SELECT$ 集
4. 检查是否为 $LL(1)$ 文法，若是，构造预测分析表
5. 预测分析
   • 对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程
   • 对于非递归的预测分析实现表驱动的预测分析算法

4.7 预测分析中的错误处理

4.7.1 预测分析中的错误检测

两种情况下可以检测到错误：

• 栈顶的终结符和当前输入符号不匹配
• 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

4.7.2 预测分析中的错误恢复

恐慌模式：

• 忽略输入中的一些符号，直到输入中出现由设计者选定的 同步词法单元（Synchronizing Token）集合中的某个词法单元
  • 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
  • 例如可以把 $FOLLOW(A)$ 中的所有终结符放入非终结符 $A$ 的同步记号集合
• 如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符

例如，预测分析表如下：

非终结符 / 输入符号	$\text{id}$	$+$	$*$	$($	$)$	$\$\;$
$E$	$E \rightarrow TE'$			$E \rightarrow TE'$	Synch	Synch
$E'$		$E' \rightarrow +TE'$			$E' \rightarrow \varepsilon$	$E' \rightarrow \varepsilon$
$T$	$T \rightarrow FT'$	Synch		$T \rightarrow FT'$	Synch	Synch
$T'$		$T' \rightarrow \varepsilon$	$T' \rightarrow *FT'$		$T' \rightarrow \varepsilon$	$T' \rightarrow \varepsilon$
$F$	$F \rightarrow \text{id}$	Synch	Synch	$F \rightarrow (E)$	Synch	Synch

Synch 表示根据相应非终结符的 $FOLLOW$ 集得到的同步词法单元。

$X$	$FOLLOW(X)$
$E$	$\$,\,)$
$E'$	$\$,\,)$
$T$	$+,\,),\,\$\;$
$T'$	$+,\,),\,\$\;$
$F$	$*,\,+,\,),\,\$\;$

分析表的使用方法：

• 如果 $M[A,\,a]$ 是空，表示检测到错误，根据恐慌模式，忽略输入符号 $a$
• 如果 $M[A,\,a]$ 是 Synch，则弹出栈顶的非终结符 $A$，试图继续分析后面的语法成分
• 如果栈顶的终结符和输入符号不匹配，则弹出栈顶的终结符

分析过程：

栈	剩余输入	输出
$E\$\;$	$+\text{id}*+\text{id}\$\;$	忽略 $+$
$E\$\;$	$\text{id}*+\text{id} \$\;$
$TE'\$\;$	$\text{id}*+\text{id} \$\;$
$FT'E'\$\;$	$\text{id}*+\text{id} \$\;$
$\text{id}T'E'\$\;$	$\text{id}*+\text{id} \$\;$
$T'E'\$\;$	$*+\text{id} \$\;$
$*FT'E'\$\;$	$*+\text{id} \$\;$
$FT'E'\$\;$	$+\text{id}\$\;$	报错
$T'E'\$\;$	$+\text{id} \$\;$
$E'\$\;$	$+\text{id} \$\;$
$+TE'\$\;$	$+\text{id} \$\;$
$TE'\$\;$	$\text{id} \$\;$
$FT'E'\$\;$	$\text{id} \$\;$
$\text{id}T'E'\$\;$	$\text{id} \$\;$
$T'E'\$\;$	$\$\;$
$E'\$\;$	$\$\;$
$\$\;$	$\$\;$