《编译原理期末考试试卷A卷.pdf》由会员分享，可在线阅读，更多相关《编译原理期末考试试卷A卷.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 编译原理试卷答题时限：120 分钟 考试形式：闭卷笔试得分统计表:号 二三四一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共20分）得分注意：须将本题答案写在下面的表格中，写在其它地方无效1234567891 0DCBDDBCBDC1.编译程序是对（）A.汇编程序的翻译C.机器语言的执行B.高级语言程序的解释执行D.高级语言的翻译2.词法分析器的输出结果是（）A.单词的种别编码C.单词的种别编码和自身值B.单词在符号表中的位置D.单词自身值3.在规范规约中，用()来刻画可规约串。A.直接短语 B.句柄 C.最左素短语 D.素短语*4.与正规式(a lb)(c Id)等价的正
2、规式是()*A.a(c I d)I b(c I d)B.a(c I d)I b(c I d)*C.a(c I d)I b(c I d)D.(alb)c I (a I b)d5.若项目集IK含有A f a,则在状态K 时，仅当面临输入符号aeFOLLOW（A）时，才采取A r a 动作的一定是（）A.LALR文法 B.LR（0）文法 C.LR文法 D.SLR文法6.四元式之间的联系是通过（）实现的。A.指示器 B.临 时 变 量 C.符号表 D.程序变量7.文法G：S f xS x ly 所识别的语言是（）A.xyx B.（xyx）C.xnyxn（n0）D.x yx8.有一语法制导翻译如下所示:
3、S fb A b print T A f（B print 2”A-a print 3”B-Aa）print 4若输入序列为b（aa）a）a）b,且采用自下而上的分析方法，则输出序列为（）A.32224441 B.34242421 C.12424243 D.344422129.关于必经结点的二元关系，下列叙述不正确的是（）A.满足自反性 B.满足传递性 C.满足反对称型 D.满足对称性10.错误的局部化是指（）。A.把错误理解成局部的错误 B.对错误在局部范围内进行纠正C.当发现错误时，跳过错误所在的语法单位继续分析下去D.当发现错误时立即停止编译，待用户改正错误后再继续编译二、判 断 题（每小
4、题1分，共5分）得分1.文法G 的一个句子对应于多个推导，则G 是二义性的。（义）2.动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（J）3.算符优先文法采用“移进一规约”技术，其规约过程是规范的。（X）4.删除归纳变量是在强度削弱以后进行。（V ）5.在目标代码生成阶段，符号表用于目标代码生成。（X）三、事 答 题（每小题5分,共15分）得分*1.构造正规式（0 1 1）00相应的正规式并化简。（共 5 分）（1）根据正规式，画出相应的NFAM（2 分）（2）用子集法将NFA确定化（2 分）IIoIIx,l,21,2,31,21,2,31,2,3,41,21,21,2,31,
5、2”,2,3,4)32,3,41,2将所有子集重命名，得到转换矩阵:S01012132212332（3）化简，并画出DFAM（1分）划分为状态：0,2 1 3 将这三个状态命名为0,1,2三个状态s010101202202 .设文法G S :（共5分）S -S +a T I a T I+a TT *a T I*a（1）写 出 句 型a T +a*a*a的最右推导并画出语法树（2分）S n S+a T n S+a*a T n S+a*a*a n a T+a*a*a s（2）写出该句型中所有的短语、直接短语、句柄和最左素短语。（3分）短语：a T *a*a、*a、a T+a*a*a直接短语：a T
6、、*a句 柄:a T最左素短语：a T3 .将下列语句翻译为逆波兰表示，三元式、间接三元式和四元式表示：（共5分）a =（b+c）*e +（b+c）/f（1）逆波兰表示（1分）a bc+e*b c +f/+=（2）三 元 式（1分）（+,b,c）（*，,e）（+,b,c）。工:置ii可 、间 (4)四元式(2分)(+,b,c,Tl)(*,Tl,e,T2)(+,b,c,T3)(/,T3,f,T4)(+,T2,T4,T5)(=,T5,a)四、综合题(共60分)得分1.已知文法G(S)：(共15分)Sf*AAT 0A1 I*求文法G的各非终结符号的FIRSTVT和LASTVT集合。(5分)FIRST
7、VT(S)=*LASTVT(S)=1,*FIRSTVT(A)=0,*LASTVT(S)=1,*(2)构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法。(5分)文法G 的任何终结符对至多只存在一种优先关系，所以文法G是一个算符优先文法。*01*0(3)分析句子*0*1,并写出分析过程。(5分)步骤符号栈输入串输出0#*0*1#1#*0*1#2#*0*1#3#*0*1#4#*0A1#5#*OA1#6#*A#7#S#分析正确2.已知文法G(S)：(共15分)S aS I bS I a(1)构造该文法的拓广文法。(1分)(o)s，一s(1)S f aS(2)A-bS(3)A-*a 构造其LR(
8、O)项目集规范族，并给出识别活前缀的DFA。(7分)(3)构造其SLR分析表，并判断该文法是否是SLR文法。(7分)状态h移进一规约冲突，计算S的Follow集合：Follow(S)=#,可以采用SLR冲突消解法,得到如下SLR分析表：状态ACTIONGOTOab#S0S)S231Sis2n42Sis253acc4h512该文法是SLR（1）文法。3.设有如下基本块：（共 10分）T1=A+BT2=5M=T2*4T3=C-DT4=M+T3L=T1*T3T4=A+BN=T4（2）假设变量L,M,N 在基本块出口之后是活跃的，给出优化后的四元式序列。（5 分）N=A+BM=20T3=C-DL=N*
9、T34.以下程序段是最内循环（共 13分）A=O1=1L1:B=J+1C=B+1A=C+Aif 1=100 GOTO L21 =1+1GOTO LIL2:流图中有一条回边B3 一 B 2,且 B2DOMB3,所以，有一个循环B2,B3,B2是循环入口结点，也是出口结点。(2)对循环优化(8 分)1.代码外提：对于B 2中的赋值四元式B=J+1,由于循环中没有对J 的定值操作，所有对J的定值都在循环外，所以，它是循环中的不变运算，可以进行代码外提。2.删除归纳变量：循环中I 是基本归纳变量，C 是与I 同族的归纳变量，两者有如下线性关系：C=B+L则1=100可以用C=B+100替代，相应的1=1+1可用C=C+1替代,再将新的不变运算提到循环外。5.有一程序如下：program ex;a:integer;procedure PP(x:integer);begin:x:=5;x:=a+lend;begina:=2;PP(a);write(a)end试用图表示ex调用PP(a)前后活动记录的过程。(共7分)I PP的活动记录(调用PP(a)之后)DISPLAY 表PP_SPex_SP形式参数X参数个数：1全局DISPLAY地址返回地址ex_SP局部变量：aDISPLAY 表ex_SP参数个数：0全局DISPLAY地址返回地址ex_SPex的活动记录 (调用PP(a)之前)