编译原理复习题及答案#

---

一、选择题（共 48 题）#

1. 编译原理是对( C )。

• A. 机器语言的执行
• B. 汇编语言的翻译
• C. 高级语言的翻译
• D. 高级语言程序的解释执行

2. ( A )是一种典型的解释型语言。

• A. BASIC
• B. C
• C. FORTRAN
• D. PASCAL

3. 把汇编语言程序翻译成机器可执行的目标程序的工作是由( B )完成的。

• A. 编译器
• B. 汇编器
• C. 解释器
• D. 预处理器

4. 用高级语言编写的程序经编译后产生的程序叫( B )

• A. 源程序
• B. 目标程序
• C. 连接程序
• D. 解释程序

5. ( C )不是编译程序的组成部分。

• A. 词法分析程序
• B. 代码生成程序
• C. 设备管理程序
• D. 语法分析程序

6. 通常一个编译程序中，不仅包含语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括( C )。

• A. 模拟执行器
• B. 解释器
• C. 表格处理和出错处理
• D. 符号执行器

7. 编译程序绝大多数时间花在( D )上。

• A. 出错处理
• B. 语法分析
• C. 目标代码生成
• D. 表格管理

8. 源程序是句子的集合，( B )可以较好地反映句子的结构。

• A. 线性表
• B. 树
• C. 完全图
• D. 堆栈

9. 词法分析器的输出结果是( D )。

• A. 单词自身值
• B. 单词在符号表中的位置
• C. 单词的种别编码
• D. 单词的种别编码和自身值

10. 词法分析器不能( D )

• A. 识别出数值常量
• B. 过滤源程序中的注释
• C. 扫描源程序并识别记号
• D. 发现括号不匹配

11. 文法：$G: S \to xSx \mid y$ 所识别的语言是( D )。

• A. $xyx$
• B. $(xyx)^*$
• C. $x^nyx^*$
• D. $x^nyx^n (n \geq 0)$

12. 如果文法 $G$ 是无二义的，则它的任何句子 $\alpha$( A )

• A. 最左推导和最右推导对应的语法树必定相同
• B. 最左推导和最右推导对应的语法树可能不同
• C. 最左推导和最右推导必定相同
• D. 可能存在两个不同的最左推导，但它们对应的语法树相同

13. 若状态 $k$ 有项目"$A \to \alpha \cdot$"，且仅当输入符号 $a \in \text{FOLLOW}(A)$ 时，才用规则"$A \to \alpha$"归约的语法分析方法是( D )。

• A. LALR分析法
• B. LR(0)分析法
• C. LR(1)分析法
• D. SLR(1)分析法

14. 若 $a$ 为终结符，则 $A \to \alpha a \cdot \beta$ 为( B )项目。

• A. 归约
• B. 移进
• C. 接受
• D. 待约

15. 在使用高级语言编程时，首先可通过编译程序发现源程序的全部和部分( A )错误。

• A. 语法
• B. 语义
• C. 语用
• D. 运行

16. 乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型，其中3型文法是( B )。

• A. 非限制文法
• B. 正则文法
• C. 上下文有关文法
• D. 上下文无关文法

17. 一个句型中的( A )称为该句型的句柄。

• A. 最左直接短语
• B. 最右直接短语
• C. 终结符
• D. 非终结符

18. 在自底向上的语法分析方法中，分析的关键是( D )

• A. 寻找句柄
• B. 寻找句型
• C. 消除递归
• D. 选择候选式

19. 在自顶向下的语法分析方法中，分析的关键是( C )

• A. 寻找句柄
• B. 寻找句型
• C. 消除递归
• D. 选择候选式

20. 在LR分析法中，分析栈中存放的状态是识别某一( C )的DFA状态。

• A. 句柄
• B. 前缀
• C. 活前缀
• D. LR(0)项目

21. 一个上下文无关文法 $G$ 包括四个组成部分，它们是一组非终结符号，一组终结符号，一个开始符号，以及一组( B )

