文档介绍：该【上海大学编译原理试卷秋B 】是由【小屁孩】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【上海大学编译原理试卷秋B 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..上海大学编译原理试卷秋B一、选择题(本题共22分,每小题2分)将一个或多个正确答案的编号填入每题题干中的横线上。错选、多选、少选均不得分。,则A*=∪A2∪…∪An∪…∪A1∪A2∪…∪An∪…C.{ε}∪A+∪A+[A]的规则为:A→A1|A0|Aa|Ac|a|b|c,..如果在推导过程中的任何一步αβ都是对α中的最右非终结符进行替换,,:..(a|b)(a|b|0|1)*→aA|→aA|bAA→0A|1A|εA→aA|bA|0A|→aA|→AA→aA|bA|0A|1A|εA→A|bA|0A|1A|→…BC…的规则,其中A,B,C是非终结符,(1)(0)[E]:E→E+T|TT→T*F|FF→(E)|a则句型T+T*F+*+T*F:..(0)分析器的核心部分是一张分析表,它包括两部分,(1)(0)、是非判断题(本题共10分,每小题1分)正确的在题后的括号内填T,,最右推导的逆过程也称为规范过程。(T)。(T)。(T),其中一个被认为是初态,最多有一个终态。(F)(1)文法。(F)。(T),即继承属性和综合属性。(T)。(T)、过程可嵌套且支持递归调用。(T)。(T)三、(本题满分10分)(a|b)a(a|b)构造一个确定的有穷自动机DFA。为正规式*(1):(4分):..(2)NFA确定化为DFA的过程如下表所示:(4分)表2:NFA确定为DFA的过程(并换名)(3):(2分)、(本题满分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|ε→→→'''①求出能推出ε的非终结符②求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分)(4)对符号串(a,(a,a))#的分析过程如下:(4分)所以符号串(a,(a,a))#是该文法的句子。五、(本题满分15分)证明下面文法不是LR(0)文法,但是SLR(1)文法。S→A:..A→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:3分)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分):..算符优先关系表因为该文法的任意两个终结符之间最多只有一种优先关系,所以该文法是算符优先文法(2分)。七、(本题满分10分)将下面语句翻译成四元式序列(假设四元式起始标号为100)。WhileAorB【解答】(10分)100ifAgoto104101goto102103goto112104ifx>6goto106105goto109106t:=x-1107x:=t108goto100109t:=x+1110y:=t111goto100112