编译原理期末考试试卷#

满分：100分

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

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

2. 用高级语言编写的程序经编译后产生的程序叫 ______。 A. 解释程序 B. 目标程序 C. 源程序 D. 连接程序

3. 词法分析的任务是（ ）。 A. 识别单词 B. 分析句子的含义 C. 识别句子 D. 生成目标代码

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

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

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

7. 以下不属于中间代码形式的是 ______。 A. 后缀式 B. DFA C. 三地址代码 D. 抽象语法树

8. 代码优化的目的是（ ）。 A. 节省时间 B. 节省空间 C. 节省时间和空间 D. 把编译程序进行等价交换

9. LR分析器的核心部分是一张分析表，该表由（ ）组成。 A. ACTION表 B. GOTO表 C. 预测分析表 D. ACTION表和GOTO表

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

---

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

1. 编译过程通常可分为5个阶段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、______ 和 ______。 2. 解释程序和编译程序的区别在于 。 3. 语法分析最常用的两类方法是 ______ 和 ______ 分析法。 4. 属性通常分为两类： 和 ______。 5. 规范归约中的可归约串是 ______，算符优先分析中的可归约串是 ______。

---

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

1. 消除左递归和提取公共左因子。 将文法 $G[S]$ 改写为等价的 $G'[S]$，使 $G'[S]$ 不含左递归和左公共因子： $S \to SAe \mid Ae$ $A \to dAbA \mid dA \mid d$

2. 写出表达式的逆波兰表示及三元式序列。 表达式：$(a+b*c)/(a+b)-d$

3. 求短语、直接短语、句柄和最左素短语。 对于文法 $G[E]$： $E \to E+T \mid T$ $T \to T*F \mid F$ $F \to (E) \mid i$ 写出句型 $(E+F)*i$ 的所有短语、直接（简单）短语、句柄和最左素短语。

---

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

1. 判断 LL(1) 文法并构造分析表。 已知文法： $S \to aD$ $D \to STe \mid \varepsilon$ $T \to bH \mid H$ $H \to d \mid \varepsilon$ 请计算各非终结符的 FIRST 集和 FOLLOW 集，判断其是否为 LL(1) 文法，并构造相应的 LL(1) 预测分析表。

2. 证明 SLR(1) 文法并构造分析表。 某语言的拓广文法 $G'$ 为： (0) $S' \to S$ (1) $S \to Db \mid B$ (2) $D \to d \mid \varepsilon$ (3) $B \to Ba \mid \varepsilon$ 证明 $G$ 不是 LR(0) 文法而是 SLR(1) 文法，并给出 SLR(1) 分析表。

3. 中间代码生成。 将下面的控制语句翻译成四元式序列（假设语句标号从 100 开始）： while (a < b) if (c > d) x = y + z

4. 语法制导翻译。 有定义二进制整数的文法如下： $L \to LB \mid B$ $B \to 0 \mid 1$ 请构造一个翻译模式，计算该二进制数的值（即将其转换为十进制的值）。

---

---

参考答案及解析#

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

1. D。编译程序绝大多数时间花在表格管理上。
2. B。用高级语言编写的程序经编译后产生的程序叫目标程序。
3. A。词法分析的任务是识别单词。
4. A。如果文法 $G$ 是无二义的，则它的任何句子最左推导和最右推导对应的语法树必定相同。
5. B。在规范归约中，用句柄来刻画可归约串。
6. B。乔姆斯基把文法分为四种类型，其中3型文法是正则文法。
7. B。DFA属于词法分析的识别工具，不属于中间代码形式（中间代码包含后缀式、三地址代码、语法树等）。
8. C。代码优化的目的是节省时间和空间，生成更高效的目标代码。
9. D。LR分析器的核心部分是一张分析表，该表由ACTION表和GOTO表（即动作表和状态转换表）组成。
10. D。词法分析器的输出结果是单词的种别编码和自身值（属性值）。

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

1. 优化阶段、目标代码生成阶段
2. 是否生成目标代码（或程序）
3. 自上而下、自下而上
4. 综合属性、继承属性
5. 句柄、最左素短语

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

1. 解： 文法 $G[S]$ 改写为等价的不含左递归和左公共因子的 $G'[S]$ 如下： $S \to AeS'$ $S' \to AeS' \mid \varepsilon$ $A \to dA'$ $A' \to AB \mid \varepsilon$ $B \to bA \mid \varepsilon$

