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

编译原理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）*d2．词法分析器的输出结果是（）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的二进制数组成的集合图15．在下列正规表达式中，_______描述了字母表{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|cCB-b|bSC-DaD-Cb|CDa2．设字母表∑={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.扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。2.本题考查正规表达式与有穷自动机的等价性。对于一个在输入字母表∑上的FAM，一定可以在字母表∑上构造一个正规表达式e，使得L(e)=L(M).根据状态转换图，从开始状态出发，可以有任意个（包括0个）b作为句子的开始部分；从0状态出发，每输入一个a，不许输入两个b才能到达终止状态后，还可以通过输入a回到状态1，或输入b回到状态0，然后进入递归过程，再输入相同的符号串，所以，该有穷自动机描述的语言为：(b*(aa*b)*b)*三.1.化简为：S-BabB-b|bS2.a（a|b|0|1）*1|b（a|b|0|1）*13.4.正规式(ab)*a对应的NFA如图2-5所示，正规式a(ba)*对应的NFA如图2-6所示。这两个正规式最终都可得到最简DFA，如图2-7所示。因此，这两个正规式等价。