编译原理期末考试试卷A卷

TJUT《编译原理》试卷答题时限：120分钟考试形式：闭卷笔试得分统计表：大题号一二三四总分一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共20分）得分注意:须将本题答案写在下面的表格中，写在其它地方无效感谢阅读12345678910DCBDDBCBDC1。编译程序是对（）A。汇编程序的翻译B.高级语言程序的解释执行C。机器语言的执行D.高级语言的翻译感谢阅读词法分析器的输出结果是(）A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身值 D．单词自身值3。在规范规约中，用（）来刻画可规约串。A．直接短语B．句柄 C．最左素短语D．素短语4。与正规式(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感谢阅读若项目集IK含有A·，则在状态K时，仅当面临输入符号aFOLLOW（A)时，才采取A·动作的一定是（)感谢阅读A．LALR文法B．LR(0)文法C．LR（1）文法D．SLR（1)文法谢谢阅读6。四元式之间的联系是通过（）实现的。A.指示器B.临时变量C。符号表D.程序变量7．文法G：SxSx｜y所识别的语言是（)谢谢阅读A．xyxB．(xyx)＊C．xnyxn（n≥0）D．x*yx*感谢阅读8.有一语法制导翻译如下所示：SbAb {print“1"}A(B {print“2"｝Aa {print“3”}BAa） {print“4”}若输入序列为b(((aa）a）a)b,且采用自下而上的分析方法，则输出序列为（)精品文档放心下载A．32224441B.34242421C．12424243D。344422129．关于必经结点的二元关系，下列叙述不正确的是（）谢谢阅读A．满足自反性B．满足传递性C．满足反对称型D．满足对称性感谢阅读10．错误的局部化是指（ )。试卷编号： 1-A 第1页共7页A．把错误理解成局部的错误B．对错误在局部范围内进行纠正谢谢阅读C．当发现错误时，跳过错误所在的语法单位继续分析下去感谢阅读D．当发现错误时立即停止编译,待用户改正错误后再继续编译谢谢阅读二、判断题（每小题1分，共5分）得分1.文法G的一个句子对应于多个推导,则G是二义性的。（×）谢谢阅读2。动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√）精品文档放心下载3。算符优先文法采用“移进－规约”技术，其规约过程是规范的。（×）谢谢阅读4。删除归纳变量是在强度削弱以后进行。（√）5。在目标代码生成阶段,符号表用于目标代码生成.(×）精品文档放心下载三、简答题(每小题5分，共15分)得分构造正规式（0∣1）＊00相应的正规式并化简。（共5分）（1）根据正规式，画出相应的NFAM(2分）谢谢阅读0X120034（2)用子集法将1NFA确定化（2分）II0I1{x,1，2}{1，2，3}{1,2}｛1，2,3｝{1,2,3，4}{1,2}{1,2}｛1,2，3｝{1,2}｛1，2，3，4}{1，2，3,4｝｛1,2｝将所有子集重命名，得到转换矩阵:S01012132212332（3）化简，并画出DFAM（1分）划分为状态:｛0，2}{1}｛3｝将这三个状态命名为0，1，2三个状态精品文档放心下载S010101202201100102012.设文法G［S]：（共5分）S→S+aT｜aT|+aT试卷编号： 1-A 第2页共7页T→＊aT|＊a（1）写出句型aT+a*a＊a的最右推导并画出语法树（2分)感谢阅读SS＋aTS＋a*aTS+a＊a*aaT+a＊a＊a S感谢阅读S ＋ a Ta T* a T(2）写出该句型中所有的短语、直接短语、句柄和最左素短语。*(3分a)感谢阅读短语:aT、*a＊a、＊a、aT+a＊a＊a直接短语：aT、＊a句柄：aT最左素短语：aT3。将下列语句翻译为逆波兰表示,三元式、间接三元式和四元式表示：（共5分)谢谢阅读a=(b+c）＊e+（b+c）/f（1)逆波兰表示（1分）abc+e＊bc+f/+=三元式（1分)(+，b,c）②（＊，①，e)③（+，b,c）④(/，③，f)⑤（+，②,④)⑥（=,a,⑤）间接三元式（1分）（+,b,c)② （*,①,e)③(/，①,f）(+，②，③）⑤（=,a,④)间接码表：①②①③④⑤（4）四元式（2分)① （+,b,c，T1)② （*，T1，e,T2)(+,b，c,T3)④（/,T3,f，T4）⑤(+，T2，T4,T5)(=,T5，－,a）四、综合题（共60分）得分1.已知文法G（S)：（共15分）试卷编号： 1-A 第3页共7页S＊A0#*0*1＃1#＊0＊1#2＃*0*1＃3＃*0*1＃4#＊0A1＃5#＊0A1＃6＃＊A#7＃S#分析正确A0A1|＊（1)求文法G的各非终结符号的FIRSTVT和LASTVT集合。（5分）谢谢阅读FIRSTVT（S)={*} LASTVT(S）=｛1，＊}谢谢阅读FIRSTVT(A）=｛0，*｝LASTVT(S）=｛1,*}谢谢阅读（2)构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法。（5分）谢谢阅读＊01*<〈>0〈〈=1〉文法G中的任何终结符对至多只存在一种优先关系，所以文法G是一个算符优先文法。(3）分析句子*0＊1，并写出分析过程.（5分）精品文档放心下载步骤符号栈输入串输出2。已知文法G（S)：（共15分）谢谢阅读SaS|bS｜a(1)构造该文法的拓广文法。（1分）（0)S’→S（1）S→aS(2)A→bS（3）A→a（2）构造其LR(0）项目集规范族,并给出识别活前缀的DFA。（7分）谢谢阅读aI1:S→a.SSI4:S→aS.S→.aSS→.bSS→.aS→a.试卷编号： 1-A 第4页共7页I0:S’→.SS→.aS

