第 1 页 （共 页） 编译原理 编译原理试题答案及评分参考（A 卷）（课程代号： 9047 ）一、单项选择题一、单项选择题题号题号1 12 23 34 45 56 67 78 89 91010答案答案B BC CA AC CD DC CA AD DB BD D题号题号1111121213131414151516161717181819192020答案答案A AB BB BA AB BD DB BB BD DC C二、多项选则题二、多项选则题题号题号21212222232324242525答案答案ADADABCABCCDECDEABCDEABCDEABCABC三、填空题三、填空题26.开始符号（识别符号） 27.圆括号（） ，方括号，花括号28.单词类别 单词的自身值29.上下文无关30.局部优化 全局优化第 2 页 （共 页）四、计算题。四、计算题。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) 答 1：构造两棵语法树如下： （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+ i*i 有两个不同的最左推导过程，所以文法具有二义性。 （1 分）32. 答：逆波兰式：(abcd-*+)SS+SSS*iiiSS+iiSS*Si第 3 页 （共 页）评分标准 运算符号正确（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 | c 评分标准 文法的四要素齐全（2 分）文法书写正确（1 分）文法含义正确，每个产生式各 1 分35. 答：第 4 页 （共 页） a a a b 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，得到确定化后的状态转换图：0123645第 5 页 （共 页） 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)= wrFOLLOW(B)=wrx，y，z= （2 分）SELECT(Ey) SELECT(E)= yFOLLOW(F)= yx，z=（2 分）SELECT(Fx) SELECT(F)=xFOLLOW(F)= xz=（1 分）012345第 6 页 （共 页）所以该文法是 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 分）ACTIONGOTO状态abc#S第 7 页 （共 页）0S2S311acc2S2S343r3r3r3r34S2S355S2S6S376r1r1r1r17r2r2r2r2（3 分）