编译原理期末复习题#

---

一、 选择题（共 10 题）#

1. 语言是（）

• A. 句子的集合
• B. 产生式的集合
• C. 符号串的集合
• D. 句型的集合

2. 编译程序前三个阶段完成的工作是（）

• A. 词法分析、语法分析和代码优化
• B. 代码生成、代码优化和词法分析
• C. 词法分析、语法分析、语义分析和中间代码生成
• D. 词法分析、语法分析和代码优化

3. 在句子中称为句柄的是该句型的最左（）

• A. 非终结符号
• B. 短语
• C. 句子
• D. 直接短语

4. 下推自动机识别的语言是（）

• A. 0型语言
• B. 1型语言
• C. 2型语言
• D. 3型语言

5. 扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位，即（）

• A. 字符
• B. 单词
• C. 句子
• D. 句型

6. 对应Chomsky四种文法的四种语言之间的关系是（）

• A. $L_0 \subset L_1 \subset L_2 \subset L_3$
• B. $L_3 \subset L_2 \subset L_1 \subset L_0$
• C. $L_3 = L_2 = L_1 = L_0$
• D. $L_0 = L_3 \subset L_2 = L_1$

7. 词法分析的任务是（）

• A. 识别单词
• B. 分析句子的含义
• C. 识别句子
• D. 生成目标代码

8. 常用的中间代码形式不包括（）

• A. 三元式
• B. 四元式
• C. 逆波兰式
• D. 语法树

9. 代码优化的目的是（）

• A. 节省时间
• B. 节省空间
• C. 节省时间和空间
• D. 把编译程序进行等价交换

10. 代码生成阶段的主要任务是（）

• A. 把高级语言翻译成汇编语言
• B. 把高级语言翻译成机器语言
• C. 把中间代码变换成具体机器的目标代码
• D. 把汇编语言翻译成机器语言

答案：ACDCBBADCC

---

二、 填空题#

1. 编译程序首先要识别出源程序中每个（单词），然后再分析每个（句子）并翻译其意义。
2. 编译程序常用的语法分析方法有（自顶向下）和（自底向上）两种。
3. 通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的（分析），中间代码生成、代码优化与目标代码的生成则是对源程序的（综合）。
4. 语义分析的基本功能包括：确定类型、类型检查、语义处理和某些静态语义检查。
5. 移进-归约分析的关键是（句柄）。

---

三、 消除左递归和提公共左因子#

题1. 消除左递归#

文法 $G[S]$：

$$S \to SAe \mid Ae$$ $$A \to dAbA \mid dA \mid d$$

答：消除左递归后：

$$S \to AeS'$$ $$S' \to AeS' \mid \varepsilon$$ $$A \to dA'$$ $$A' \to AbA \mid bA \mid \varepsilon$$

题2. 提公共左因子#

文法 $G[S]$：

$$S \to (T) \mid a+S \mid a$$ $$T \to ST'$$ $$T' \to ,ST' \mid \varepsilon$$

答：提取公共左因子：

$$S \to (T) \mid aS'$$ $$S' \to +S \mid \varepsilon$$ $$T \to ST'$$ $$T' \to ,ST' \mid \varepsilon$$

---

四、 LL(1) 文法判断与分析表构造#

题1. LL(1) 文法判断#

文法：

$$S \to aH$$ $$H \to aMd \mid d$$ $$M \to Ab \mid \varepsilon$$ $$A \to aM \mid e$$

答：计算 FIRST 集和 FOLLOW 集：

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

验证 LL(1) 条件：

• $\text{predict}(H \to aMd) \cap \text{predict}(H \to d) = \{a\} \cap \{d\} = \varnothing$
• $\text{predict}(M \to Ab) \cap \text{predict}(M \to \varepsilon) = \{a, e\} \cap \{d, b\} = \varnothing$
• $\text{predict}(A \to aM) \cap \text{predict}(A \to e) = \{a\} \cap \{e\} = \varnothing$

所以该文法是 LL(1) 文法。

题2. LL(1) 文法判断#

文法：

$$S \to aD$$ $$D \to STe \mid \varepsilon$$ $$T \to bH \mid H$$ $$H \to d \mid \varepsilon$$

答：计算 FIRST 集和 FOLLOW 集：

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

验证 LL(1) 条件均满足，所以该文法是 LL(1) 文法。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$

---

