《编译原理》复习第1章~第5章

前言

练习题来自超星《吉林大学编译原理》课程的章节测验和作业，全文仅为自己学习使用，如果有错，欢迎指正。

---

课时安排（课程重点）

2.4-2.7：正则式描述单词和确定有限自动机（DFA）部分
2.8-2.10：NFA、NFA的确定化、DFA的化简部分
2.11节和第3章全部
4.1：文法定义部分，这部分知识点是语法分析的理论基础
4.2～4.4：文法等价变换、语法分析功能和三个集合的求法。其中，文法等价变换只要求掌握消除公共前缀，消除直接左递归，其他的文法等价变换方法了解就可以。三个集合的求法是重点也是难点，是必须掌握的知识点。
4.5：递归下降法部分，这是本章的重点内容。在递归下降法中，要了解递归下降语法分析的思想，掌握递归下降语法分析程序的构造。
4.6～4.7节：LL（1）语法分析方法部分是本章的重点内容，需要了解LL（1）语法分析方法的思想，学会构造LL（1）分析表，掌握LL(1)语法分析程序的构造，针对一个文法，对给定符号串，能给出分析过程。
第5章：不在期末考试的范围内。（ 5.1自底向上语法分析基本思想要仔细看看，其他节简单看就可以。）
6.1-6.3：语义分析方面的内容
6.4-6.11：涉及到函数标识符和域名标识符的属性表示、各种类型的内部表示以及值的内部表示。
6.12-6.17：涉及到的知识点包括标识符的作用域、符号表的局部化和全局符号表。
7.1～7.5：其中7.5 LR(1)语法制导方法只做简单了解即可，四元式必须掌握，要求理解语法制导翻译的基本思想和LL(1)语法制导方法。
7.6-7.9：下标变量
7.10-7.15
8.1-8. 4
8.5-8.8
9.1-9.5
10.1-10.7

第一章：编译引论

一. 概括（思维导图）

所以这一章的内容即为：

• 1.1 程序设计语言发展及其高级语言实现
• 1.2 编译程序的组成

知识点：编译程序，编译过程概述，编译程序的结构，编译程序生成，学习构造编译程序。
重点：编译程序工作的基本过程及其各阶段的基本任务，编译程序框架。
难点：编译程序的结构。

---

二. 练习题

1. 以下关于高级语言实现方式的说法中错误的是( D)。
A. 编译方式与解释方式的根本区别在于是否生成目标代码;
B. 编译方式对源程序的处理是先翻译后执行;
C. 解释方式是按源程序中语句的动态顺序逐句地进行分析解释,并立即执行;
D. 解释方式并不对源程序进行翻译;

答案解析：解释方式也需要对源程序进行翻译,只不过是边翻译边执行,不生成目标程序。

---

2. “用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行。”,这种说
法正确与否?

不正确

实现高级语言的方式有①编译、②解释和③转换，所以用高级语言编写的源程序也可以通过解释方式或转换方式来实现运行。

---

3. 符号串集合A= { a,b,c,d,…,z,A,B,C,D,…,Z },下面对集合Aⁿ说法正确的是:（B）
A. 该集合是英文字母集合
B. 该集合中符号串长度都等于n
C. 该集合是英文串集合
D. 该集合中符号串长度都小于等于n

Aⁿ是英文字母集合A自我n次乘积,可以表示长度为n的英文串集。

---

4. r=(a|b|c)(x|y|z),则L®中元素个数是: 9
r表示的正规集中每个字符串都包含两部分,前部分只能是a、b或c三种之一,后面部分只能是x、y或z三种之一,共有3*3也就是9种变化。

---

5. 与正则表达式 (a*|b)*(c|d) 等价的正则表达式是:

 (a|b)*c| (a|b)*d  
1

---

6. 设正则表达式 r = (a|b)(x|y)*,则下面错误的正规集元素是:(A)
A. abx
B. bxxx
C. a
D. bxyyxxy

答案解析：r表示的正规集中元素都包含两部分,前部分只能是a或b,后面可以由x或y的任意次幂连接,因为是星闭包,也可以不包含x和y。

---

