《编译原理A答案.doc》由会员分享，可在线阅读，更多相关《编译原理A答案.doc（7页珍藏版）》请在三一文库上搜索。
1、 编译原理试题答案及评分参考（A卷）（课程代号： 9047 ）一、单项选择题题号12345678910答案BCACDCADBD题号11121314151617181920答案ABBABDBBDC二、多项选则题题号2122232425答案ADABCCDEABCDEABC三、填空题26.开始符号（识别符号） 27.圆括号（），方括号，花括号28.单词类别 单词的自身值29.上下文无关30.局部优化 全局优化四、计算题。31. 答：(1) S= S+S= S+ S*S = S+ S*i= S+ i*i =i+ i*i或S= S*S= S*i = S+S*i= S+ i*i =i+ i*i（2分）(2
2、) 答1：构造两棵语法树如下：SS+iiSS*SiSS+SSS*iii （2分） （2分）所以句子i+ i*i有两棵不同的语法树，所以文法具有二义性。（1分）答2：因为S= S+S= S+ S*S = S+ S*i= S+ i*i =i+ i*i（2分）或S= S*S= S*i = S+S*i= S+ i*i =i+ i*i（2分）所以句子i+ i*i有两个不同的最右推导过程，所以文法具有二义性。（1分）答3：因为S= S+S= S+ S = i+ S= i+S*S =i+S*i=i+ i*i（2分）或S= S*S=S+Si*S = i+S*S=i+i*S =i+ i*i（2分）所以句子i+
3、i*i有两个不同的最左推导过程，所以文法具有二义性。（1分）32. 答：逆波兰式：(abcd-*+)评分标准 运算符号正确（2分）运算顺序正确（2分）三元式序列: (1) - c d （1分） (2) * b (1) （1分） (3) + a (2) （1分）33.答：FIRSTVT(E)=+，*，（），i （2分）LASTVT(E)= +，*，（），i （1分）FIRSTVT(T)= *，（），i（1分）LASTVT(T)= *，（），i（1分）FIRSTVT(F)= （），i （1分）LASTVT(F)= ，i （1分）34. 答：文法G(S):S aaSbb | aaCbbC ccB |
4、 c 评分标准 文法的四要素齐全（2分）文法书写正确（1分）文法含义正确，每个产生式各1分35. 答： a a0123645 e e a b e e b b(2分)确定化：Iab0,1,21,2,31,21,2,31,2,31,2,4,5,61,21,2,31,21,2,4,5,61,2,3,5,61,2,5,61,2,3,5,61,2,3,5,61,2,4,5,61,2,5,61,2,3,5,61,2,5,6 评分标准 子集法步骤正确（2分）结果正确（1分）将0,1,2、1,2,3、1,2、1,2,4,5,6、1,2,3,5,6、1,2,5,6重新命名为状态0，1，2，3，4，5，6，得到确
5、定化后的状态转换图：012345 b b b a a a a a a b b b （2分）六、设计分析题。39.答：因为FIRST(S)=u,FIRST(B)=w,r，, FIRST(D)=FIRST(E)= x，y, ，FIRST(F)= x,（2分）由SuBDz得FOLLOW(S)=# ，FOLLOW(D)=z又由BwB|rB|得FOLLOW(B)=zFIRST(D)=x，y，z再由DEF得FOLLOW(E)= FIRST(F)FOLLOW(D)= x，zFOLLOW(F)= FOLLOW(D)= z（2分）所以SELECT(BwB)SELECT(BrB)SELECT(B)= wrFOLL
6、OW(B)=wrx，y，z= （2分）SELECT(Ey) SELECT(E)= yFOLLOW(F)= yx，z=（2分）SELECT(Fx) SELECT(F)=xFOLLOW(F)= xz=（1分）所以该文法是LL(1)文法。（1分）40.答：首先拓广文法G为GS：(0)SS,(1)SaSSb (2)SaSSS(3)Sc（2分）构造其LR(0)项目集规范族为：I0:SS,SaSSbSaSSSScI1:SSI2:SaSSbSaSSSSaSSbSaSSSScI3:ScI4:SaSSbSaSSSSaSSbSaSSSScI5:SaSSbSaSSSSaSSbSaSSSScI6:SaSSbI7:SaSSS（3分）只有不存在移进归约冲突显然该文法是LR(0)文法（2分）状态ACTIONGOTOabc#S0S2S311acc2S2S343r3r3r3r34S2S355S2S6S376r1r1r1r17r2r2r2r2（3分）