北方工业大学《编译原理》期中试卷2019

北方工业大学试卷第1页共11页北方工业大学《编译原理》课程期中答案2019年春季学期开课学院：信息学院考试方式：闭卷考试时间：95分钟班级姓名学号题号一二三四五六总分满分10201060100得分阅卷人一、判断题(每个小题1分，共10分，正确的打上√，错误的画上×)1.编译程序的输出是机器语言语言程序。2.一个上下文无关文法包含一组开始符号和一组终结符号。3.一个文法具有二义性，是该文法有两个不同的推导方式。4.词法分析时，单词符号有五种类别，其中常数没有属性信息。5.语法分析时，必须先消除文法中的左递归。6.构造LR分析器的任务就是构造LR分析表。7.递归下降分析法是自上向下分析法。8.某计算机上的某编译程序在另一台计算机上能直接使用的必要条件是两台计算机的操作系统功能完全相同。9.LL(1)文法是无二义的文法。10.SLR分析法的S是简单的意思。1.×；2.×；3.×；4.×；5.×；6.√；7.√；8.×；9.√；10.√。二、单项选择题（每题1分，共20分）请将答案填写在下面的答题表中题号12345678910答案DABADCDCDB题号11121314151617181920答案CBCBCDBACD1、下列不属于编译程序前端的结构是（）。A．词法分析器B．语法分析器C．语义分析D．目标代码生成器2、下列对编译程序描述正确的是（）。序号订线装()()()()()()()()()()北方工业大学试卷第2页共11页A．编译程序能把一种语言程序转换成另一种语言程序B．编译程序只是对高级语言的翻译C．链接程序只有链接功能D．优化是对目标代码的优化3、已知下列文法G[S]，请问它的语言是（）。G[S]:S→dAA→aA|aA．{dman|n1,m1}B．{dan|n0}C．{dand|n=1}D．{and|n0}4、下列正规表达式中与(a*|b*)c等价的表达是（）。A．a*c|b*cB．a*|b*cC．a*c|b*D．(a|b)*c5、下列状态转换图识别的字符串是（）。A．以1开头的二进制数组成的集合B．以0结尾的二进制数组成的集合C．含奇数个1和0的二进制数组成的集合D．以1开头，0结尾的二进制数组成的集合6、DFA与NFA的描述正确的是（）。A．可以从NFA转换到DFA，转换前后的初态与终态结点不变B．NFA与DFA都只包含一个初态结点C．NFA和DFA都可以有多条箭弧从一个状态结点出发D．NFA的结点数肯定多于DFA的状态结点数7、若一个文法具有左递归，则它能产生的句子的个数是（）。A．有限个B．无穷个C．不确定D．根据其他产生式而定8、对短语的描述正确的是（）。A．短语是由产生式直接生成的B．在归约的过程中，每个短语都是句柄C．在归约的过程中，部分短语是句柄D．直接短语包含素短语9、已知下列文法G[E]，该文法对于句型E+a*(F+T)的直接短语包含（）。G[E]:E→E+T|TT→F|T*FF→a|(E)A．TB．EC．a*(F+T)D．F10、若文法G的符号集是无限的，则该文法必然是（）。A.二义性的B.递归的C.无二义性的D.前后文无关的11、已知文法S→xSxy|y，请问它所识别的语言是（）。A．xyxB．(xyx)*C．xny(xy)n(n=0)D．x*yx*12、已知语言xnyyn(n=1)，则下述文法中，可以产生该语言的文法是（）。A.S→xSy|xAy|xB.S→xAyA→xAy|xA→xAy|yXY101，0北方工业大学试卷第3页共11页C.S→AyBD.S→xAy|yA→xB|xA→xB→xy|y13、已知下列状态转换图，与它等价的正规式是（）。A．(a|b)a(a|b)B．(a|b)a*(a|b)C．(a*|b*)a(a|b)D.(a|b)*aab14、已知文法G[S]，该文法的FOLLOW(A)是（）。G[S]:S→xAB|yA→xB|εB→(S)|εA．{(,ε,#}B．{(,),#}C．{(,),ε,#}D．{),#}15、已知文法G[S]，该文法对于输入串xxByxxB的最左素短语是（）。G[S]:S→xABA→xBy|yB→xB|x|yA．xB．xByC．xBD．y16、已知文法G[E]，该文法对于输入串i1*i2+T*F进行规范归约的第4步的句柄是（）。G[E]:ET|E+TTF|T*FF(E)|iA．i1B．i2C．TD．T*F17、已知某语言可表示所有包含1个a或者多个a，并且以b结尾字符串，该正规式是（）。A.a*bB.aa*bC.a*|abD.a|a*b18、已知递归下降程序如下，请问该程序对应的文法是（）。PROCEDUREE；IFSYM=‘+’THENBEGINADVANCE；T；EEND；A.E+TE|B.E+T|+EC.E+|TED.E+T|E19、已知LL(1)预测分析表，请问对于输入字符i+i分析时，可选的产生式有（）。a,baa,b北方工业大学试卷第4页共11页非终结符输入字符i+*#EE→TE’E→+TETT→iT→T→FTE’E’→+TE’E’→(1)E→TE’(2)T→i(3)E→+TE(4)T→(5)E’→+TE’(6)T→FT(7)E’→A.所有产生式B.(3)(4)(5)(6)(7)C.(1)(2)(5)(7)D.(1)(2)(3)(5)(7)20、已知文法G[S]，请问该文法对于输入串aacabccb的最左推导正确的是（）。G[S]:SaAcB|BdSABaB|aBc|aBaScA|cAB|bA.SBdSaScAdSaBdScAdSabdScAdSabdaAcBcAdSabdaacBcAdSabdaacbcAdSabdaacbcadSabdaacbcadaAcBabdaacbcadaacBabdaacbcadaacbB.SaAcBaaBcaacABcaacaBcaacabcC.SBdSaScAdSaaAcBcAdSaaacBcAdSaaacbcAdSaaacbcadSaaacbcadaAcBaaacbcadaacBaaacbcadaacbD.SaAcBaaBccBaacaBccBaacabccBaacabccb三、填空题(每空1分，共10分)1、编译程序的输入是_______________输出是_______________。2、编译程序结构中，除了包含词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成以外，还包含_______________和_______________。3、文法G的开始符号S，Sx(x∈VT)，则x是文法G的一个_______________；若SAx(A∈VN,x∈VT)，则Ax是文法G的一个_______________。4、自上而下分析中，主要面临的问题是_______________和_______________。5、已知语言L={aibj|ji=1}，能产生该语言的上下文无关文法是_______________，该文法_______________二义性文法。1.源语言程序、目标语言程序2.表格管理、出错管理3.句子、句型4.左递归、回溯5.G[S]:S→aSb|Sb|b、是四、综合题(共60分)1.已知文法G[S]:S→aA|bB|aCA→aB|b|bCB→bC|aC→b(1)请判断该文法的二义性；(2)请给出该文法的NFA图;(3)请对NFA确定化，画出DFA图；北方工业大学试卷第5页共11页(4)请最小化该DFA，画出最小化的DFA图。（10分)答案：（1）该文法对输入串ab具有二义性，SaAab,SaCab（2）由文法G[S]构造的NFA状态转换矩阵和由NFA状态转换矩阵生成的NFA状态转换图状态abS{A,C}{B}A{B}{Z,C}B{Z}{C}CØ{Z}ZØØ（3）对NFA确定化的状态转换矩阵和对NFA确定化后的DFA状态转换图IIaIb0{S}1{A,C}2{B}1{A,C}2{B}3{Z,C}2{B}4{Z}5{C}3{Z,C}4{Z}4{Z}5{C}4{Z}（4）最小化DFA的步骤和具体思路：1.初始集合：把所有状态分为{非终态组},{终态组}={0,1,2,5}，{3,4}2.{0，1，2，5}，{3，4}考察{3，4}，由于{3，4}a={Ø},{3，4}b={4}⊂{3,4},{3，4}经过a弧和b弧到达同一个状态组，所以不可分。当前状态组依然为{0，1，2，5}，{3，4}3.{0，1，2，5}，{3，4}考察{0，1，2，5}，由于{0，1，2，5}a={1，2，4}，它既不包含在{0，1，2，5}，也不包含在{3，4}之中，因此，应把{0，1，2，5}一分为二。由于状态0、1经a弧到达状态1、2包含在{0，1，2，5}中，而状态2经a弧到达状态4包含在{3，4}中，状态5经a弧不到达任何状态，因此，应该把状态2和5划分出来。当前状态组为：{0，1}，{5}，{2}，{3，4}4.{0，1}，{2}，{3，4}，{5}考察{0，1}，由于{0，1}a={1，2},它既不包含在{0，1}，也不包含在{3，4}和{2}之中，因此，应把{0，1}一分为二。当前状态组为：{0}，{1}，{2}，{3，4}，{5}5.最终分组结果{0}，{1}，{2}，{3，4}，{5}6.对分组重新编号以后结果：0，1，2，3，5SABCZbaaaabbbb013254aaabbbbb北方工业大学试卷第6页共11页对DFA最小化分组后的状态转换矩阵：状态ab0{1}{2}1{2}{3}2{3}{5}3Ø{3}5Ø{3}DFA最小化后的状态转换图：01325abaabbbb2.已知有限自动机如下图所示（1）请给出该状态转换图表示的语言；（2）写出其正规式与正规文法；（3）构造识别该语言的最小化DFA。（10分)答案：（1）状态转换图表示的语言：以多个或0个0或1开头，中间2个1，以多个或0个0或1结尾的字符串。{(0m|1n)11(0x|1y)|m,n,x,y=0}。（2）正规式：(0|1)*11(0|1)*正规文法：G(A):A→0A|1A|1BB→1CC→0C|1C北方工业大学试卷第7页共11页（3）对该有限自动机NFA图生成确定化状态转换矩阵：II0I10{A}0{A}1{A,B}1{A,B}0{A}2{A,B,C}2{A,B,C}3{A,C}2{A,B,C}3{A,C}3{A,C}2{A,B,C}对NFA确定化后的DFA的状态转换图：最小化DFA的具体步骤和思路：1.初始集合：把所有状态分为{非终态组},{终态组}={0，1}，{2，3}2.{0，1}，{2，3}：考察{0，1}，{0，1}0={0}⊂{0，1},{0，1}1={1，2}，它既不包含在{0，1}，也不包含在{2，3}之中，因此，应把{0，1}一分为二，划分为{0}，{1}。当前分组结果：{0}，{1}，{2，3}3.{0}，{1}，{2，3}考察{2，3}，{2，3}0={3}⊂{2，3}，{2，3}1={2}⊂{2，3}，所以，它不能划分。当前分组结果：{0}，{1}，{2，3}4.最终分组结果：{0}，{1}，{2，3}5.对分组结果重新编号以后的结果：0，1，2最小化DFA后的状态转换矩阵和状态转换图：状态010{0}{1}1{0}{2}2{2}{2}3.已知文法G[E]E→E+T|TT→T*F|TF|FF→(E)|i(1)画出句型T+T*F*(T-i)的语法分析树；(2)找出句型T+T*F*(T-i)的所有短语、素短语、最左素短语、直接短语和句柄。（8分)021300001111021000,111北方工业大学试卷第8页共11页答案：(1)语法分析树如右图(2)短语：T，i，T-i，(T-i)，T*F，T*F*(T-i)，T+T*F*(T-i)素短语：i，T*F最左素短语：T*F直接短语：T，i，T*F句柄：T4.已知下文法G[D]D→TLT→int|realL→idRR