编译原理复习练习题详解.docx

文法 S-a|^|(T) T-T,S|S 对 (a,(a,a))) 和 (((a,a),^,(a)),a) 的最左推导。 解：略。 何谓优化？简述优化的原则是什么？按所涉及的程序范围可分为哪几级优化？ 解： (1)优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。　　　 　　　　　(2) 三种级别：局部优化、循环优化、全局优化。 3.构造正规式 1(0|1)*101 相应的DFA。 4.已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。（以句子aabbbb为例） 解：由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：? 因此，文法G[S]为二义文法 5.考虑文法 G[S]: S → (T) | a+S | a T → T,S | S 消除文法的左递归及提取公共左因子。 解：消除文法G[S]的左递归：?? S→(T)?|?a+S?|?a?? T→ST′?? T′→,ST′|?ε?? 提取公共左因子：?? S→(T)?|?aS′?? S′→+S?|?ε?? T→ST′?? T′→,ST′|?ε 6. 文法 G[S] 为： S-Ac|aB A-ab B-bc 写出 L(G[S]) 的全部元素。 解： S=Ac=abc??或S=aB=abc?? 所以L(G[S])={abc} 7、已知 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-TE 　　 E-+E| ε 　　 T-FT 　　 T -T| ε 　　 F- PF 　　 F- *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.对文法G[S] S?a|∧|(T) T?T,S|S 给出(a,(a,a))的最左推导。改写文法，消除左递归。 解： (a,(a,a))的最左推导：略。 消除左递归后文法： S→a|∧|(T)?? T→ST′?? T′→,ST′|?ε?? 12. 简要说明语义分析的基本功能。 答：按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码。 13、编译过程概述和编译程序的结构 答： 编译过程概述：一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。 编译程序的结构：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。 14. 已知文法为： ??S-a|^|(T) ??T-T,S|S ??构造它的 LR(0)分析表。 （这样的文法是否要先消除左递归？） 不需要 解： 扩展文法G’为： S’-S S-a S-∧ S-(T) T-T,S T-S LR(0)项目集族及识别活前缀的DFA 如下图所示： ( a ) ∧ ( ∧ S a , S T I0: S’-.S S-.a S-.∧ S-.(T) I1: S’-S. S I2: S-a. I4: S-(.T) T-.T,S T-.S S-.a S-.∧ S-.(T) ∧ ( I7: S-(T). I3: S-∧. I6: T-S., I8: T-T, .S S-.a S-.∧ S-.(T) I9: T-T, S. a I5: S-(T.) T-T.,S LR(0)分析表: 　ActionGotoState a ∧ （ ） ， # S T 0 S2 S3 S4 11 acc　2 R1 R1 R1 R1 R1 R1　3 R2 R2 R2 R2 R2 R2　4 S2 S3