7. 算术表达式123+45.6,在词法分析后,下面的合法单词是:(ACD)
A. 十进制数123
B. 符号串123
C. 运算符+
D. 十进制数45.6

答案解析：算术表达式通过词法分析能分析为3个单词——①常量十进制整数123，②运算符+和③实数45.6。

---

8. 字母表Σ={0,1},下面属于Σ的符号串的是（ABC）
A. 1
B. 000
C. ε
D.空集

基本概念。符号串是由字母表中的符号组成的任意有穷序列。符号串中可以不包含任何符号,这样的字符串称为空串ε。而空集显然不符合定义。

---

9. 设字母表S={0,1}，写正则表达式表示：
1）.所有S上定义的串；
（0|1）*

2）.不带前导0的二进制数；
0| （1（0|1）*）

3）.以非零为前导的能被2整除的二进制数。
0| （1（0|1）*0）

答案解析：
乘法优先级比或运算更高
*表示重复多位，每位是0或1.
不带前导0的非0数第一位是1，后面*运算重复多位，每位是0或1.
在2题基础上，以0结尾的二进制数可以被2整除.

---

10. 【单选题】编译程序必须完成的工作有( ①②③⑥ )。
① 词法分析
② 语法分析
③ 语义分析
④ 中间代码生成
⑤ 中间代码优化
⑥ 目标代码生成
A、①②③④⑤⑥
B、①②③④
C、①②③⑥
D、①②③④⑤

源程序在经过词法分析、语法分析和语义分析之后可以直接转换为目标程序,有中间代码生成的目的是为了方便优化和移植,因此中间代码生成和中间代码优化不是编译过程中必须完成的工作。

---

11. 编译程序各阶段的工作都要涉及( 表格管理 )和( 出错处理 )。

---

---

第二章：形式语言与有限自动机

一. 概括（思维导图）

教学内容：
2.1 词法分析概述
2.2 字符和字符串基本概念
2.3 正则表达式定义
2.4 正则表达式描述单词
2.5 确定有限自动机DFA.
2.6 DFA接受的字符串
2.7 DFA描述单词及DFA的实现
2.8 非确定自动机NFA
2.9 NFA的确定化
2.10 DFA的化简
2.11 正则表达式和有限自动机的相互转化

知识点：正规表达式与有限自动机。
重点：正则表达式与有限自动机。
难点：正则表达式、有限自动机之间的关系。

---

二. 练习题

1. 如果一个正则表达式所代表的集合是无穷的,则该正则表达式必含有的运算是: *

---

2. 不是DFA的构成成分的是（B）:
A、有穷字母表
B、初始状态集合
C、终止状态集合
D、有限状态集合

根据DFA的定义可知,DFA只能有唯一确定的起始状态。

---

3.有限自动机M和N等价是指（D）:
A、M和N的字母表相同
B、M和N状态数相等
C、M和N状态数或有向边数相等
D、M和N识别的字符串集合相同

---

4. 与DFA相比，NFA的非确定性体现在:（AC）
A、允许有多个开始状态
B、允许有多个终止状态
C、在没有任何输入的情况下允许进行状态转换
D、一个状态可以有多个不同后继状态

---

5.下面关于DFA说法正确的是（C）:
A. 一个DFA,可以通过多条路径识别一个符号串
B. 一个DFA识别的语言是一个无限集合,则该DFA的状态数也得是无限个
C. 一个DFA识别的语言是一个无限集合,则该DFA的状态图一定含有回路
D. 一个DFA无法接受空串ε

A：DFA每个状态的后续状态都是确定的,它对每个符号串的识别路径也是确定的,只有一条识别路径;
B：根据概念所知,DFA的状态数都是有限个；
D：只要DFA开始状态也是终止状态,则该DFA就能识别空串。

---

6.将识别各类单词的有限自动机合并后得到的有限自动机会:（A）
A. 可能是NFA,也可能是DFA
B. 一定是DFA
C. 一定是NFA
D. 一定是最小的DFA

---

7. 关于NFA的确定化说法正确的是:（ABD）
A. NFA的确定化算法具有消除ε空边的功能
B. 给定一个NFA,一定存在一个DFA,使得两者等价
C. 一个NFA只能存在一个DFA与其等价
D. NFA确定化后会使得状态转换函数成为单值函数

