编译原理阶段练习一.doc

编译原理练习一
一、 填空题
1．编译程序的工作过程一般可以划分为 词法分析、语法分析、语义分析、代码生成、代码优化等几个基本阶段，同时还会伴有表格处理和出错处理。

2．若源程序是用高级语言编写的，目标程序是机器或汇编语言的程序，则其翻译程序称为编译程序。

3．编译程序与解释程序的根本区别在于是否生成目标代码。

4．如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：编译阶段和运行阶段。如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为三个阶段：编译阶段、汇编阶段和运行阶段。

5．词法分析的任务是：依据语言的词法规则，分析由字符组成的源程序，把它识别为一个一个具有独立意义的最小语法单位，即“单词”，并识别出与其相关的属性。

6．确定的有限自动机是一个五元组（五元式），通常表示为DFA=（K，S，M，S，Z）。

7．高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常量 以及运算符、界限符。

8．词法分析程序的输出形式是一个单词，每个单词由单词类别和单词自身值
两部分组成。

9．高级语言的语言的处理程序分为解释程序和编译程序两种。编译程序有五个阶段，而解释程序通常缺少代码优化和目标代码生成。其中，代码优化的目的是使最后阶段产生的目标代码更为高效。与编译系统相比，解释系统比较简单，可移植性好，执行速度慢。解释程序处理语言时，大多数采用的是先将源程序转化为中间代码，再解释执行方法。BASIC就是一种典型的解释型语言。

10．编译程序与具体的机器有关，与具体的语言无关。

二、 选择题（单项或多项）
1．在使用高级语言编程时，首先可通过编译程序发现源程序的全部 a 错误和部分 b 错误。
a、语法 b、语义 c、语用 d、运行

2．程序语言的语言处理程序是一种 （1）a。 （2）b 是两类程序处理程序，它们的主要区别在于 （3）d 。
（1）a、系统软件 b、应用软件 c、实时系统 d、分布式系统
（2）a、高级语言程序和低级语言程序 b、解释程序和编译程序
c、编译程序和操作系统 d、系统程序和应用程序
（3）a、单用户和多用户的差别 b、对用户程序的差错能力
c、机器执行效率 d、是否生成目标代码

3．下面关于解释程序的描述正确的是 a 。
a、 解释程序的特点是处理程序时不产生目标代码
b、 解释程序适用于COBOL和FORTRAN语言
c、 解释程序是为打开编译程序技术的僵局而开发的

4．要在某一台机器上为某种语言构造一个编译程序，必须掌握下述三方面的内容： c 、 d 、 f 。
a、汇编语言 b、高级语言 c、源语言 d、目标语言
e、程序设计方法学 f、编译方法 g、测试方法 h、机器语言

5．由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成 b ，诸阶段的工作往往是 h 进行的。
a、过程 b、遍 c、批量 d、程序 e、顺序 f、并行
g、成批 h、穿插

6．编译程序必须完成的工作有 a b c d 。
a、词法分析 b、语法分析 c、语义分析 d、代码生成
e、中间代码生成 f、代码优化

7．编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过
a b c 这几步。
a、编辑 b、编译 c、连接 d、运行

8．“用高级语言书写的源程序都必须通过编译，产生目标代码后才能投入运行。”这种说法 a 。
a、不正确 b、正确

9．编译程序生成的目标程序 b 是机器语言的程序。
a、一定 b、不一定

10．编译程序生成的目标程序 b 是可执行的程序。
a、一定 b、不一定

11．编译过程中词法分析器的任务包括 a b c d e f g
。
a、 组织源程序的输入
b、 按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出
c、 删除注解
d、 删除空格及无用字符
e、 行记数、列记数
f、 发现并定位词法错误
g、 建立符号表

12．正则式的“|”读作 b ，“•”读作 c ，“*”读作 d 。
a、并且 b、或者 c、连接 d、闭包

13．设有如图所示的有穷自动机，状态j为开始状态，状态n为终止状态，假设digit代表数字0到9。则下述实数中 d 可被该有穷自动机识别。
a、+47 b、-1 c、 .5 d、-11.47 e、至少两个
1
2
3
4
5
digit
digit
digit
+
.
digit
e a

-

14．设有穷自动机的状态转换图如下状态j为开始状态，状态l为终止状态，则下述正则表达式中 a b 可被该有穷自动机识别
a、0（10）*0 b、11（01）*1 c、 1（101）*00
1
2
4
3
0
1
0
1
0
1
1
5

150
． b 这样一些语言，它们能被确定的有限自动机识别，但不能用正则表达式表示。
a、存在 b、不存在 c、 无法判定是否存在

三、 构造下列正则式相应的DFA
1．1(0|1)*101

0
DFA为：

0
0
C

1

Þ
E
1
D
A
S

0
1

0
1
B

1

1

2．b((ab)*|bb)*ab
D

b
b
NFA为：

b
a
H
I
G
b
e
e
C
B
Þ
A

e
e

E

b
a

F

子集法求DFA…….略

四、 将所示的NFA确定化

S
Z
Þ
1
0
0
0，1
Q
V
U
1
0
1
0,1
0，1

子集法求DFA得：

0

0
0
D
B

1
0

Þ
A
0
1

1
E
C

1
1

五、 将所示的DFA最小化
7
6
1
Þ
b
a
c
5
3
4
d
2
a
d
a
b
b
b
c
b
b

最小DFA为：
c
b

b
b
a
6

Þ
3
1

d
a

5

六、构造一个DFA，它接受的符号串集合等于正则表达式(ab*c)|(abc*)所示的符号串集合。要求先构造NFA，其次转换成DFA，最后加以简化。

c
5
b
4
c
b
a
a
3
2
Þ
1
NFA为：

DFA为：

A
Þ
B
C
E
a
b
b
c
c
c
c
c
b
D
F
G

c
F
D
b
c
c
c
b
b
a
E
C
B
Þ
A
最小DFA为：