编译原理 - a 卷 - 答案

《编译原理 - a 卷 - 答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江工业大学之江学院2011/2012(2)编译原理A卷(答案)班级：姓名：题序12总分计分一、选择题(20*2=40)CBCADABDBACCDCDCDCDA二、问答题1．(5分)给出下图确定化后的DFA。答：2．(5分)写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。答：逆波兰表示：abc*＋ab＋/d－三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)1．(5分)已知文法G(S)S→a

2、∧

3、(T)T→T，S

4、S写出句子((a，a)，a)的规范归约过程及每一步的句柄。答：句型归约规则句柄((a，a)，a)S→aa((S，a)，

5、a)T→SS((T，a)，a)S→aa((T，S)，a)T→T，ST，S((S)，a)T→SS((T)，a)S→S(T)(T)(S，a)T→SS(T，a)S→aa(T，S)T→T，ST，S(T)S→(T)(T)S2．(5分)设文法G(S)：A→BCc

6、gDBB→bCDE

7、εC→DaB

8、caD→dD

9、εE→gAf

10、c计算每个非终结符的FIRST和FOLLOW；答：FIRST(A)={a,b,c,d,g}FIRST(B)={b,ε}FIRST(C)={a,c,d}FIRST(D)={d,ε}FIRST(E)={g,c}FOLLOW(A)={#,f}FOLLOW(B)={#,a,c,d,f,g}

11、FOLLOW(C)={c,d,g}FOLLOW(D)={#,a,b,c,g,f}FOLLOW(E)={#,a,c,d,f,g}1．(15分)设S={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答：构造相应的正规式：(0

12、1)*1(0

13、1)(5分)NFA:(5分)确定化：(5分)2．(10分)文法G[S]及其LR分析表如下，请给出对输入串da;aoa#的分析过程。G[S]:0)S′→S1)S→dSoS2)S→dS3)S→S;S4)S→anameACTIONGOTOdo;a#S0S2S3 S3 11  S4 acc 2S2

14、  S3 53 r4r4 r4 4S2  S3 65 S7S4 r2 6 r3r3 r3 7S2  S3 88 r1S4 r1 答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作12345678900302024024602467024678024601##d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a####移进用V→d归约移进用A→ε归约移进移进用A→Aba归约用M→VbA归约接受1．(15分)某语言的拓广文法G′为：　　(0)S′→S　　(1)S→Db

15、B　　(2)D→d

16、ε　　(3)B→Ba

17、ε证明G不是LR(0)

18、文法而是SLR(1)文法，请给出SLR(1)分析表。答：拓广文法G'，增加产生式S'→S在项目集I0中：有移进项目D→·d归约项目D→·和B→·存在移进-归约和归约-归约冲突，所以G不是LR(0)文法。若产生式排序为：(0)S'→S(1)S→Db(2)S→B(3)D→d(4)D→ε(5)B→Ba(6)B→εG′的LR(0)项目集族及识别活前缀的DFA如下图：由产生式知Follow(S)={#}Follow(D)={b}Follow(B)={a,#}在I0中:Follow(D)∩{d}={b}∩{d}=Follow(B)∩{d}={a,#}∩{d}=Follow(D)∩Follow(B)={

19、b}∩{a,#}=在I3中:Follow(S)∩{a}={#}∩{a}=所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法,构造的SLR(1)分析表如下表：状态ACTIONGOTObda#SDB0r4S4r6r61231   acc   2S5      3  S6r2   4r3      5   r1   6  r5r5