B：根据等价定理判别正确；
A,D：NFA确定化后转化为DFA,而DFA无空边,且状态转换函数是单值函数，故正确；
C：错是因为NFA等价的DFA可以有多个,但最简DFA就一个。

---

8. 自动机实现的直接转向法说法正确的是:（AD）
A. 直接转向法是基于状态转换图实现的一种方法
B. 直接转向法程序设计简单,但占用存储空间大
C. 直接转向法是基于状态转换矩阵实现的一种方法
D. 直接转向法占用存储空间小,但相应的程序较长

自动机的实现通常有两种方法:状态转换矩阵法和直接转向法（也就是状态转换图）。
状态转换矩阵法优点是程序短,但占用存储空间多;
直接转向法是基于状态转换图的方法,优点是占用空间小,但程序较长。

---

9. 设计确定有限状态自动机，识别被5整除的二进制正整数（不包括有前导零的数）。
参考答案：

我做的答案：

---

---

第三章：词法分析器的实现

一. 概括（思维导图）

教学内容：
3.1 词法分析器实现前的准备
3.2 词法分析器的具体实现
3.3 实现词法分析器的注意事项
知识点：词法分析器任务，词法分析器设计。
重点：词法分析器的任务与设计，状态转换图。

tokenization，也叫word segmentation,是一种操作，它按照特定需求，把文本切分成一个字符串序列 (其元素一般称为token，或者叫词语)。

一般来说，我们要求序列的元素有一定的意义，比如“text mining is time-consuming”需要处理成"text mining/ is/ time-consuming"，其中"text mining"表示"文本挖掘"。 如果我们把语料中所有的token做一个去重，就得到了一个词汇表，其中的每一个词语被称为type。 英文信息处理中,tokenization需要把"I’m Li"这样的句子转换为"I am Li"，即将一些词语、短语的写法规范化。

---

二. 练习题

1. 词法分析器的输入是（B）
A、单词符号串
B、源程序
C、语法单位
D、目标程序

词法分析器的功能是将源程序由字符序列转换等价的token序列,并检查源程序中的词法错误,因此词法分析器的输入是源程序。

---

2. 作为语法分析程序子程序的词法分析程序,它的返回结果是( C)
A、单词属性值
B、单词在符号表中的位置表示法
C、单词的种别编码和语义值
D、单词的种别编码
当词法分析程序作为语法分析器的子程序存在时,语法分析器的每次调用,词法分析器都会返回一个token,token是单词的机内表示,包含单词的种类信息和语义值。

---

3. 将编译程序分成若干个“遍”是为了(B )
A、利用有限的机器内存并提高机器的执行效率
B、使程序的结构更加清晰
C、提高程序的执行效率
D、利用有限的机器内存但降低了机器的执行效率

所谓“遍”就是对源程序或源程序的中间表示形式从头到尾扫描一次,并作加工处理,生成新的中间结果或目标程序。
编译程序分成若干“遍”,实际就是编译程序对源程序或其等价的中间代码扫描了若干次,每次都执行不同的功能,这样做的目的是编译程序的结构更加清晰。

---

4. 词法分析中能够发现以下(C )错误。
A、操作数类型不匹配
B、标识符重复声明
C、程序中出现非法符号
D、除法溢出
词法分析器的功能是将源程序由字符序列转换等价的token序列,并检查源程序中的词法错误,以上错误中,只有非法符号属于词法错误。

---

5. 编译程序中的语法分析器接受以（ C ）为单位的输入,并产生有关信息供以后各阶段使用。
A、表达式
B、产生式
C、单词
D、语句
词法分析器的功能是将源程序由字符序列转换等价的token序列,并检查源程序中的词法错误,因此语法分析器接受以单词(由字符组成)为单位的输入。

---

6.在词法分析阶段不能识别的是(C )。
A、标识符
B、运算符
C、四元式
D、常数
词法分析器的功能是将源程序由字符序列转换等价的token序列,并检查源程序中的词法错误,token中包含了单词的种类信息（保留字、标识符、常量、特殊符号）和语义值,四元式不属于单词，且往往是优化阶段的产物,所以在词法分析阶段无法识别。

