编译原理复习 (2).doc

《编译原理复习 (2).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.合并LR（1）同心集后有可能产生归约归约冲突对2.一个基本块不能确定一个赋值是否真的有用对3每一个文法都能改写成LL（1）文法错4.编译程序与具体的机器有关，也与具体的语言有关对5.一个语言的文法是唯一的错6.过程与过程调用中，信息交换的方法是全局变量的使用和参数传递对7.在编译程序中，安排中间代码生成的目的是便于代码优化和便于目标程序的移植对8.编译中的语义处理是指两个功能即审查每一个语法结构的静态语义和执行真正的翻译对9.程序基本块是指一组顺序执行的程序段，仅有一个入口和一个出口错10.存在这样的一些语言他们能够被确定的

2、有限自动机识别，但是不能用正规式表示。错二、填空题：11.要在某一台机器上为某一种语言构造一个编译程序，必须掌握机器指令、语言文法、（操作系统）三方面内容。12.设G是一个给定的文法，S是文法开始符号，如果S—>X，那么X是文法G的句子。(X是终结符串）13.在一个典型的编译过程中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等5个部分，还包括出错处理程序和表格处理程序，其中，词法分析器用于识别单词符号，语法分析器用来发现源程序中的语法结构。编译方式与解释方式的根本区别是是否需要整体考虑，递归下降子程序分析法

3、是自上向下的分析法。14.语法分析的任务是识别给定的终结符串是否为给定文法的句子。15.语法分析最常用的两类方法是自上而下和自下而上分析方法，16.在有限自动机中，两个状态等价一致性条件蔓延性条件。17.LR分析法中，每个项目的含义与原点的位置有关，概括的说，原点的左部表示已识别的句柄部分，原点的右部表示期待的后缀部分。18.在构造LR项目集规范族时，新项目集是组成的，合并LR（1）项目集规范族的同心集所产生的冲突一定是归约冲突。19.语法制导翻译比较接近于形式化，它用属性文法工具来表达程序设计语言的语义，每个产生式对应的都给它

4、配上语义动作来进行翻译用。已知文法G[S]：S→MH

5、aH→LSo

6、εK→dML

7、εL→eHfM→K

8、bLM判断G是否是LL(1)文法，如果是，构造LL(1)分析表。答案：文法展开为：0）S→MH1）S→a2）H→LSo3）H→ε4）K→dML5）K→ε6）L→eHf7）M→K8）M→bLM非终结符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,ε}.

9、.....{e,#,o}......对相同左部的产生式可知：SELECT(S→MH)∩SELECT(S→a)={d,b,e，#,o}∩{a}=空SELECT(H→LSo)∩SELECT(H→ε)={e}∩{#,f,o}=空SELECT(K→dML)∩SELECT(K→ε)={d}∩{e,#,o}=空SELECT(M→K)∩SELECT(M→bLM)={d，e,#,o}∩{b}=空所以文法是LL(1)的。预测分析表：aodefb#S→a→MH→MH→MH→MH→MHM→K→K→K→bLM→KH→ε→LSo→ε→εL→eHfK→ε→

10、dML→ε→ε由预测分析表中无多重入口也可判定文法是LL(1)的。题2中当程序编译到r的过程体时的名字表table的内容为：Namekindlevel/valadrsizexvariable0dxyvariable0dx+1pprocedure0过程p的入口（待填）5avariable1dxqprocedure1过程q的入口4sprocedure1过程s的入口（待填）5cvariable2dxdvariable2dxrprocedure2过程r的入口5evariable3dxfvariable3dx+1构造下列正规式相应的DFA

11、.1(0

12、1)　*101(1)先构造NFA：用子集法将NFA确定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:给出下述文法所对应的正规式：S→0A

13、1BA→1S

14、1B→0S

15、0答案：解方程组S的解：S=0A

16、1BA=1S

17、1B=0S

18、0将A、B产生式的右部代入S中S=01S

19、01

20、10S

21、10=（01

22、10）S

23、（01

24、10）所以：S=(01

25、10)*(0

26、1

27、10)证明文法：S→A$A→BaBb

28、DbDaB→εD→ε是LR(1)但不是SLR(1)。(其中'$'相当于'#')答案：文法：A→BaBb

29、DbDaB→εD→ε拓广文法为G′，增加产生式S′→A若产生式排序为：0S'→A1A→BaBb2A→DbDa3B→ε