《编译原理A卷答案》由会员分享，可在线阅读，更多相关《编译原理A卷答案（8页珍藏版）》请在金锄头文库上搜索。
1、浙江工业大学之江学院 2011/2012（2） 编译原理A卷（答案）班级：姓名：题序12总分计分一、选择题（20*2=40）CBCAD ABDBACCDCD CDCDA二、问答题1.（5分）给出下图确定化后的 DFA。答：2.（5分）写出表达式（a+ b*c）/（a + b） d的逆波兰表示及三元式序列答：逆波兰表示：abc* + ab+ /d 三元式序列： （* , b, c） （+, a,） （+, a, b） (/，) ( ， d)3 (5 分) 已知文法 G(S)S-a| A |(T)TT, S|S写出句子(a , a), a)的规范归约过程及每一步的句柄。答：句型归约规则句柄(a，
2、a) ，a)Saa(S， a) ，a)TSS(T， a) ，a)Saa(T， S) ，a)TT， ST，S(S)，a)TSS(T)，a)SS(T)(T)(S，a)TSS(T，a)Saa(T，S)TT， ST，S(T)S(T)(T)S4 (5 分) 设文法 G(S) ：A BCc | gDBB bCDE|C DaB | caD dD |E gAf | c 计算每个非终结符的 FIRST 和 FOLLOW； 答：FIRST(A)=a,b,c,d,gFIRST(B)=b, 4FIRST(C)=a,c,dFIRST(D)=d, 4FIRST(E)=g,cFOLLOW(A)=#,fFOLLOW(B)=#
3、,a,c,d,f,gFOLLOW(C)=c,d,gFOLLOW(D)=#,a,b,c,g,fFOLLOW(E)=#,a,c,d,f,g5. （15分）设=0 , 1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答：构造相应的正规式：（0|1）*1（0|1）（5分）NFA:（5 分）确定化：（5分）6. （10分）文法GS及其LR分析表如下，请给出对输入串da;aoa#的分析过程。GS:0） S1）S t dSoS2）S t dS3) S t S;S4) S t an ameACTIONGOTOdoa#S0S2S3S311S4acc2
4、S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作10#dbba#移进203#dbba#用V Td归约302#Vbba#移进4024#Vbba#用A t归约50246#VbAba#移进602467#VbAba#移进7024678#VbAba#用A TAba归约80246#VbA#用M tVbA 归约901#M#接受7. （15分）某语言的拓广文法 G为:(0) S tS(1) S t Db|BIo：5 fBD dD B亠 B注右产生式排序为(0) STS(1) StDbStBDtdDt
5、BtBaBt(2) D t d| &(3) B t Ba| 证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。答：拓广文法G,增加产生式 Sts在项目集Io中：有移进项目D d归约项目D t和B存在移进-归约和归约-归约冲突，所以 G不是LR(0)文法。由产生式知Follow(S)=#Follow(D)= bFollow(B)= a ,#在Io中：Follow(D)n d= b n_d=Follow(B)n d= a ,# d= -nFollow(D) n Follow(B)= b n a ,#=在I3中：Follow(S) n a=# n a=所以在Io, I3中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR文法,构造的SLR(1)分析表如下表：状态ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r5