---

7.是否存在这样一些语言,它们能被确定有限自动机识别,但不能用正则表达式表示（B）。
A. 存在
B. 不存在
C. 无法判定是否存在

正则表达式和自动机在接受语言的能力上是等价的。

---

8. 文法G所描述的语言是( D)的集合。
A. 文法G的字母表V中所有符号组成的符号串。
B. 文法G的字母表的闭包V*中的所有符号串。
C. 由文法的开始符推出的所有符号串。
D. 由文法的开始符推出的所有终极符号串。

由文法定义可知,文法所定义的语言是由该文法的开始符推导出的所有的终极符串的集合。

---

9. 下列文法能够产生如图所示语言的是(D )。

A.
Z→aZb | aAb | b
A→aAb | b
B.
A→aAb
A→b
C.
Z→AbB
A→aA | a
B→bB | b
D.
Z→aAb
A→aAb | b
注意语言特点,所有两边a和b的个数对称,至少有一个。

---

10. 正则表达式和有限自动机的关系以下说法正确的是:(BC)
A. 一个正则表达式只能等价于一个确定的有限自动机
B. 正则表达式、NFA和DFA在接受语言的能力上是相互等价的
C. 对任何形式正则表达式r,都存在一个NFA M,满足L(M)=L®
D. 一个正则表达式可以转化为一个等价的自动机,但自动机不一定都能表示为等价的正则表达式

正则表达式和自动机在接受语言的能力上是等价的,并且一个正则表达式有可能等价于多个自动机。

---

11. 请说明四类文法在产生式的限制和语言描述能力上的关系（AD）
A. 从0型文法到3型文法，对产生式的限制逐步增强
B. 从0型文法到3型文法，对产生式的限制逐步减弱
C. 从0型文法到3型文法，语言描述能力逐步增强
D. 从0型文法到3型文法，语言描述能力逐步减弱

四类文法讲解

---

---

第四章：自顶向下的语法分析方法

一.概括（思维导图）

关于求First集、Follow集、LL(1)表这篇博客写的好好

教学内容：
4.1 文法定义
4.2 文法等价变换
4.3 语法分析功能
4.4 三个集合的求法
4.5 递归下降分析方法
4.6 LL(1)分析方法

4.1：文法定义部分，这部分知识点是语法分析的理论基础
4.2～4.4：文法等价变换、语法分析功能和三个集合的求法。其中，文法等价变换只要求掌握消除公共前缀，消除直接左递归，其他的文法等价变换方法了解就可以。三个集合的求法是重点也是难点，是必须掌握的知识点。
4.5：递归下降法部分，这是本章的重点内容。在递归下降法中，要了解递归下降语法分析的思想，掌握递归下降语法分析程序的构造。
4.6：LL（1）语法分析方法部分是本章的重点内容，需要了解LL（1）语法分析方法的思想，学会构造LL（1）分析表，掌握LL(1)语法分析程序的构造，针对一个文法，对给定符号串，能给出分析过程。

关于“短语、直接短语、句柄”这篇博客写的不错

---

二.练习题

1.如果文法G是无二义性的，则它的任何句子α：（A）
A. 最左推导和最右推导对应的语法树必定相同
B. 最左推导和最右推导对应的语法树可能不同
C. 最左推导和最右推导必定相同
D. 可能存在两个不同的最左推导

答案解析：如果文法G是无二义性的，对它的任何句子α来说，最左推导和最右推导对应的语法树必定相同，只不过最左推导是先生长左边的枝叶，而最右推导先生长右边的枝叶；对于D，如果有两个不同的最左推导，则必然有二义性。因此选A。

2. 已知如下文法:
E→TE’ | ε
E’→+TE’ | ε
T→FT’
T’→*FT’ | ε
F→(E) | id
则Follow(F)=(D ).