五、 NFA 与 DFA#

题1. NFA 构造#

给出与正规式 $R = ((ab)^*|b)^*(a|(ba)^*)$ 等价的 NFA。

（图略，需参考原试卷中的 NFA 状态转换图）

题2. NFA 确定化为 DFA#

用子集法确定化：

$I$	$I_a$	$I_b$	状态
$\{X,1,2\}$	$\{1,2\}$	$\{1,2,3\}$	$X$
$\{1,2\}$	$\{1,2\}$	$\{1,2,3\}$	$1$
$\{1,2,3\}$	$\{1,2,Y\}$	$\{1,2,3\}$	$2$
$\{1,2,Y\}$	$\{1,2\}$	$\{1,2,3\}$	$3$

---

六、 LR 分析#

题1. SLR(1) 文法证明#

文法 $G[E]: E \to aTd \mid \varepsilon$

证明 $G$ 不是 LR(0) 文法而是 SLR(1) 文法。

答：拓广文法 $G'$，增加产生式 $S' \to E$。

在项目集 $I_0$ 中：有移进项目 $E \to \cdot aTd$ 和归约项目 $E \to \cdot$，存在移进-归约冲突，所以 $G$ 不是 LR(0) 文法。

$\text{Follow}(E) = \{\#, b\}$，$\text{Follow}(T) = \{d\}$

在 $I_0$、$I_2$ 中：$\text{Follow}(E) \cap \{a\} = \{\#, b\} \cap \{a\} = \varnothing$

所以 $G'$ 是 SLR(1) 文法。SLR(1) 分析表：

	$a$	$b$	$d$	$\#$	$E$	$T$
0	$S_2$	$r_2$		$r_2$	1
1				$acc$
2	$S_5$	$r_2$		$r_2$	4	3
3			$S_6$
4			$S_7$
5	$S_5$	$r_2$	$r_4$	$r_2$	4	3
6		$r_1$		$r_1$
7				$r_3$

题2. LR 分析过程#

文法 $G[M]$：$M \to VbA$，$V \to d \mid \varepsilon$，$A \to a \mid Aba \mid \varepsilon$。

对串 $dbba\#$ 的分析过程：

步骤	状态栈	文法符号栈	剩余输入	动作
1	0	$\#$	$dbba\#$	移进
2	03	$\#d$	$bba\#$	用$V \to d$ 归约
3	02	$\#V$	$bba\#$	移进
4	024	$\#Vb$	$ba\#$	用$A \to \varepsilon$ 归约
5	0246	$\#VbA$	$ba\#$	移进
6	02467	$\#VbAb$	$a\#$	移进
7	024678	$\#VbAba$	$\#$	用$A \to Aba$ 归约
8	0246	$\#VbA$	$\#$	用$M \to VbA$ 归约
9	01	$\#M$	$\#$	接受

题3. LR 分析过程#

文法：$S \to VdB$，$V \to e \mid \varepsilon$，$B \to a \mid Bda \mid \varepsilon$。

对串 $dada\#$ 的分析过程：

步骤	状态栈	文法符号栈	剩余输入	动作
1	0	$\#$	$dada\#$	用$V \to \varepsilon$ 归约
2	02	$\#V$	$dada\#$	移进
3	024	$\#Vd$	$ada\#$	移进
4	0245	$\#Vda$	$da\#$	用$B \to a$ 归约
5	0246	$\#VdB$	$da\#$	移进
6	02467	$\#VdBd$	$a\#$	移进
7	024678	$\#VdBda$	$\#$	用$B \to Bda$ 归约
8	0246	$\#VdB$	$\#$	用$S \to VdB$ 归约
9	01	$\#S$	$\#$	接受

题4. LR(0) 项目集族与 DFA#

文法 $G(S)$：$S \to aAd \mid aAb$，$A \to \varepsilon$

归约规则：$r_1: S \to aAd$，$r_2: S \to aAb$，$r_3: A \to \varepsilon$

LR 分析表：

状态	$a$	$b$	$d$	$\#$	$A$	$S$
0	$S_2$				1
1				$acc$
2	$S_2$	$r_3$	$r_3$		3
3		$S_5$
4	$r_2$	$r_2$	$r_2$
5			$r_1$	$r_2$

句子 $ab\#$ 的分析过程：

步骤	状态栈	符号栈	输入串	ACTION	GOTO
1	0	$\#$	$ab\#$	$S_2$
2	02	$\#a$	$b\#$	$r_3$	3
3	023	$\#aA$	$b\#$	$S_5$
4	0235	$\#aAb$	$\#$	$r_2$	1
5	01	$\#S$	$\#$	$acc$

---

七、 语法制导翻译#

题1. 翻译方案#

已知文法 $G(S)$ 及翻译方案：

$$S \to aAb \quad \{\text{print "1"}\}$$ $$S \to a \quad \{\text{print "2"}\}$$ $$A \to AS \quad \{\text{print "3"}\}$$ $$A \to c \quad \{\text{print "4"}\}$$

输入 $acab$，输出是什么？

答：输出为 4321

---

八、 短语与句柄#

题1. 短语、句柄、最左素短语#

文法 $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$

题2. 短语、句柄、最左素短语#

文法 $G[S]: S \to SdT \mid T$，$T \to T<G \mid G$，$G \to (S) \mid a$

句型 $(SdG)<a$ 的分析：

• 短语：$(SdG)<a$，$(SdG)$，$SdG$，$G$，$a$
• 简单(直接)短语：$G$，$a$
• 句柄：$G$
• 最左素短语：$SdG$

---

九、 逆波兰式与三元式#

题1. 逆波兰式和三元式#

表达式 $(a+b*c)/(a+b)-d$ 的逆波兰表示：$abc*+ab+/d-$

三元式序列：

1. $(*, b, c)$
2. $(+, a, ①)$
3. $(+, a, b)$
4. $(/, ②, ③)$
5. $(-, ④, d)$

题2. 逆波兰式#

表达式 $a + b*(c-d)/e$ 的逆波兰式：$abcd-*e/+$

---

十、 其他填空题#

1. 语法分析是依据语言的语法规则进行的，中间代码产生是依据语言的语义规则进行的。
2. 语法分析器的输入是单词符号串，其输出是语法单位。
3. 一个名字的属性包括类型、作用域。
4. 产生式是用于定义语法范畴的一种书写规则。
5. 逆波兰式 $ab+c+d*e-$ 所表达的表达式为 $(a+b+c)*d-e$
6. 语法分析最常用的两类方法是自上而下和自下而上。
7. 词法分析基于正规文法进行，语法分析基于上下文无关文法。
8. 语法分析的有效工具是语法树。
9. Chomsky 分类法，文法按照规则定义的形式分类。
10. 一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有递归定义的规则。
11. 文法是递归的，产生的语言的句子是无穷多个。
12. 对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。
13. 程序语言的语句可分为执行性语句和说明性语句。
14. 递归下降法不允许任一非终极符是直接左递归的。
15. 采用自上而下分析，必须消除回溯。
16. 自上而下分析法的动作包括：移进、归约、错误处理、接受。
17. 自顶向下从开始符号开始，向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。
18. 自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上直接归约，力求归约到文法的开始符号。
19. 在自底向上的语法分析方法中，关键是选择候选式。
20. 常用的参数传递方式有传地址、传值和传名。
21. 语法分析器则可以发现源程序中的语法错误。
22. 在使用高级语言编程时，首先可通过编译程序发现源程序的全部语法错误和语义部分错误。
23. 执行用高级语言编写的程序主要有解释和编译两种方式。
24. 若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。
25. 编译与解释的根本区别是是否生成目标代码。
26. 解释程序的特点是执行程序时不产生目标代码。
27. 编译程序是对高级语言的翻译。
28. 编译程序输入源程序，输出目标程序。
29. 构造编译程序应掌握源程序、目标语言、编译方法。
30. 在语法分析处理中，FIRST、FOLLOW 集合、SELECT 集合均是终结符集。
31. 词法分析器的输出结果是单词的种别编码和自身值。
32. M1 和 M2 等价是指M1 和 M2 所识别的语言集相等。
33. 文法 $G: S \to xSx \mid y$ 所识别的语言是 $x^nyx^n (n \geq 0)$。
34. 如果文法 G 是无二义的，则它的任何句子 $\alpha$ 的最左推导和最右推导对应的语法树必定相同。
35. 解释程序处理语言时，大多数采用的是先将源程序转化为中间代码，再解释执行。
36. 编译过程中，语法分析器的任务就是分析单词串是如何构成语句和说明的。
37. 编译程序是一种翻译程序。