baS→.bSS→.ab

I2:S→b.SS→.aSS→.bSS→.a

S I3:S’→S.aI5:S→bS.b(3）构造其SLR分析表,并判断该文法是否是SLR（1)文法。（7分）谢谢阅读状态I1移进－规约冲突，计算S的Follow集合：Follow(S）＝｛#}，可以采用SLR冲突消解法，得到如下SLR分析表：谢谢阅读状态ACTIONab0S1S21S1S22S1S2345该文法是SLR（1)文法。3。设有如下基本块：（共10分）T1=A+BT2=5M=T2*4T3=C—DT4=M+T3L=T1＊T3T4=A+BN=T4(1)画出该基本块的DAG图。（5分） n10 L谢谢阅读*n9

GOTO#S3r345accr1T320D分)(2)假设变量L，M,N在基本块出口之后是活T4跃的，给出优化后的四元式序列。(5N＝A＋B+M=20n3T1,T4,NT3=C-Dn8+试卷编号：1-A第5页共7页－n1n2n4T2n5Mn6n7L=N*T34.以下程序段是最内循环(共13分）A=0I=1L1:B=J+1C=B+IA=C+AifI=100GOTOL2I=I+1GOTOL1L2:(1)画出程序流图，并找出回边与循环.（3分）A=0I=1 B1L1：B=J+1C=B+I B2A=C+AifI=100gotoL2I=I+1 B3GOTOL1L2： B4流图中有一条回边B3B2，且B2DOMB3，所以，有一个循环{B2，B3｝，B2是循环入口结点，也是出口结点。感谢阅读(2)对循环优化（8分）1.代码外提：对于B2中的赋值四元式B=J+1，由于循环中没有对J的定值操作，所有对J的定值都在循环外,所以，它是循环中的不变运算，可以进行代码外提。感谢阅读2.删除归纳变量：循环中I是基本归纳变量，C是与I同族的归纳变量，两者有如下线性关系：C=B+I，则I=100可以用C=B+100替代,相应的I=I+1可用C=C+1替代，再将新的不变运算提到循环外。精品文档放心下载(3)画出优化后的程序流图(2分）试卷编号： 1-A 第6页共7页A=0I=1B1B=J+1C=B+IR=B+100L1：A=C+AB2ifC=RgotoL2B3C=C+1GOTOL1L2： B4有一程序如下：programex；a：integer;procedurePP（x：integer)；begin：感谢阅读x:=5;x：=a+1end；begina：=2;PP（a）；write（a)end试用图表示ex调用PP(a）前后活动记录