华东交通大学2016-2017学年度第一学期编译原理期末样题

第1页共6页背面有试题装O订O线O华东交通大学2016—2017学年第一学期(样题)(A)卷课程名称：编译原理(B)考试时间：分钟考试方式：闭卷学时：48学时学生姓名：学号：教学班级：教学小班序号：一、是非判断题(对下列各题，请在答题卡上对应的小题中，对的打“√”，错的打“×”，共10小题，每题1分，共计10分)1.编译程序和机器硬件有关，和具体的语言无关。2.NFA在识别记号的时候会产生大量的回溯。3.每个文法都能改写为LL(1)文法。4.LR分析表是由动作表和转移表两部分组成的。5.文法G的一个句子对应于多个推导，则G是二义性的。6.算符优先文法采用“移进－规约”技术，其规约过程是规范的。7.在目标代码生成阶段，符号表用于目标代码生成。8.综合属性的计算方式是自上而下包含自身。9.语法分析时必须先消除文法中的左递归。10.两个正规集相等的必要条件是他们产生的符号串是相同的。二、单项选择填空题(对下列各题，请在答题卡上对应的小题中填上你的选项，共10小题，每题2分，共计20分)1.编译程序是对()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.四元式之间的联系是通过()实现的。A.指示器B.临时变量C.符号表D.程序变量题号一二三四五六七八九十总分得分10206910151515100阅卷人得分得分第2页共9页背面有试题2装O订O线O7．文法G：SxSx|y所识别的语言是()A．xyxB．(xyx)*C．xnyxn(n≥0)D．x*yx*8.语法分析中的立法机构是()A.正规式B.上下文无关文法C.上下文有关文法D.预测分析器9.编译的各个阶段中，与源程序打交道的阶段是A.语法分析B.语义分析C.词法分析D.代码优化10.下面的逆波兰表达式：ab+cd+*,所代表的中缀形式的表达式是()A.a+b+c*dB.(a+b)*(c+d)C.(a+b)*c+dD.a+b*c+d三、(本题共计6分)给出生成下述语言的上下文无关文法：(1){anbnambm|n，m=0}(3分)(2)为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，7等构造一个文法。(3分)四、(本题共计9分)一个上下文无关文法生成句子abbaa的推导树如下：(1)给出串abbaa最左推导、最右推导。(3分)(2)该文法的产生式集合P可能有哪些元素？(3分)(3)找出该句子的所有短语、直接短语、句柄。(3分)得分第3页共6页背面有试题装O订O线O五、(本题共计10分)已知某NFA的状态转换矩阵如下表所示，将此NFA确定化，构造最小化DFA，要求写出具体解题过程。表NFA的状态转换矩阵abcd13224236354735546676得分第4页共9页背面有试题4装O订O线O六、(本题共计15分)对于文法文法G[S]：S→S*aT|aT|*aTT→+aT|+a；判定G[S]是否是LL(1)文法，若不是，试图将文法G[S]改写成等价的LL(1)文法，并构造预测分析表，若是，请直接给出其LL(1)分析表。第5页共6页背面有试题装O订O线O七、(本题共计15分)对文法G[S]:S→aSb|PP→bPc|bQcQ→Qa|a构造简单优先关系表。该文法是否是简单优先文法？(只需要将序号部分补充完整)得分SabPQcS(5)a(1)(2)(6)(10)(12)b(3)(7)(11)P(8)(13)Q(4)(14)c(9)(15)第6页共9页背面有试题6装O订O线O八、(本题共计15分)已知文法G(S)：SaS|bS|a(1)构造该文法的拓广文法。(1分)(2)构造其LR(0)项目集规范族，并给出识别活前缀的DFA。(7分)(3)构造其SLR分析表，并判断该文法是否是SLR(1)文法。(7分)第7页共6页背面有试题装O订O线O华东交通大学2016—2017学年第一学期样题(A)答题纸一、是非判断题(共10小题，每题1分，共计10分)12345678910FTFTFFFFFT二、单项选择填空题(每题2分，共计20分)12345678910DCBDDBCBCB三、(本题共6分)解:(1)S→AAA→aAb|ε(3分)(2)G[S]:S-S+D|S-D|DD-0|1|2|3|4|5|6|7|8|9(3分)四、(本题共9分)解:(1)串abbaa最左推导:S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa最右推导：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa3分(2)产生式有：S→ABS|Aa|εA→aB→SBB|b3分(3)该句子的所有短语、直接短语、句柄有：3分短语直接（简单）短语句柄a1相对A1√√ε相对S√b1相对B1√b2相对B2√a2相对A2√εbb相对Baa相对Saεbbaa相对S五、(本题共10分)解：从上表中可以看出，该NFA已经是DFA，所以直接对其进行最小化(2分)初始分划Π0:终态组｛6,7｝，非终态组｛1,2,3,4,5｝---------------------(2分)对{1,2,3,4,5}进行审查：{1,2}输入b到达｛2｝，而{3,4}输入b到达｛6,7｝，{5}输入b不会有任何动作，故得到新分划{1,2}{3,4}{5}-----------------------(2分)Π1:{1,2}{3,4}{5}{6,7}Π1即是最后划分,----------------------(2分)重新命名,以1，3，5，6代替{1,2}{3,4}{5}{6,7}得最小化的DFA如下表2所示第8页共9页背面有试题8装O订O线O表2最小化后的DFAabcd13136355366(2分)六、(本题共15分)解：消除左递归后的文法G’:S→aTS’|*aTS’S’→*aTS’|εT→+aT|+a提取左公因子得文法G’’:S→aTS’|*aTS’S’→*aTS’|εT→+aT’T’→T|εSelect(S→aTS’)={a}Select(S→*aTS’)={*}Select(S→aTS’)∩Select(S→*aTS’)=ФSelect(S’→*aTS’)={*}Select(S’→ε)=Follow(s’)={#}Select(S’→*aTS’)∩Select(S’→ε)=ФSelect(T→+aT’)={+}Select(T’→T)=First(T)={+}Select(T’→ε)=Follow(T’)={*,#}Select(T’→T)∩Select(T’→ε)=Ф所以该文法是LL(1)文法。预测分析表：*+a#SS’Ta,NTS’T,NS’S’Ta,Nε,PTT’a,NT’ε,PT,Pε,Paε,N#OK七、(本题共15分)解：简单优先关系矩阵如下：SabPQcS=a=36b1abcb5da第9页共6页背面有试题装O订O线Ob==P=Q==c由于矩阵中有元素存在多种优先关系，故不是简单优先文法。八、(本题共15分)解：(1)构造该文法的拓广文法。(1分)(0)S’→S(1)S→aS(2)A→bS(3)A→a(2)构造其LR(0)项目集规范族，并给出识别活前缀的DFA。(7分)(3)构造其SLR分析表，并判断该文法是否是SLR(1)文法。(7分)状态I1移进－规约冲突，计算S的Follow集合：Follow(S)＝{#}，可以采用SLR冲突消解法，得到如下SLR分析表：状态ACTIONGOTOab#S0S1S231S1S2r342S1S253acc4r15r2该文法是SLR(1)文法。I0:S’→.SS→.aSS→.bSS→.aI2:S→b.SS→.aSS→.bSS→.aI3:S’→S.I5:S→bS.aaSbbSbI1:S→a.SS→.aSS→.bSS→.aS→a.I4:S→aS.aS