《编译原理》期末考试试卷#

一、 单项选择题（本题共 10 小题，每小题 2 分，共 20 分）#

1. 编译程序绝大多数时间花在 ( ) 上。 A. 出错处理 B. 词法分析 C. 目标代码生成 D. 表格管理

2. 解释程序和编译程序的根本区别在于 ( )。 A. 是否生成中间代码 B. 加工的对象不同 C. 是否生成目标代码 D. 使用的实现技术不同

3. 乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型，其中3型文法是 ( )。 A. 非限制文法 B. 正则文法 C. 上下文有关文法 D. 上下文无关文法

4. 如果文法 $G$ 是无二义的，则它的任何句子 $\alpha$ ( )。 A. 最左推导和最右推导对应的语法树必定相同 B. 最左推导和最右推导对应的语法树可能不同 C. 最左推导和最右推导必定相同 D. 可能存在两个不同的最左推导，但它们对应的语法树相同

5. 词法分析器的输出结果是 ( )。 A. 单词自身值 B. 单词在符号表中的位置 C. 单词的种别编码 D. 单词的种别编码和自身值

6. 非确定有限自动机 (NFA) 与确定有限自动机 (DFA) 的主要区别在于 ( )。 A. NFA 不能识别正则语言，DFA 可以 B. NFA 的状态转换可能不确定（同一状态和输入有多个下一状态） C. NFA 没有接受状态，DFA 有 D. NFA 只能处理短输入串，DFA 可处理任意长度

7. 在高级语言编译程序常用的语法分析方法中，预测分析方法属于 ( )。 A. 自左至右分析法 B. 自上而下分析法 C. 自下而上分析法 D. 自右至左分析法

8. 在规范归约中，用 ( ) 来刻画可归约串。 A. 直接短语 B. 句柄 C. 最左素短语 D. 素短语

9. 在 LR 分析法中，分析栈中存放的状态是识别规范句型 ( ) 的 DFA 状态。 A. 句柄 B. 前缀 C. 活前缀 D. LR(0) 项目

10. LR(1)文法都是 ( )。 A. 无二义性且无左递归 B. 可能有二义性但无左递归 C. 无二义性但可能是左递归 D. 可以既有二义性又有左递归

---

二、 填空题（本题共 5 小题，每小题 2 分，共 10 分）#

1. 编译过程通常可分为 5 个阶段：词法分析、语法分析、语义分析与中间代码产生、代码优化和目标代码生成。
2. 词法分析基于**正则（或3型）文法进行，语法分析基于上下文无关（或2型）**文法进行。
3. 语法分析最常用的两类方法是自上而下和自下而上分析法。
4. 规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指最左素短语。
5. 一个上下文无关文法 $G$ 包括四个部分：终结符号、非终结符号、开始符号和一组产生式。

---

三、 求解题（本题共 3 小题，每小题 10 分，共 30 分）#

1. （词法分析）构造一个最小的DFA $M$，使其接受字母表 $\Sigma=\{0,1\}$ 上所有满足下述条件的串：每个1都有0直接跟在右边。并构造和 $M$ 等价的正规式。

【解答】 正规式： $(0|10)^*$。 DFA状态说明： 由于每个1后面必须直接跟着0，状态转移如下：

• 设初始状态为 A（也是终态）。
• 处于状态 A 时，输入 0，停留在状态 A（合法）。
• 处于状态 A 时，输入 1，进入状态 B（非终态，必须等下一个输入为 0）。
• 处于状态 B 时，输入 0，回到状态 A（合法，1后面跟了0）。
• 处于状态 B 时，输入 1，进入错误状态 C（非法，1后面接了1）。
• （若有错误状态 C，其接收任何输入均在 C，非终态）。

2. （自顶向下分析）已知文法 $G(S)$：$S \to (L) \mid aS \mid a$， $L \to L,S \mid S$。 (1) 消除左递归和回溯；(5分) (2) 计算每个非终结符的 FIRST 和 FOLLOW 集。(5分)

