中国大学mooc《编译原理(武汉理工大学) 》章节测试答案

title编译原理(武汉理工大学)中国大学mooc答案100分最新版content作业第2章文法与语言第2章作业1、文法G＝({A,B,S},{a,b,c},P,S),其中P为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

评分规则:

参考答案：L(G[S])={abc}评分指南：（1)与答案一致得2分；（2)答案式中等号左侧不规范，右侧正确得1分；（3)其它情况得0分。

2、文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？

评分规则:

参考答案：L(G[N])={

|V∈{0,1,2,3,4,5,6,7,8,9},n>=1}或者L(G[N])={允许0开头的非负整数}评分指南：（1)正确得2分；(2)主体（等式的右部）正确得1分；（3)其它情况0分。3、考虑下面上下文无关文法：S→SS|SS+|a(1)说明通过此文法如何生成串aa+a，并为该串构造语法树。(2)G[S]的语言是什么？

评分规则:

参考答案：（1)此文法生成串aa+a的最右推导如下(也可以使用其它推导方式）:S=>SS=>SS=>Sa=>SS+a=>Sa+a=>aa+a,语法树如下：（2)该文法生成的语言是：和+的后缀表达式，即逆波兰式。（也可以给出L(G[S])的表达式）评分指南：（1)解题正确得4分，部分正确酌情得1-2分，不正确得0分。（2)解题正确得2分，部分正确酌情得1分，不正确得0分。4、文法S→Ac|aBA→abB→bc是二义的吗？说明理由。

评分规则:

参考答案：对于串abc(1)S=>Ac=>abc;(2)S=>aB=>abc存在两不同的最右推导。所以，该文法是二义的。（注意：也可采用最左推导）或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。评分指南：解题正确得5分，部分正确酌情得2分，不正确得0分。5、给出生成下述语言的上下文无关文法：

评分规则:

参考答案：评分指南：每个解答正确得3分，7个解答正确得21分；每个解答部分正确得1分，不正确得0分。注意：上面答案不唯一，只要文法能正确定义相应得语言就算正确。6、给出生成下述语言的三型文法：

评分规则:

参考答案：评分指南：每个解答正确得3分，3个解答正确得9分；每个解答部分正确得1分，不正确得0分。注意：上面答案不唯一，只要文法能正确定义相应得语言就算正确。作业第3章词法分析第3章词法分析作业（适用于软件工程专业）1、构造下列正规式相应的DFA.1(0|1)*101

评分规则:

以下4步全对得10分，其中第1步占2分，第2步占3分，3步各占1分，第4步占2分。注意：下面状态图或矩阵中结点的命名方式可以因人而异，但结点个数不能与参考答案不同。2、已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。

评分规则:

以下4步全对得10分，其中第1步占2分，第2步占3分，3步各占1分，第4步占2分。注意：（1)下面状态图或矩阵中结点的命名方式可以因人而异，但结点个数不能与参考答案不同。（2）第1步也可以是画出状态转换图。3、给文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b构造相应的最小的DFA。

评分规则:

以下5步全对得12分，其中第1步占2分，第2步占3分，3步各占1分，第4步占2分，第5步4分。注意：（1)下面状态图或矩阵中结点的命名方式可以因人而异，但结点个数不能与参考答案不同。（2）第1步也可以是画出状态转换图。

第4步全对得2分，第5步全对得4分，部分对酌情给分。4、为下边所描述的串写正规式，字母表是{a,b}.(1)以ab结尾的所有串(2)包含偶数个b且含任意数目a的所有串

评分规则:

全对得6分，每题占3分，每题部分对得1分。参考答案如下：(1)(a|b)ab(2)bb(bb)a*作业第3章词法分析第3章词法分析作业（适用于数据科学与大数据技术专业）1、为下边所描述的串写正规式，字母表是{a,b}.(1)以ab结尾的所有串(2)包含偶数个b但不含a的所有串(3)只包含一个a的所有串(4)包含ab子串的所有串

评分规则:

（1）(a|b)ab（2）bb(bb)（3）bab（4）(a|b)ab(a|b)2、给定一个有穷自动机（FA）表示如下：请回答如下问题：（1）串000111是否能被上面自动机所接受，请说明理由。（2）请写出上面FA的五元组表示形式（3）该FA是确定的有穷自动机吗？为什么？

评分规则:

教师批改作业第3章词法分析词法分析实验（软件工程专业）1、词法分析实验要求：1.每位学生任选附件中4道实验题目之一，可以独立完成，也可以4位学生为一组完成。2.4位学生为一组完成为加分项。要求每位学生完成1道实验题，并考虑前后的接口衔接问题，最后得到一个完整的词法分析程序自动构造