• A. 句子
• B. 产生式
• C. 单词
• D. 句型

22. 词法分析器用于识别( C )

• A. 句子
• B. 产生式
• C. 单词
• D. 句型

23. 编译程序是一种( B )

• A. 汇编程序
• B. 翻译程序
• C. 解释程序
• D. 目标程序

24. 按逻辑上划分，编译程序第三步工作是( A )

• A. 语义分析
• B. 词法分析
• C. 语法分析
• D. 代码生成

25. 在语法分析处理中，$\text{FIRST}$ 集合、$\text{FOLLOW}$ 集合均是( B )

• A. 非终结符集
• B. 终结符集
• C. 字母表
• D. 状态集

26. 编译程序中语法分析器接收以( A )为单位的输入。

• A. 单词
• B. 表达式
• C. 产生式
• D. 句子

27. 编译过程中，语法分析器的任务就是( B )

• A. 分析单词是怎样构成的
• B. 分析单词串是如何构成语句和说明的
• C. 分析语句和说明是如何构成程序的
• D. 分析程序的结构

28. 若一个文法是递归的，则它所产生的语言的句子( A )。

• A. 是无穷多个
• B. 是有穷多个
• C. 是可枚举的
• D. 个数是常量

29. 识别上下文无关语言的自动机是( C )

• A. 下推自动机
• B. NFA
• C. DFA
• D. 图灵机

30. 编译原理各阶段工作都涉及( B )

• A. 词法分析
• B. 表格管理
• C. 语法分析
• D. 语义分析

31. 正则表达式 R1 和 R2 等价是指( C )

• A. R1 和 R2 都是定义在一个字母表上的正则表达式
• B. R1 和 R2 中使用的运算符相同
• C. R1 和 R2 代表同一正则集
• D. R1 和 R2 代表不同正则集

32. 已知文法 $G[S]: S \to A1$，$A \to A1 \mid S0 \mid 0$。与 $G$ 等价的正规式是( C )

• A. $0(0|1)^*$
• B. $1^* \mid 0^*1$
• C. $0(1|0)^*1$
• D. $1(10|01)^*0$

33. 与 $(a|b)^*(a|b)$ 等价的正规式是( C )。

• A. $a^* \mid b^*$
• B. $(ab)^*(a|b)$
• C. $(a|b)(a|b)^*$
• D. $(a|b)^*$

34. ( D )文法不是 LL(1)的。

• A. 递归
• B. 右递归
• C. 2型
• D. 含有公共左因子的

35. 给定文法 $A \to bA \mid cc$，则符号串 ①cc ②bc ③bcacc ④bccbcc ⑤bbcc 中，是该文法句子的是( D )

• A. ①
• B. ③④⑤
• C. ②④
• D. ①⑤

36. LR(1)文法都是( C )

• A. 无二义性且无左递归
• B. 可能有二义性但无左递归
• C. 无二义性但可能是左递归
• D. 可以既有二义性又有左递归

37. 文法 $E \to E+E \mid E*E \mid i$ 的句子 $i*i+i*i$ 有( C )棵不同的语法树。

• A. 1
• B. 3
• C. 5
• D. 7

38. 文法 $S \to aaS \mid abc$ 定义的语言是( C )。

• A. $\{a^{2k}bc \mid k>0\}$
• B. $\{a^kbc \mid k>0\}$
• C. $\{a^{2k-1}bc \mid k>0\}$
• D. $\{a^kakbc \mid k>0\}$

39. 若 B 为非终结符，则 $A \to \alpha \cdot B\beta$ 为( D )。

• A. 移进项目
• B. 归约项目
• C. 接受项目
• D. 待约项目

40. 同心集合并可能会产生新的( D )冲突。

• A. 二义
• B. 移进/移进
• C. 移进/归约
• D. 归约/归约

41. 就文法的描述能力来说，有( C )