【解答】 (1) 消除左递归和提取公共左因子（消除回溯）： 消除左递归： $S \to (L) \mid aS'$ $S' \to S \mid \varepsilon$ $L \to SL'$ $L' \to ,SL' \mid \varepsilon$ (2) FIRST 和 FOLLOW 集计算：

• $\text{FIRST}(S) = \{ (, a \}$
• $\text{FIRST}(S') = \{ (, a, \varepsilon \}$
• $\text{FIRST}(L) = \{ (, a \}$
• $\text{FIRST}(L') = \{ ,, \varepsilon \}$
• $\text{FOLLOW}(S) = \{ \#, ,, ) \}$
• $\text{FOLLOW}(S') = \{ \#, ,, ) \}$
• $\text{FOLLOW}(L) = \{ ) \}$
• $\text{FOLLOW}(L') = \{ ) \}$

3. （自底向上分析）已知文法 $G[E]：E \to E+T \mid T$，$T \to T*F \mid F$，$F \to (E) \mid i$。 写出句型 $(E+F)*i$ 的所有短语、简单（直接）短语、句柄和最左素短语。

【解答】

• 短语：$(E+F)*i$ ， $(E+F)$ ， $E+F$ ， $F$ ， $i$。
• 简单(直接)短语：$F$ ， $i$。
• 句柄：$F$。
• 最左素短语：$E+F$。

---

四、 综合题（本题共 4 小题，每小题 10 分，共 40 分）#

1. （文法二义性证明）已知文法 $G(S)：S \to aSbS \mid bSaS \mid \varepsilon$。试证明 $G(S)$ 是二义文法。并给出句子 $abab$ 的两种不同的最左推导过程。

【解答】 证明： 该文法产生的语言是 $a$ 的个数和 $b$ 的个数相等的串的集合。一个文法如果存在某个句子有两棵不同的语法树（或者有两个不同的最左推导），则它是二义性的。 对于句子 $abab$，存在如下两种完全不同的最左推导：

• 推导1：$S \Rightarrow aSbS \Rightarrow abS \Rightarrow abaSbS \Rightarrow ababS \Rightarrow abab$。
• 推导2：$S \Rightarrow aSbS \Rightarrow abSaSbS \Rightarrow abaSbS \Rightarrow ababS \Rightarrow abab$。 由此可见，句子 $abab$ 存在两个不同的最左推导，故 $G(S)$ 是二义文法。

2. （LL(1)语法分析）判断下面文法是否为 LL(1) 文法，若是，请构造相应的 LL(1) 分析表。 $S \to aD$ $D \to STe \mid \varepsilon$ $T \to bH \mid H$ $H \to d \mid \varepsilon$

【解答】 (1) 计算各非终结符的 FIRST 集和 FOLLOW 集：

• $\text{FIRST}(S) = \{a\}$， $\text{FOLLOW}(S) = \{\#, b, d, e\}$
• $\text{FIRST}(D) = \{a, \varepsilon\}$， $\text{FOLLOW}(D) = \{\#, b, d, e\}$
• $\text{FIRST}(T) = \{b, d, \varepsilon\}$， $\text{FOLLOW}(T) = \{e\}$
• $\text{FIRST}(H) = \{d, \varepsilon\}$， $\text{FOLLOW}(H) = \{e\}$ (2) 判断LL(1)条件： 对于每个有多个候选式的产生式，其 SELECT 集均不相交，例如 $D \to STe$ 的 SELECT 集为 $\{a\}$，与 $D \to \varepsilon$ 的 SELECT 集 $\{\#, b, d, e\}$ 交集为空，故满足条件，是 LL(1) 文法。 (3) 构造 LL(1) 分析表： | 非终结符 | $a$ | $e$ | $b$ | $d$ | $\#$ | | -------- | --------- | ----------------- | ----------------- | ----------------- | ----------------- | | $S$ | $\to aD$ | | | | | | $D$ | $\to STe$ | $\to \varepsilon$ | $\to \varepsilon$ | $\to \varepsilon$ | $\to \varepsilon$ | | $T$ | | $\to H$ | $\to bH$ | $\to H$ | | | $H$ | | $\to \varepsilon$ | | $\to d$ | |

3. （LR(0)语法分析）对下面的文法 $G$： $S' \to E$ $E \to aA$ $A \to cA \mid d$ (1) 列出该文法的 $LR(0)$ 项目，并构造它的 $LR(0)$ 项目集规范族。 (2) 判定该文法是否是 $LR(0)$ 文法，若是，构造它的 $LR(0)$ 分析表。

【解答】 (1) $LR(0)$ 项目集规范族（DFA状态）如下：

• $I_0$: $S' \to \cdot E$ ； $E \to \cdot aA$
• $I_1 = \text{GO}(I_0, E)$: $S' \to E \cdot$
• $I_2 = \text{GO}(I_0, a)$: $E \to a \cdot A$ ； $A \to \cdot cA$ ； $A \to \cdot d$
• $I_3 = \text{GO}(I_2, A)$: $E \to aA \cdot$
• $I_4 = \text{GO}(I_2, c)$: $A \to c \cdot A$ ； $A \to \cdot cA$ ； $A \to \cdot d$
• $I_5 = \text{GO}(I_2, d)$: $A \to d \cdot$
• $I_6 = \text{GO}(I_4, A)$: $A \to cA \cdot$

(2) 判定与分析表构造： 检查各项目集，每个状态子集内均不包含“移进-归约”或“归约-归约”冲突项目，因此该文法是 $LR(0)$ 文法。 其 $LR(0)$ 分析表如下：

状态	$a$	$c$	$d$	$\#$	$E$	$A$
0	$s_2$				1
1				$acc$
2		$s_4$	$s_5$			3
3	$r_1$	$r_1$	$r_1$	$r_1$
4		$s_4$	$s_5$			6
5	$r_3$	$r_3$	$r_3$	$r_3$
6	$r_2$	$r_2$	$r_2$	$r_2$
(注：设产生式编号为 (1)$E \to aA$, (2)$A \to cA$, (3)$A \to d$)

4. （SLR(1)语法分析）某语言的文法 $G$ 为： $E \to aTd \mid \varepsilon$ ， $T \to Eb \mid a$ 。证明 $G$ 不是 LR(0) 文法而是 SLR(1) 文法。

【解答】 证明过程如下：

1. 拓广文法 $G'$：增加产生式 $(0) \ S' \to E$。设原产生式为 $(1) \ E \to aTd$，$(2) \ E \to \varepsilon$，$(3) \ T \to Eb$，$(4) \ T \to a$。
2. 考察冲突（为何不是 LR(0)）： 在项目集 $I_0$ 的闭包中，包含项目：

• $S' \to \cdot E$
• $E \to \cdot aTd$ （移进项目）
• $E \to \cdot$ （归约项目） 此时，在 $I_0$ 中同时存在移进项目 $E \to \cdot aTd$ 和归约项目 $E \to \cdot$，产生了典型的“移进-归约”冲突，因此 $G$ 不是 LR(0) 文法。

3. 利用 FOLLOW 集合消解冲突（证明是 SLR(1)）： 计算非终结符的 FOLLOW 集：

• $\text{FOLLOW}(E) = \{ \#, b \}$
• $\text{FOLLOW}(T) = \{ d \}$ 在存在冲突的状态 $I_0$ 中，面临的移进符号是 $a$。而进行 $E \to \varepsilon$ 归约的条件是输入符号必须属于 $\text{FOLLOW}(E)$。 因为 $\text{FOLLOW}(E) \cap \{a\} = \{ \#, b \} \cap \{a\} = \emptyset$。 可以看出，移进的后续符号集合与归约的 FOLLOW 集合完全不相交。同理，文法中其余状态产生的冲突均可通过 FOLLOW 集完美区分，不会发生混淆。所以 $G'$ 满足 SLR(1) 条件，是 SLR(1) 文法。