2. 解： （1）逆波兰表示：$abc*+ab+/d-$ （2）三元式序列： ① $(*, b, c)$ ② $(+, a, ①)$ ③ $(+, a, b)$ ④ $(/, ②, ③)$ ⑤ $(-, ④, d)$

3. 解： 通过对句型 $(E+F)*i$ 画出语法树进行分析可知：

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

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

1. 解： 首先计算文法的 FIRST 集和 FOLLOW 集如下表：

非终结符	FIRST 集	FOLLOW 集
$S$	$\{a\}$	$\{\#, b, d, e\}$
$D$	$\{a, \varepsilon\}$	$\{\#, b, d, e\}$
$T$	$\{b, d, \varepsilon\}$	$\{e\}$
$H$	$\{d, \varepsilon\}$	$\{e\}$

由于： $\text{predict}(D \to STe) \cap \text{predict}(D \to \varepsilon) = \{a\} \cap \{\#, b, d, e\} = \emptyset$ $\text{predict}(T \to bH) \cap \text{predict}(T \to H) = \{b\} \cap \{e\} = \emptyset$ $\text{predict}(H \to d) \cap \text{predict}(H \to \varepsilon) = \{d\} \cap \{e\} = \emptyset$ 验证 LL(1) 条件均满足，所以该文法是 LL(1) 文法。 构造的 LL(1) 分析表如下表：

	$a$	$b$	$d$	$e$	$\#$
$S$	$\to aD$
$D$	$\to STe$	$\to \varepsilon$	$\to \varepsilon$	$\to \varepsilon$	$\to \varepsilon$
$T$		$\to bH$	$\to H$
$H$			$\to d$	$\to \varepsilon$

2. 解： **证明：**在项目集 $I_0$ 中，存在移进项目 $D \to \cdot d$，以及归约项目 $D \to \cdot$ 和 $B \to \cdot$。由于同一状态中存在移进-归约和归约-归约冲突，所以 $G$ 不是 LR(0) 文法。 由产生式可知： $\text{FOLLOW}(S) = \{\#\}$ $\text{FOLLOW}(D) = \{b\}$ $\text{FOLLOW}(B) = \{a, \#\}$ 在 $I_0$ 状态下面临的冲突可通过 FOLLOW 集解决： $\text{FOLLOW}(D) \cap \{d\} = \{b\} \cap \{d\} = \emptyset$ $\text{FOLLOW}(B) \cap \{d\} = \{a, \#\} \cap \{d\} = \emptyset$ $\text{FOLLOW}(D) \cap \text{FOLLOW}(B) = \{b\} \cap \{a, \#\} = \emptyset$ 在 $I_3$ 状态中： $\text{FOLLOW}(S) \cap \{a\} = \{\#\} \cap \{a\} = \emptyset$ 因为冲突均可以由 FOLLOW 集解决，所以 $G$ 是 SLR(1) 文法。 SLR(1) 分析表如下（假设产生式分别为：(1)$S \to Db$, (2)$S \to B$, (3)$D \to d$, (4)$D \to \varepsilon$, (5)$B \to Ba$, (6)$B \to \varepsilon$）：

状态	$a$	$b$	$d$	$\#$	$S$	$D$	$B$
0	$r_6$	$r_4$	$S_4$	$r_6$	1	2	3
1				acc
2		$S_5$
3	$r_2$		$S_6$
4		$r_3$
5	$r_1$
6	$r_5$			$r_5$

(注：不同产生式标号产生的表项 $r_x$ 具体数字可能略有不同，按等价逻辑给分)

3. 解： 将控制结构翻译成四元式序列如下：

序号	四元式
100	$(j<, a, b, 102)$
101	$(j, \_, \_, 107)$
102	$(j>, c, d, 104)$
103	$(j, \_, \_, 106)$
104	$(+, y, z, t)$
105	$(=, t, \_, x)$
106	$(j, \_, \_, 100)$
107

4. 解： 引入 $L$、$B$ 的综合属性 $val$，可以得到如下语法制导翻译模式：

$S \to L$ $\{ \text{print}(L.val) \}$ $L \to L_1B$ $\{ L.val = L_1.val \times 2 + B.val \}$ $L \to B$ $\{ L.val = B.val \}$ $B \to 0$ $\{ B.val = 0 \}$ $B \to 1$ $\{ B.val = 1 \}$