《编译原理》单元测试第三章试题.pdfVIP

百学须先立志。——朱熹

编译原理

2014—2015学年第二学期第三单元测试试卷

（闭卷考试）时间：45分钟。

姓名班级出题人刘兵班级（满分100分）

题目一二三四五总分

得分

一、选择题（5*2分）（每题1分，共10分）

1．下述正规表达式中_____与（a*+b）*（c+d）等价。

A．a*（c+d）+b（c+d）B.a*（c+d）*+b（c+d）*

C．a*（c+d）b*（c+d）D.（a+b）*c+（a+b）*d

2．词法分析器的输出结果是（）

A．单词的种别编码B.单词在符号表中的位置

C．单词的种别编码和自身值D.单词自身值

3．正规式M1和M2等价是指（）

A．M1和M2状态数相等B.M1和M2有向边条数相等

C．M1和M2所识别的语言集相等D.M1和M2状态数和有向边条数相等

4．DFAM(见图1)接受的字集为。

a.以0开头的二进制数组成的集合

b.以0结尾的二进制数组成的集合

c.含奇数个0的二进制数组成的集合

d.含偶数个0的二进制数组成的集合

图1

5．在下列正规表达式中，_______描述了字母表{a，b}上长度不为3的符号串

A．ε|0|1|00|01|10|11|（0|1）（0|1）+

B．ε|0|1（00|01|10|11）+（0|1）*

C．ε|0|1（00|01|10|11）*

D．没有一个

百学须先立志。——朱熹

二、简答题（2*10分）（每题10分，共20分）

1．什么是扫描器？扫描器的功能是什么？

2.给定如图2所示的有穷自动机，试用正规表达式给出它能接受的语言集合。

三、分析题（4题共70分）

1．化简下面文法：

G[S]:S-Bab|cC

B-b|bS

C-Da

D-Cb|CDa

百学须先立志。——朱熹

2．设字母表∑={a,b,0,1},请写出满足下述条件的正规表达式：以字母a或b开头，以1

结尾。

3．构造一个DFAM，它接受字母表{a,b,c}上,以a或b开始的字符串，或以c开始但所

含的a不多于一个的字符串。

4.正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。

百学须先立志。——朱熹

编译原理

2014—2015学年第二学期第三单元测试答案

答案

一.1.d2.C3.C4.d5.d

二1.扫描器就是词法分析器，它接受输入的源程序，对源程序进行词

法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分

析器使用