编译原理复习练习题.docx

1、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： S aSb|Sb|b，对句子 aabbbb 对应的两棵语

2、法树为： 因此，文法 GS为二义文法 5.考虑文法 GS: S (T) | a+S | a T T,S | S 消除文法的左递归及提取公共左因子。 解 ：消除文法 GS的左递归： S (T) | a+S | a T ST T ,ST | 提取公共左因子： S (T) | aS S +S | T ST T ,ST | 6. 文法 GS 为： S-Ac|aB A-ab B-bc 写出 L(GS) 的全部元素。 解 ： S=Ac=abc 或 S=aB=abc 所以 L(GS)=abc 7、 已知 NFA= （ x,y,z,0,1,M,x,z ）， 其中 ：M(x,0)=z,M(y,0)=x,y,M(

3、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 为活跃变量； 否

4、则称 A 在点 p 是不活跃的 ， A 为不活跃变量 。 10. 试为表达式 w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。 解 ： w a b + c d e 10 - / 8 + + * + 11.对文法 GS Sa| |(T) TT,S|S 给出 (a,(a,a)的最左推导。 改写文法， 消除 左递归。 解 ： (a,(a,a)的最左推导 ：略。 消除 左递归 后文法： S a| |(T) T ST T ,ST | 12. 简要说明语义分析的基本功能。 答 ： 按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码 。 13、 编译过程概述和编译

5、程序的结构 答 ： 编译过程概述 ： 一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段 。 另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。 编译程序的结构 ： 词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。 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,

6、S （ 5） T-S LR(0)项目集族及识别活前缀的 DFA 如下图所示： LR(0)分析表 : Action Goto State a （ ） ， # S T 0 S2 S3 S4 1 1 acc 2 R1 R1R1R1R1R1 3 R2 R2R2R2R2R2 4 S2 S3 S4 6 5 5 S7 S8 6 R5 R5R5R5R5R5 7 R3 R3R3R3R3R3 8 S2 S3 S4 9 9 R4 R4R4R4R4R4 15. 写出表达式 (a+b)/(a-b)-(a+b*c)的三 地址码 TAC及四 元式 。 解 ： 三地址码 ( a ) ( S a , S T I0: S -.S

7、 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 四元式 (+,a,b, ) (-,a,b, ) ( ,b,c, ) (+,a, , ) (+, , , ) (-, , , ) 16、 构造下列正规式相应的 DFA： a(a|b)*|ab*a)* b 解 ： 首先构造 NFA 然后 确定化 ， 用矩阵图表示 ： 0

8、 A 1,2,3B 0 1,2,3B 2,3,4,5C 2,3D 0 2,3,4,5C 1,2,3,4,5,6E 2,3,5F 0 2,3D 2,3,4,5C 2,3D 0 1,2,3,4,5,6E 1,2,3,4,5,6E 2,3,5,7G 0 2,3,5F 1,2,3,4,5,6E 2,3,5F 0 2,3,5,7G 1,2,3,4,5,6E 2,3,5F 1 故 DFA 为： 0 1 2 3 a a|b 4 a 5 b 6 a 7 b 17. 简述 DFA 与 NFA 有何区别 ? 答 ： DFA 与 NFA 的区别表现为两个方面 :一是 NFA 可以若干个开始状态，而 DFA 仅只一个开始状态。 另一方面， DFA的映象 M是从 K到 K，而 NFA的映象 M是从 K到 K的子集， 即映象 M 将产生一个状态集合（可能为空集），而不是单个状态。 18.已知文法 GS： SMH|a HLSo| KdML| LeHf MK|bLM 判断 G 是否是 LL（ 1） 文法 ， 如果是 ， 构造 LL（ 1） 分析表。 （这道题目 Follow 集要特别注意为 的情形，特别是 相邻字符连续为 ） 解 ： 所以是 LL（ 1） A B C D E F G a a b a b a b a b a b a b