您好,欢迎访问三七文档
当前位置:首页 > 机械/制造/汽车 > 机械/模具设计 > 上海大学编译原理试卷秋B
一、选择题(本题共22分,每小题2分)将一个或多个正确答案的编号填入每题题干中的横线上。错选、多选、少选均不得分。1.词法分析阶段的任务是__B___.A.识别表达式B.识别单词C.识别语句D.识别程序2.设A是字母表,则A*=__BCD___.A.A1∪A2∪…∪An∪…B.A0∪A1∪A2∪…∪An∪…C.{ε}∪A+D.A0∪A+3.设文法G[A]的规则为:A→A1|A0|Aa|Ac|a|b|c,则下列符号串__BCD__是该文法的句子.A.ab0B.a0c01C.aaaD.bc104..如果在推导过程中的任何一步αβ都是对α中的最右非终结符进行替换,则称这种推导为__BD___.A.直接推导B.最右推导C.最左推导D.规范推导5.程序设计语言的单词符号一般可分为5种,它们是ACD__及运算符和界符.A.常数B.表达式C.基本字D.标识符6.正规式(a|b)(a|b|0|1)*对应的文法为C__.A.S→aA|bAB.S→aA|bAA→0A|1A|εA→aA|bA|0A|1AC.S→aA|bAD.S→AA→aA|bA|0A|1A|εA→A|bA|0A|1A|ε7.通常程序设计语言的单词符号都能用AC__描述.A.正规文法B.上下文无关文法C.正规式D.上下文有关文法8.如果文法G中没有形如A→…BC…的规则,其中A,B,C是非终结符,则文法G是D__.A.算法优先文法B.LL(1)文法C.LR(0)文法D.算法文法9.文法G[E]:E→E+T|TT→T*F|FF→(E)|a则句型T+T*F+a的素短语是AB_.A.aB.T*FC.TD.T+T*F10.LR(0)分析器的核心部分是一张分析表,它包括两部分,分别是BC__.A.LL(1)分析表B.分析动作表C.状态转换表D.移进分析表11.LR(0)项目集规范族的项目类型可分为ABCD__.A.移进项目B.归约项目C.待约项目D.接受项目二、是非判断题(本题共10分,每小题1分)正确的在题后的括号内填T,错误的填F1.在形式语言中,最右推导的逆过程也称为规范过程。(T)2.每个直接短语都是某规则的右部。(T)3.任何正规文法都是上下文无关文法。(T)4.一张状态转换图包含有限个状态,其中一个被认为是初态,最多有一个终态。(F)5.无左递归的文法是LL(1)文法。(F)6.LR分析法是一种规范归约分析法。(T)7.文法符号的属性有两种,即继承属性和综合属性。(T)8.紧跟在条件转移语句后的语句是基本块的入口语句。(T)9.PL0程序具有分程序结构、过程可嵌套且支持递归调用。(T)10.符号表可以辅助上下文语义正确性检查。(T)三、(本题满分10分)为正规式*(a|b)a(a|b)构造一个确定的有穷自动机DFA。(1)构造NFA如图2.1所示:(4分)SABCZababa图2.1NFANεε(2)NFA确定化为DFA的过程如下表所示:(4分)表2:NFA确定为DFA的过程(并换名)IIaIb①[S,A,B]②[A,B,C]③[A,B]②[A,B,C]④[A,B,C,Z]⑤[A,B,Z]③[A,B]②[A,B,C]③[A,B]④[A,B,C,Z]④[A,B,C,Z]⑤[A,B,Z]⑤[A,B,Z]②[A,B,C]③[A,B](3)相应的DFA状态土如图2.2所示:(2分)1325ababa图2.2DFAM4baabb四、(本题满分18分)对文法G[S]S→(L)|aL→L,S|S(1)给出句子(a,((a,a),(a,a)))的一个最右推导(4分);(2)对文法G,消除左递归,使之成为LL(1)文法,并加以验证(6分)。(3)构造这个LL(1)文法的预测分析表(4分)。(4)用预测分析器给出输入串(a,(a,a))#的分析过程,并说明该串是否是G的句子(4分)。【解答】(1)最右推导为:(4分)S(L)(L,S)(L,(L))(L,(L,S))(L,(L,(L)))(L,(L,(L,S)))(L,(L,(L,a)))(L,(L,(S,a)))(L,(L,(a,a)))(L,(S,(a,a)))(L,((L),(a,a)))(L,((L,S),(a,a)))(L,((L,a),(a,a)))(L,((S,a),(a,a)))(L,((a,a),(a,a)))(S,((a,a),(a,a)))(a,((a,a),(a,a)))(2)将所给文法消除左递归得G’:(6分)S(L)|aLSLL,SL|①求出能推出ε的非终结符SLL′否否是②求First集FIRST(S)={(,a}FIRST(L)={(,a}FIRST(L′)={,,ε}③求Follow集FOLLOW(S)={FIRST(L′)–{ε}}∪FOLLOW(L)FOLLOW(L)={)}FOLLOW(L′)=FOLLOW(L)所以有,FOLLOW(S)=={#,,)}FOLLOW(L)={)}FOLLOW(L′)={)}④求Select集Select(S→(L))={(}Select(S→a)={a}Select(S→(L))∩Select(S→a)=Select(L→SL′)={(,a}Select(L′→,SL′)={,}Select(L′→ε)=FOLLOW(L′)={)}Select(L′→,SL′)∩Select(L′→ε)=所以,该文法是LL(1)文法。(3)构造预测分析表’:(4分)a(),#S→a→(L)L→SL′→SL′L′→ε→,SL′(4)对符号串(a,(a,a))#的分析过程如下:(4分)步骤分析栈剩余输入串所用产生式1#S(a,(a,a))#S→(L)2#)L((a,(a,a))#匹配3#)La,(a,a))#L→SL4#)LSa,(a,a))#S→a5#)Laa,(a,a))#匹配6#)L,(a,a))#L→,SL7#)LS,,(a,a))#匹配8#)LS(a,a))#S→(L)9#)L)L((a,a))#匹配10#)L)La,a))#L→SL11#)L)LSa,a))#S→a12#)L)Laa,a))#匹配13#)L)L,a))#L→,SL14#)L)LS,,a))#匹配15#)L)LSa))#S→a16#)L)Laa))#匹配17#)L)L))#L→ε18#)L)))#匹配19#)L)#L→ε20#))#匹配21##接受所以符号串(a,(a,a))#是该文法的句子。五、(本题满分15分)证明下面文法不是LR(0)文法,但是SLR(1)文法。S→AA→Ab|bBaB→aAc|a|aAb【解答】该文发的拓广文法如下:(8分)(0)S´→S(1)S→A(2)A→Ab(3)A→bBa(4)B→aAc(5)B→a(6)B→aAb构造识别该文法活前缀的有限自动机DFA:cB0I:S´→SA→·AA→·AbA→·bBa1I:S´→S·3I:A→b·BaB→·aAcB→·aB→·aAba6I:B→a·AcB→a·B→a·AbA→·AbA→·bBaaS8I:B→aA·cB→aA·bA→A·b10I:B→aAb·A→Ab·A2I:S→A·A→A·bA4I:A→Ab·b5I:A→bB·a7I:A→bBa·9I:B→aAc·abb3分)I2,I6存在移进-归约冲突。I10存在归约-归约冲突。∴该文法不是LR(0)文法。(4分)对于状态I2:FOLLOW(S)={#}。FOLLOW(S)∩{b}=,所以此状态的冲突可以通过SLR(1)方法消除。对于状态I6:FOLLOW(B)={a}。FOLLOW(B)∩{b}=,所以此状态的冲突也可以通过SLR(1)方法消除。对于状态I10:FOLLOW(B)={a}。FOLLOW(A)={b,c,#}。FOLLOW(A)∩FOLLOW(B)=,所以此状态的冲突也可以通过SLR(1)方法消除。∴该文法是SLR(1)文法。六、(本题满分15分)已知文法G[S]为:S→a||(T)T→T,S|S(1)计算G[S]的FIRSTVT,LASTVT.(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。【解答】(1)(5分)将文法改写成:S′→#S#S→a||(T)S→T,S|S用简单关系图方法求非终结符号的FIRSTVT,LASTVT如下:FIRSTVT(S′)={#}FIRSTVT(S)={a,,(}FIRSTVT(T)={a,,(,,}LASTVT(S′)={#}LASTVT(S)={a,,)}LASTVT(T)={a,,),,}(2)(8分)算符优先关系表a(),#a······(···=··)···,·····#···=·因为该文法的任意两个终结符之间最多只有一种优先关系,所以该文法是算符优先文法(2分)。七、(本题满分10分)将下面语句翻译成四元式序列(假设四元式起始标号为100)。WhileAorBDdoif(x6)thenx:=x-1elsey:=x+1【解答】(10分)100ifAgoto104101goto102102ifBDgoto104103goto112104ifx6goto106105goto109106t:=x-1107x:=t108goto100109t:=x+1110y:=t111goto100112
本文标题:上海大学编译原理试卷秋B
链接地址:https://www.777doc.com/doc-5078488 .html