23307235 编译原理试卷.docx

上传人:p** 文档编号:1006450 上传时间:2024-06-15 格式:DOCX 页数:8 大小:31.95KB
下载 相关 举报
23307235 编译原理试卷.docx_第1页
第1页 / 共8页
23307235 编译原理试卷.docx_第2页
第2页 / 共8页
23307235 编译原理试卷.docx_第3页
第3页 / 共8页
23307235 编译原理试卷.docx_第4页
第4页 / 共8页
23307235 编译原理试卷.docx_第5页
第5页 / 共8页
23307235 编译原理试卷.docx_第6页
第6页 / 共8页
23307235 编译原理试卷.docx_第7页
第7页 / 共8页
23307235 编译原理试卷.docx_第8页
第8页 / 共8页
亲,该文档总共8页,全部预览完了,如果喜欢就下载吧!
资源描述

《23307235 编译原理试卷.docx》由会员分享,可在线阅读,更多相关《23307235 编译原理试卷.docx(8页珍藏版)》请在第壹文秘上搜索。

1、23307235编译原理一、判断题(共10题,20分)1、语法分析时必须先消除文法中的左递归。(2.0)错误2、在自下而上的语法分析中,语法树与分析树一定相同。(2.0)错误3、有穷自动机接受的语言是正则语言。(2.0)正确4、有穷自动机接受的语言是正则语言。(2.0)正确5、对一个右线性文法G,必存在一个左线性文法G,使得1.(G)=1.(G),反之亦然。(2.0)正确6、一个有限状态自动机中,有且仅有一个惟一终态。(2.0)错误7、语法分析时必须先消除文法中的左递归。(2.0)错误8、确定的自动机以及不确定的自动机都能正确地识别正规集。(2.0)正确9、对任意一个右线性文法G,都存在一个N

2、FAM,满足1.(G)=1.(M)。(2.0)正确10、在自下而上的语法分析中,语法树与分析树一定相同。(2.0)错误二、多选题(共5题,10分)11、符号表的每一项均包含(AC)。(2.0)A、名字栏B、类型栏C、信息栏D、值栏12、中间代码主要有(ACDE)。(2.0)A、四元式B、间接三元式C、三元式D、后缀式)有能力描述它。13、对正规文法描述的语言,以下(ABCDE(2.0)A、0型文法B、1型文法C、上下文无关文法D、右线性文法E、左线性文法14、下列优化中,属于循环优化的有(ABE)。(2.0)A、强度削弱B、合并已知量C、代码外提D、删除归纳变量15、对1.R分析表的构造,有可

3、能存在(CE)动作冲突。(2.0)A、移进归约移进/归约归约/归约三、问答题(共3题,30分)16、写出算术表达式:A+B*(C-D)+E(CT)tN的:四元式序列;三元式序列;间接三元式序列(10.0)答案6.解答:表达式的四元式序列:(-,C,D,T)(2) (*,B,Ti,T2)(3) (+AKT3)(4) (-,CAT4)(5) (t,T4,N,T5)(6) (Z,E,T5,T6)(7) (+,T3,TT7)表达式的三兀式序列(1)(-,C,D)(2)(*,B,(1)(+A(2)(-,C,D)(t,(4),2(/EQ)(+X3),(6)间接三元式序列(CD)(2)(*,B,(1)(3)

4、(+A(2)(t,(l),N)(5)(/,E,(4)(十,(6)17、按指定类型,给出语言的文法。1.=aibjjil的上下文无关文法。(10.0)答案:1.解答:由1.=abIji21知,所求该语言对应的上下文无关文法首先应有SfaSb型产生式,以保证b的个数不少于a的个数;其次,还需有SfSb或SfbS型的产生式,用以保证b的个数多于a的个数;也即所求上下文无关文法GS为:GS:SaSbSbb18、分别写出语句a:=b*-c+b*-c的四元式、三元式和间接三元式的表示。(10.0)答案5.解答:三地址语句的四元式表示OPArglArg2Result(0)(1)(2)(3)(4)(5)umi

5、nus*uminus*+assigncbcbt2t5tlt3t4tlt2t3t4t5a三地址语句的三元式表示OPArglArg2(0)(1)(2)(3)(4)(5)minus*uminus*+assigncbcb(1)a(0)(2)(3)(4)三地址语句的间接三元式表示(O)(1)(2)(3)(4)(5)(14)(15)(16)(17)(18)(19)opArglArg2(14)(15)(16)(17)(18)(19)minus*uminus*+assigncbcb(15)a(14)(16)(17)(18)四、综合题(共2题,40分)19、将文法GV改造成为1.1.(I)的。GV:V-NNEE

6、VV+ENi(20.0)答案:8.解答:对文法GV提取公共左因子后得到文法:G,V:VNAAEEVBB+ENi求出文法GV中每一个非终结符号的FlRST集:FIRST(V)=iFIRST(八)=,FIRST(E)=iFIRST(B)=,FIRST(N)=i求出文法GIV中每一个非终结符号的FO1.1.oW集:FO1.1.oW(V)=#UFIRST(B)吩UFo1.1.oW(E)=#,+,FO1.1.OW(八)=FO1.1.OW(V)=+#FO1.1.OW(E)=FIRST()UFO1.1.OW(B)=FIRST()UF01.1.0W(E)=FO1.1.OW(B)=FO1.1.OW(E)=FO1

7、.1.OW(N)=FIRST(八)UFO1.1.OW(V)=,+,#可以看到,对文法GTV的产生式AT钳印,有FIRST(E)FO1.1.OW(八)=+,=0对产生式BTe+E,有FIRST(+E)FO1.1.OW(B)=+=0而文法的其他产生式都只有一个不为的右部,所以文法GV是1.1.(I)文法。20、请写出在=(a,b)上,不是a开头的,但以aa结尾的字符串集合的正规表达式,并构造与之等价状态最少的DFA。(20.0)答案:解答:根据题意,不以a开头就意味着以b开头,且以aa结尾的正规式为:b(ab)*aa根将图1所示的NFA确定化,如图2所示。从图2可知已为最简状态,由于开始状态0只能输入字符b而不能与状态1合并,而状态2和状态3面对输入符号的下一状态相同,但两者一为非终态、一为终态,故也不有合并,故图2所示的状态转换矩阵已是最简的DFA,如图3所示据正规式画出NFA,如图1所示。IkIbx(11,2(1,2)1,2,Y(1,2,Y)12Y图2状态转换矩阵重新命名IASaBIj1121231331a2ba图3最简DFA

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!