编译原理复习练习题

1. 文法 S-a|(T) T-T,S|S 对 (a,(a,a) 和 (a,a),(a),a) 的最左推导。解：略。2. 何谓优化？简述优化的原则是什么？按所涉及的程序范围可分为哪几级优化？解：(1)优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。(2) 三种级别：局部优化、循环优化、全局优化。3.构造正规式 1(0|1) *101 相应的 DFA。4.已知文法 GS 为 S aSb|Sb|b ，试证明文法 GS 为二义文法。（以句子 aabbbb为例）解：由文法 GS：SaSb|Sb|b，对句子 aabbbb 对应的两棵语法树为： 因此，文法 GS为二义文法5.考虑文法 GS:S (T) | a+S | a T T,S | S 消除文法的左递归及提取公共左因子。解：消除文法 GS的左递归： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 6. 文法 GS 为： S-Ac|aB A-ab B-bc 写出 L(GS) 的全部元素。解：S=Ac=abc 或 S=aB=abc 所以 L(GS)=abc7、已知 NFA= （ x,y,z,0,1,M,x,z ），其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)= ,M(z,1)=y, 构造相应的 DFA 并最小化。最小化：8、对下面的文法 G ： E-TEE-+E| T-FTT -T| F- PFF- *F| P-(E)|a|b| (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。(2) 证明这个方法是 LL(1) 的。(3) 构造它的预测分析表。解：9. 什么是非活跃变量？什么是活跃变量？答：对程序中的某变量 A 和某点 p 而言，如果存在一条从 p 开始的通路，其中引用了 A 在点 p 的值，则称 A 在点 p 是活跃的，则 A 为活跃变量；否则称 A 在点 p 是不活跃的，A 为不活跃变量。10. 试为表达式 w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。解：w a b + c d e 10 - / 8 + + * +11.对文法 GSSa|(T)TT,S|S给出(a,(a,a)的最左推导。改写文法，消除左递归。解：(a,(a,a)的最左推导：略。消除左递归后文法：Sa|(T) TST T,ST| 12. 简要说明语义分析的基本功能。答：按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码。13、编译过程概述和编译程序的结构答：编译过程概述：一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译程序的结构：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。14. 已知文法为： S-a|(T) T-T,S|S 构造它的 LR(0)分析表。（这样的文法是否要先消除左递归？） 不需要解：扩展文法 G为：（0） S-S（1） S-a（2） S-（3） S-(T)（4） T-T,S（5） T-SLR(0)项目集族及识别活前缀的 DFA 如下图所示：LR(0)分析表:Action GotoState a （ ） ， # S T 0 S2 S3 S4 11 acc 2 R1 R1R1R1R1R1 3 R2 R2R2R2R2R2 4 S2 S3 S4 6 55 S7 S8 6 R5 R5R5R5R5R5 7 R3 R3R3R3R3R3 8 S2 S3 S4 99 R4 R4R4R4R4R4 15. 写出表达式(a+b)/(a-b)-(a+b*c)的三地址码 TAC 及四元式。解：(a)(Sa,STI0:S-.SS-.aS-.S-.(T)I1:S-S.SI2:S-a.I4:S-(.T)T-.T,ST-.SS-.aS-.S-.(T)(I7:S-(T).I3:S-.I6:T-S.,I8:T-T,.SS-.aS-.S-.(T)I9:T-T,S.aI5:S-(T.)T-T.,S三地址码 1+234+351+2654四元式(+,a,b, )1(-,a,b, )2( ,b,c, ) 3(+,a, , )34(+, , , )125(-, , , )54616、构造下列正规式相应的 DFA：a(a|b) *|ab*a)* b解：首先构造 NFA0 1 2 3aa|b 4a5b6a7b然后确定化，用矩阵图表示： 0 A 1,2,3B 01,2,3B 2,3,4,5C 2,3D 02,3,4,5C 1,2,3,4,5,6E 2,3,5F 02,3D 2,3,4,5C 2,3D 01,2,3,4,5,6E 1,2,3,4,5,6E 2,3,5,7G 02,3,5F 1,2,3,4,5,6E 2,3,5F 02,3,5,7G 1,2,3,4,5,6E 2,3,5F 1故 DFA 为：A B C DE FGa aba baba ba bab17. 简述 DFA 与 NFA 有何区别 ?答：DFA 与 NFA 的区别表现为两个方面:一是 NFA 可以若干个开始状态，而 DFA 仅只一个开始状态。 另一方面，DFA 的映象 M 是从 K到 K，而 NFA 的映象 M 是从 K到 K 的子集，即映象 M 将产生一个状态集合（可能为空集），而不是单