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

编译原理作业参考答案编译原理作业参考答案一、填空1 图二 图一。2 文法是无产生式，且任意两个终结符之间至多有一种优先关系的算符文法。3 最右推导 最右推导。4 对于循环中的有些代码，如果它产生的结果在循环中是不变的，就把它提到循环外来。 把程序中执行时间较长的运算替换为执行时间较短的运算。5 对于文法中的每个非终结符A的各个产生式的候选首符集两两不相交； 对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST（A）FOLLOW（A）= 6 控制。7 语义分析和中间代码产生 8 自上而下 自下而上 自上而下 9 自下而上 表达式10 自下而上 11 源程序 单词符号12 DFA初态唯一，NFA初态不唯一；DFA弧标记为上的元素，NFA弧标记为*上的元素； DFA的函数为单射，NFA函数不是单射13词法，词法分析器，子程序，语法14，a，ab，ab15终结符号，非终结符号，产生式16L(G)=an | n1 171型，2型，3型18二义的 19快20终态，输入字21单词符号，终结符22归约 23必须24直接 25终结符，更快 26EE+T， EE+T， EE+T， EE+T27归约归约 28类型检查，一致性检查29词法分析、词法30语法分析程序、语法 31。终结符号、产生式、开始符号、非终结符322、2、3 33不需要避开 34符合、不符合 35推导 36包括37Ass 38一定没有、一定没有、至多只有一个39SLR（1） 40移进归约41a.控制流检查、b.一致性检查、c.相关名字检查二、判断下面语法是否正确1 2 3 4 5 6 三、简答题1词法分析的任务是对输入的源程序进行单词及其属性的识别，为下一步的语法分析进行铺垫；有两种方法可以实现词法分析器：一， 手工编写词法分析程序。二，由词法分析器自动生成程序生成。2 DAG在代码优化中的用途有: 一 如果DAG某内部结点上附有多个标识符，由于计算该结点的表达式是一个公共子表达式，当我们把该结点重新写成中间代码时，就可删除多余运算；二 合并已知量和已知量的运算;三 删除无用的赋值;从而我们可以利用DAG图来重新生成原基本块的一个优化的中间代码序列。四综合1(1) fIf+f*f#gIg*g+g#(2)i*+#f6642g753220 （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最左推导 NNDNDDNDDDDDDD0DDD01DD012D0127最右推导 NND N7ND7N27ND27N127D12701274(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）#EETEEE +TEE E TTFTTFTFF(E)FiTT T *FTT T 5（1） 间接三元式（1）（+，A,B） (2) ( *, (1), C ) (3) (:=, (2), X )(4) (, D, (1) )(5) (:=, (4), Y )(2)逆波兰式a b c + * ; A CD6(1) 文法：EE+T|T TT*F|F F(E)|i证明因为：EE+T TT*FEE+T*F 所以：EE+T*F是文法的一个句型（2）短语： E+T*F T*F句柄： T*F7证明：SA,AAbBSAbB又BcBS,BeBcesSAbces故Abces是文法G的一个句型该句型的短语：e，ces，Abces 素短语：e 句柄：e8四元式序列：OpArg1Arg2Result(0)(1)(2)(3)(4)(5)(6)-*+-/*+CBACET5T3DT1T2DT4NT6T1T2T3T4T5T6T7 A a B A b a B A b c9证明：A=aB =aAb =aaBb =aaAbb =aacbb 短语： acb、 c、 aacbb 句柄： c10解：100（ j , i , 2 , 102 ） 101 (