上海大学编译原理试卷秋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→SL4#)LSa,(a,a))＃S→a5#)Laa,(a,a))＃匹配6#)L,(a,a))＃L→,SL7#)LS,,(a,a))＃匹配8#)LS(a,a))＃S→(L)9#)L)L((a,a))＃匹配10#)L)La,a))＃L→SL11#)L)LSa,a))＃S→a12#)L)Laa,a))＃匹配13#)L)L,a))＃L→,SL14#)L)LS,,a))＃匹配15#)L)LSa))＃S→a16#)L)Laa))＃匹配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