编译原理复习.doc

1.合并LR（1）同心集后有可能产生归约归约冲突 对2.一个基本块不能确定一个赋值是否真的有用 对3每一个文法都能改写成LL（1）文法 错4.编译程序与具体的机器有关，也与具体的语言有关 对5.一个语言的文法是唯一的 错6.过程与过程调用中，信息交换的方法是全局变量的使用和参数传递 对7.在编译程序中，安排中间代码生成的目的是便于代码优化和便于目标程序的移植 对8.编译中的语义处理是指两个功能即审查每一个语法结构的静态语义和执行真正的翻译 对9.程序基本块是指一组顺序执行的程序段，仅有一个入口和一个出口 错10.存在这样的一些语言他们能够被确定的有限自动机识别，但是不能用正规式表示。 错二、填空题：11. 要在某一台机器上为某一种语言构造一个编译程序，必须掌握 机器指令 、 语言文法 、 （操作系统） 三方面内容。12. 设G是一个给定的文法，S是文法开始符号，如果SX，那么X是文法G的 句子 。(X是终结符串）13. 在一个典型的编译过程中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等5个部分，还包括 出错处理程序 和表格处理程序 ，其中，词法分析器用于识别 单词符号 ，语法分析器用来发现源程序中的 语法结构 。编译方式与解释方式的根本区别是 是否需要整体考虑 ，递归下降子程序分析法是 自上向下的 分析法。14. 语法分析的任务是识别给定的终结符串是否为给定文法的 句子 。15. 语法分析最常用的两类方法是 自上而下 和 自下而上 分析方法，16. 在有限自动机中，两个状态等价 一致性条件 蔓延性条件 。17. LR分析法中，每个项目的含义与原点的位置有关，概括的说，原点的左部表示 已识别的句柄部分 ，原点的右部表示 期待的后缀部分 。18. 在构造LR项目集规范族时，新项目集是 组成的，合并LR（1）项目集规范族的同心集所产生的冲突一定是 归约 冲突。19. 语法制导翻译比较接近于形式化，它用 属性文法 工具来表达程序设计语言的语义，每个产生式对应的都给它配上 语义动作 来进行翻译用。已知文法GS：SMH|aHLSo|KdML|LeHfMK|bLM判断G 是否是LL(1)文法，如果是，构造LL(1)分析表。答案：文法展开为：0） SM H1） Sa2） HL S o3） H4） Kd M L5） K6） Le H f7） MK8） Mb L M非终结符 FIRST 集 FOLLOW 集S a,d,b,e #,o.M d,b. e,#,o.H ,e. #,f,o.L e.a,d,b,e,o,#K d,. e,#,o.对相同左部的产生式可知：SELECT(SM H)SELECT(Sa) = d,b ,e，#,o a =空SELECT(HL S o)SELECT(H) = e #,f,o =空SELECT(Kd M L)SELECT(K) = d e,#,o =空SELECT(MK)SELECT(Mb L M) = d，e,#,o b =空所以文法是LL(1)的。预测分析表：a o d e f b #S a MH MH MH MH MHM K K K bLM KH LSo L eHfK dML 由预测分析表中无多重入口也可判定文法是LL(1)的。题 2 中当程序编译到r 的过程体时的名字表table 的内容为：Name kind level/val adr sizex variable 0 dxy variable 0 dx+1p procedure 0 过程p 的入口（待填） 5a variable 1 dxq procedure 1 过程q 的入口 4s procedure 1 过程s 的入口（待填） 5c variable 2 dxd variable 2 dxr procedure 2 过程r 的入口 5e variable 3 dxf variable 3 dx+1构造下列正规式相应的DFA.1(0|1)*101 (1) 先构造NFA：用子集法将NFA 确定化. 0 1X . AA A ABAB AC ABAC A ABYABY AC AB除X，A 外，重新命名其他状态，令AB 为B、AC 为C、ABY 为D，因为D 含有Y（NFA的终态），所以D 为终态。. 0 1X . AA A BB C BC A DD C BDFA 的状态图：:给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0答案：解方程组S 的解：S=0A|1BA=1S|1B=0S|0将A、B 产生式的右部代入S 中S=01S|01|10S|10=（01|10）S|（01|10）所以：S= (01|10)*(01|10)证明文法：SA$ABaBb|DbDaBD是LR(1)但不是SLR(1)。(其中$相当于#)答案：文法：ABaBb|DbDaBD拓广文法为G，增加产生式SA若产生式排序为：0 SA1 A BaBb2 A DbDa3 B 4 D 由产生式知：First (S ) = a,bFirst (A ) = a,bFirst (B ) = First (D ) = Follow(S ) = #Follow(A ) = #Follow(B ) = a,bFollow(D ) = a,bG的LR(1)项目集族及识别活前缀的DFA 如下图所示：在I0 中：B .,a 和T .，b 为归约项目，但它们的搜索符不同，若当前输入符为a 时用产生式B归约，为b 时用产生式D 归约，所以该文法是LR(1)文法。若不看搜索符，在I0 中项目B .和T .为归约-归约冲突，而Follow(B ) Follow(D ) = a,b a,b ，冲突不能用Follow 集解决，所以该文法不是SLR(1)文法。给出下面表达式的逆波兰表示(后缀式)：if(x+y)*z=0 then s=(a+b)*c else s=a*b*c答案：xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else 运算）如果写成这样： xy+z*0=sab+c*:=sabc*:=￥，则是错误的，因为写表达式和赋值语句的中间代码序列，或是写它们的代码生成过程，必须注意按照算符优先序进行，这实际上是按照LR 分析过程进行的。例如：写出赋值语句a:=a+b*c*(d+e)的四元式中间代码,当前四元式序号为100。不能写成：100 (+,d,e,t1)