• A. $SLR(1) \subset LR(0)$
• B. $LR(1) \subset LR(0)$
• C. $SLR(1) \subset LR(1)$
• D. 无二义文法 $\subset LR(1)$

42. 有限状态自动机能识别( C )

• A. 上下文无关语言
• B. 上下文有关语言
• C. 正规语言
• D. 0型文法定义的语言

43. 已知文法 G 是无二义的，则对 G 的任意句型 $\alpha$( A )

• A. 最左推导和最右推导对应的语法树必定相同
• B. 最左推导和最右推导对应的语法树可能相同
• C. 最左推导和最右推导必定相同
• D. 可能存在两个不同的最左推导，但他们对应的语法树相同

44. ( B )不是 DFA 的成分

• A. 有穷字母表
• B. 多个初始状态的集合
• C. 多个终态的集合
• D. 转换函数

45. 与逆波兰式 $ab+c*d$ 对应的中缀表达式是( B )

• A. $a+b+c*d$
• B. $(a+b)*c+d$
• C. $(a+b)*(c+d)$
• D. $a+b*c+d$

46. 后缀式 $abc-+-d+$ 可用表达式( B )来表示。

• A. $(-(a+b)-c)+d$
• B. $-(a+(b-c))+d$
• C. $-(a-(b+c))+d$
• D. $(a-(-b+c))+d$

47. 表达式 $A*(B-C*(C/D))$ 的后缀式为( B )。

• A. $ABC-CD/**$
• B. $ABCCD/*-**$
• C. $ABC-*CD/*$
• D. 以上都不对

48. ( D )不是 NFA 的成分。

• A. 有穷字母表
• B. 初始状态集合
• C. 终止状态集合
• D. 有限状态集合

---

二、分析综合题#

题1. 消除左递归和左公共因子#

将文法 $G[S]$ 改写为等价的 $G'[S]$，使 $G'[S]$ 不含左递归和左公共因子。

$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 AB \mid \varepsilon$ $B \to bA \mid \varepsilon$

题2. 消除左递归和左公共因子#

$G[S]$: $S \to [A$ $A \to B] \mid AS$ $B \to aB \mid a$

答： $S \to [A$ $A \to B]A'$ $A' \to SA' \mid \varepsilon$ $B \to aB'$ $B' \to B \mid \varepsilon$

题3. 判断 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) 文法。LL(1) 分析表：

	$a$	$d$	$b$	$e$	$\#$
$S$	$\to aH$
$H$	$\to aMd$	$\to d$
$M$	$\to Ab$	$\to \varepsilon$	$\to \varepsilon$	$\to Ab$
$A$	$\to aM$			$\to e$

题4. 判断 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$

题5. NFA 构造#

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

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

题6. NFA 确定化为 DFA#

将 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$

题7. 证明 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) 文法。

产生式排序：(0) $S' \to E$ (1) $E \to aTd$ (2) $E \to \varepsilon$

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

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

在 $I_5$ 中：$\text{Follow}(E) \cap \{a\} = \varnothing$，$\text{Follow}(T) \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$

题8. LR 分析过程#

文法 $G[M]$ 及其 LR 分析表如下，给出对串 $dbba\#$ 的分析过程。

$G[M]$:

1. $M \to VbA$
2. $V \to d$
3. $V \to \varepsilon$
4. $A \to a$
5. $A \to Aba$
6. $A \to \varepsilon$

LR 分析表：

	$b$	$d$	$a$	$\#$	$M$	$A$	$V$
0	$r_3$	$S_3$			1		2
1				$acc$
2	$S_4$
3	$r_2$
4	$r_6$		$S_5$	$r_6$		6
5	$r_4$			$r_4$
6	$S_7$			$r_1$

分析过程：

步骤	状态栈	文法符号栈	剩余输入	动作
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$	$\#$	接受

题9. LR 分析过程#

文法 $G[M]$：$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$	$\#$	接受

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

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

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

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

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

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

逆波兰表示：$abc*+ab+/d-$

三元式序列：

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