《编译原理》作业参考答案

《《编译原理》作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《编译原理》作业参考答案《编译原理》作业参考答案一、填空1．图二图一。2．文法是无ε产生式，且任意两个终结符之间至多有一种优先关系的算符文法。3．最右推导最右推导。4．对于循环中的有些代码，如果它产生的结果在循环中是不变的，就把它提到循环外来。把程序中执行时间较长的运算替换为执行时间较短的运算。5．对于文法中的每个非终结符A的各个产生式的候选首符集两两不相交；对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST（A）∩FOLLOW（A）=ø6．控制。7．语义分析和中间代码产生8．自上而下自下而上自上而下9．自下而上表达式10．自下而上11．源程序单词符号12．DF

2、A初态唯一，NFA初态不唯一；DFA弧标记为Σ上的元素，NFA弧标记为Σ*上的元素；DFA的函数为单射，NFA函数不是单射13．词法，词法分析器，子程序，语法14．ε，a，ab，ab15．终结符号，非终结符号，产生式16．L(G)={an

3、n≥1}17．1型，2型，3型18．二义的19．快20．终态，输入字21．单词符号，终结符22．归约23．必须24．直接25．终结符，更快26．E→E+∙T，E→E∙+T，E→∙E+T，E→E+T∙27．归约—归约28．类型检查，一致性检查29．词法分析、词法30．语法分析程序、语法31。终结符号、产生式、开始符号、非终结符32．2、2、333

4、．不需要避开34．符合、不符合35．推导36．包括37．Ass第5页共5页《编译原理》作业参考答案38．一定没有、一定没有、至多只有一个39．SLR（1）40．移进——归约41．a.控制流检查、b.一致性检查、c.相关名字检查二、判断下面语法是否正确1×2×3√4×5√6×三、简答题1．词法分析的任务是对输入的源程序进行单词及其属性的识别，为下一步的语法分析进行铺垫；有两种方法可以实现词法分析器：一，手工编写词法分析程序。二，由词法分析器自动生成程序生成。2．DAG在代码优化中的用途有:一如果DAG某内部结点上附有多个标识符，由于计算该结点的表达式是一个公共子表达式，当我们把该结

5、点重新写成中间代码时，就可删除多余运算；二合并已知量和已知量的运算;三删除无用的赋值;从而我们可以利用DAG图来重新生成原基本块的一个优化的中间代码序列。四．综合1．(1)fIf+f*f#gIg*g+g#(2)i*+#f6642g7532第5页共5页《编译原理》作业参考答案2．0（J≥,A,B,2）1（J,__,__,7）2（J=,C,D,0）3（J,__,__,0）4（+,y,z,T1）5（:=,x,T1,_）6（J,__,__,0）73．最左推导N→ND→NDD→NDDD→DDDD→0DDD→01DD→012D→0127最右推导N→ND→N7→ND7→N27→ND27→N12

6、7→D127→01274．(1)FIRST集FIRST(E)={(}FIRST(E’)={+,ε}FIRST(T)={(,i}FIRST(T’)={*,ε}FIRST(F)={(,i,}FOLLOW集FOLLOW(E)={),#}FOLLOW(E’)={),#}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={*,+,),#}(2)预测分析表（+*i）#EE→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’FF→(E)F→iT’T’→εT’→*FT’T’→εT’→ε5．（1）间接三元式（1）（+，A,B）(2)(*,(1),

7、C)(3)(:=,(2),X)第5页共5页《编译原理》作业参考答案(4)(↑,D,(1))(5)(:=,(4),Y)(2)逆波兰式ab@c+*;A┐CD┐∪┐∪6．(1)文法：E→E+T

8、TT→T*F

9、FF→(E)

10、i证明因为：E→E+TT→T*FE→E+T*F所以：E→E+T*F是文法的一个句型（2）短语：E+T*FT*F句柄：T*F7．证明：∵S＝＞A,A＝＞AbB∴S＝＞AbB又∵B＝＞cBS,B＝＞e∴B＝＞ces∴S＝＞Abces故Abces是文法G的一个句型该句型的短语：e，ces，Abces素短语：e句柄：e8．四元式序列：OpArg1Arg2Result(0)(1

11、)(2)(3)(4)(5)(6)-*+-/*+CBACET5T3DT1T2DT4NT6T1T2T3T4T5T6T7第5页共5页《编译原理》作业参考答案AaBAbaBAbc9．证明：A=〉aB=〉aAb=〉aaBb=〉aaAbb=〉aacbb短语：acb、c、aacbb句柄：c10．解：100（j>,i,2,102）101(j,__,__，104)102（+，x，2，T）103（：=，Ｔ　，__，a　）104（+，a，1，T）105（：=，T，__，x）第5页共5页