天津理工大学编译原理期末考试试卷

试卷编号：1-A第1页共9页天津理工大学考试试卷2009～2010学年度第二学期《编译原理》期末考试试卷课程代码：0660116试卷编号：1-A命题日期：2010年6月15日答题时限：120分钟考试形式：闭卷笔试得分统计表：大题号总分一二三四一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共20分）得分注意：须将本题答案写在下面的表格中，写在其它地方无效12345678910DCBDDBCBDC1.编译程序是对（）A.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译2.词法分析器的输出结果是（）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)*d5.若项目集IK含有A·，则在状态K时，仅当面临输入符号aFOLLOW(A)时，才采取A·动作的一定是（）A．LALR文法B．LR(0)文法C．LR(1)文法D．SLR(1)文法6.四元式之间的联系是通过（）实现的。试卷编号：1-A第2页共9页A.指示器B.临时变量C.符号表D.程序变量7．文法G：SxSx|y所识别的语言是（）A．xyxB．(xyx)*C．xnyxn(n≥0)D．x*yx*8.有一语法制导翻译如下所示：SbAb{print“1”}A(B{print“2”}Aa{print“3”}BAa){print“4”}若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为（）A．32224441B.34242421C．12424243D.344422129．关于必经结点的二元关系，下列叙述不正确的是（）A．满足自反性B．满足传递性C．满足反对称型D．满足对称性10．错误的局部化是指（）。A．把错误理解成局部的错误B．对错误在局部范围内进行纠正C．当发现错误时，跳过错误所在的语法单位继续分析下去D．当发现错误时立即停止编译，待用户改正错误后再继续编译二、判断题（每小题1分，共5分）得分1.文法G的一个句子对应于多个推导，则G是二义性的。（×）2.动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√）3.算符优先文法采用“移进－规约”技术，其规约过程是规范的。（×）4.删除归纳变量是在强度削弱以后进行。（√）5.在目标代码生成阶段，符号表用于目标代码生成。（×）三、简答题（每小题5分，共15分）得分1.构造正规式(0∣1)*00相应的正规式并化简。（共5分）（1）根据正规式，画出相应的NFAM（2分）（2）用子集法将NFA确定化（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}X12340001试卷编号：1-A第3页共9页将所有子集重命名，得到转换矩阵：S01012132212332（3）化简，并画出DFAM（1分）划分为状态：{0,2}{1}{3}将这三个状态命名为0，1，2三个状态S010101202202.设文法G[S]:（共5分）S→S+aT|aT|+aTT→*aT|*a（1）写出句型aT+a*a*a的最右推导并画出语法树（2分）SS＋aTS＋a*aTS+a*a*aaT+a*a*a（2）写出该句型中所有的短语、直接短语、句柄和最左素短语。（3分）短语：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/+=101200101SS＋a*a*aTaTT试卷编号：1-A第4页共9页(2)三元式（1分）①(+,b,c)②(*,①,e)③(+,b,c)④(/,③,f)⑤(+,②,④)⑥(=,a,⑤)(3)间接三元式（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分）S*AA0A1|*(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分）试卷编号：1-A第5页共9页步骤符号栈输入串输出2.已知文法G(S)：（共15分）SaS|bS|a(1)构造该文法的拓广文法。（1分）(0)S’→S(1)S→aS(2)A→bS(3)A→a(2)构造其LR(0)项目集规范族，并给出识别活前缀的DFA。（7分）0#*0*1#1#*0*1#2#*0*1#3#*0*1#4#*0A1#5#*0A1#6#*A#7#S#分析正确I1:S→a.SS→.aSS→.bSS→.aS→a.I4:S→aS.aS试卷编号：1-A第6页共9页(3)构造其SLR分析表，并判断该文法是否是SLR(1)文法。（7分）状态I1移进－规约冲突，计算S的Follow集合：Follow(S)＝{#}，可以采用SLR冲突消解法，得到如下SLR分析表：状态ACTIONGOTOab#S0S1S231S1S2r342S1S253acc4r15r2该文法是SLR（1）文法。3.设有如下基本块：（共10分）T1=A+BT2=5M=T2*4T3=C-DT4=M+T3L=T1*T3T4=A+BN=T4(1)画出该基本块的DAG图。（5分）I0:S’→.SS→.aSS→.bSS→.aI2:S→b.SS→.aSS→.bSS→.aI3:S’→S.I5:S→bS.aaSbbSbn10n3n8T1,T4,NT4L+*试卷编号：1-A第7页共9页(2)假设变量L，M，N在基本块出口之后是活跃的，给出优化后的四元式序列。（5分）N＝A＋BM=20T3=C-DL=N*T34.以下程序段是最内循环（共13分）A=0I=1L1:B=J+1C=B+IA=C+AifI=100GOTOL2I=I+1GOTOL1L2:(1)画出程序流图，并找出回边与循环。（3分）流图中有一条回边B3B2，且B2DOMB3，所以，有一个循环{B2,B3}，B2是循环入口结点，也是出口结点。A=0I=1L1：B=J+1C=B+IA=C+AifI=100gotoL2I=I+1GOTOL1L2：B1B2B3B4n9T3D20试卷编号：1-A第8页共9页(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分）5.有一程序如下：programex;a:integer;procedurePP(x:integer);begin:x:=5;x:=a+1end;begina:=2;PP(a);write(a)end试用图表示ex调用PP(a)前后活动记录的过程。（共7分）A=0I=1B=J+1C=B+IR=B+100L1：A=C+AifC=RgotoL2C=C+1GOTOL1L2：B1B2B3B4试卷编号：1-A第9页共9页PP_TOP→PP_SP→ex_TOP→ex_SP→DISPLAY表PP_SPex_SP形式参数x参数个数：1全局DISPLAY地址返回地址ex_SP局部变量：aDISPLAY表ex_SP参数个数：0全局DISPLAY地址返回地址ex_SPPP的活动记录（调用PP（a）之后）ex的活动记录（调用PP（a）之前）