A. {*,+}
B. {*,ε}
C. {+,#, )}
D. {*,+,#,)}
E. {#,)}
F. {*,+,#, ),id}
1
2
3
4
5
6

3.编译过程中，语法分析的功能是（C ）。
①分析单词是怎么样构成的; ②分析单词串是如何构成语句的; ③分析语句是如何构成程序的; ④分析程序的结构。
A. ②③
B. ④
C. ②③④
D. ①②③④

4. 设有文法G[S]为：
S->AB|bC
A-> ε|b
B-> ε|aD
C->AD|b
D->aS|c
则First(S)包含以下哪些字符：（ABD）
A. a
B. b
C. c
D. ε
E. #

5. 设有文法G[S]为：
S->AB|bC
A-> ε|b
B-> ε|aD
C->AD|b
D->aS|c
则Follow(A)包含以下哪些字符：（ACE）
A. a
B. b
C. c
D. ε
E. #

6. 设有文法G[S]为：
S->eT | RT
T->DR | ε
R->dR | ε
D->a | bd
则First(S)集合包含以下哪些字符？（ ABCDE）
A. a
B. b
C. d
D. e
E. ε
F. #
7. 已知如下文法：
S→eT | RT
T→DR | ε
R→dR | ε
D→a | bd
则First(S)=( ① ), First(T)=( ② ), First®=( ③ ), First(D)=( ④ )。
答案：
① {a,b,d,e,ε}，②{a,b,ε}，③ {d,ε}，④{a,b}

8. 通过文法等价变换消除以下文法G[E]的左递归，并用变换后的文法画出表达式i*i+i*(i+i)+i的语法树。
   E -> T | E + T
   T -> F | T * F
   F -> i | ( E )
   
   
   9. 已知如下文法：
   S→eT | RT
   T→DR | ε
   R→dR | ε
   D→a | bd
   求First（S）、First（T）、First（R）、First（D）。
   正确答案：
   First（S）={ a, b, d, e, ε }
   First（T）={ a, b, ε }
   First（R）={ d, ε}
   First（D）={ a, b }
   答案解析：根据First集的定义：
   First(S) = First(eT) ∪ First(RT) = { e } ∪ { d, a, b, ε} = { a, b, d, e, ε }
   First(T) = First(DR) ∪ {ε} = {a,b} ∪ {ε} = { a,b,ε}
   First® = First(dR) ∪ {ε} = {d} ∪ {ε} ={ d, ε}
   First(D) = First(a) ∪ First(bd) = { a, b}

10.设有文法G[S]如下：
S→a | (T)
T→T,S | S
请给出句子(a,(a,a))的所有短语、简单短语和句柄。

正确答案：
短语： (a,(a,a) )、a,(a,a) 、第一二三个a、(a,a)、a,a
简单短语:第一二三个 a
句柄：第一个a
答案解析：根据短语，简单短语和句柄的定义可以求得。
也可以先画出句子的语法树，之后根据每棵子树的叶子节点求得短语，每棵简单子树的叶子节点求得简单短语，最左端简单子树的叶子节点求得句柄。

11.
答案：

---

---

第五章：自底向上的语法分析方法

一. 概括（思维导图）

二. 练习题

1. 高级语言编译程序的语法分析方法中,递归下降法属于( B )分析方法。
A. 自左至右
B. 自顶向下
C. 自底向上
D. 自右至左

2. 【判断题】使用自顶向下分析法，要先消除文法的左递归。（√）

3.【判断题】对于任何文法，都能将其改写成LL(1)文法。（×）
有4个条件才能写成LL(1)文法：

加一个条件：并且文法里没有公共前缀！！！！
不然在进行分析过程的时候，对于某个输入字符，分支匹配两条以上支路，肯定不知道怎么跳转。

4.下列文法中，____ C_____是LL(1)文法。
A. S->aSb | ab
B. S->ab | Sab
C. S->aSb | b
D. S->aS | a

解析：
A：存在公共前缀
B：存在直接左递归
D：存在公共前缀

5.已知如下文法:
S->eT | RT
T->DR | ε
R->dR | ε
D->a | bd
则该文法的LL(1)分析表为( D )。

解析：

6.下列文法中属于LL（1）文法的是：（AD）
A.
G[S]:
S → ABc
A → a | ε
B → b | ε

B.
G[S]:
S → Ab
A → a | B | ε
B → b | ε

C.
G[S]:
S → ABBA
A → a | ε
B → b | ε

D.
G[S]:
S → aSe | B
B → bBe | C
C → cCe | d

---

7. 如图

解析：

---