资源描述：
《编译原理A答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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=>
2、i+i*i（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
3、=>i+i*i（2分）所以句子i+i*i有两个不同的最左推导过程，所以文法具有二义性。（1分）32.答：逆波兰式：(abcd-*+)[评分标准]运算符号正确（2分）运算顺序正确（2分）三元式序列:(1)-cd（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.答：文
4、法G(S):S®aaSbb
5、aaCbbC®ccB
6、c[评分标准]文法的四要素齐全（2分）文法书写正确（1分）文法含义正确，每个产生式各1分35.答：aa0123645 eeabeebb (2分)确定化：Iab{0,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3}{1,2,4,5,6}{1,2}{1,2,3}{1,2}{1,2,4,5,6}{1,2,3,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,3,5,6}{1,2,4,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,5,6}[评分标准]子集法步骤正确（2分）结果
7、正确（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，得到确定化后的状态转换图：012345bbbaaaaa abbb （2分）六、设计分析题。39.答：因为FIRST(S)={u},FIRST(B)={w,r，ε},FIRST(D)=FIRST(E)={x，y,ε}，FIRST(F)={x,ε}（2分）由S→uBDz得FOLLOW(S)={#}，FOLLOW(D)={z}又由B→wB
8、rB
9、ε得FOLLOW(B)={z}∪FIRST(D
10、){ε}={x，y，z}再由D→EF得FOLLOW(E)=FIRST(F){ε}∪FOLLOW(D)={x，z}FOLLOW(F)=FOLLOW(D)={z}（2分）所以SELECT(B→wB)∩SELECT(B→rB)∩SELECT(B→ε)={w}∩{r}∩FOLLOW(B)={w}∩{r}∩{x，y，z}=Φ（2分）SELECT(E→y))∩SELECT(E→ε)={y}∩FOLLOW(F)={y}∩{x，z}=Φ（2分）SELECT(F→x)∩SELECT(F→ε)={x}∩FOLLOW(F)={x}∩{z}=Φ（1分）所以该文法是LL
11、(1)文法。（1分）40.答：首先拓广文法G为G′[S′]：(0)S′→S,(1)S→aSSb(2)S→aSSS(3)S→c（2分））构造其LR(0)项目集规范族为：I0:S′→•S,S→•aSSbS→•aSSSS→•cI1:S′→S•I2:S→a•SSbS→a•SSSS→•aSSbS→•aSSSS→•cI3:S→c•I4:S→aS•SbS→aS•SSS→•aSSbS→•aSSSS→•cI5:S→aSS•bS→aSS•SS→•aSSbS→•aSSSS→•cI6:S→aSSb•I7:S→aSSS•（3分）只有不存在移进——归约冲突显然该文法是LR(0
12、)文法（2分）状态ACTIONGOTOabc#S0S2S311acc2S2S343r3r3r3r34S2S355S2S6S
