编译原理复习练习题
- 格式：docx
- 大小：2.47 MB
- 文档页数：16
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.已知文法 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 | aT → T,S | S消除文法的左递归及提取公共左因子。
解：消除文法G[S]的左递归：S→(T) | a+S | aT→ST′T′→,ST′| ε提取公共左因子：S→(T) | aS′S′→+S | εT→ST′T′→,ST′| ε6. 文法 G[S] 为：S->Ac|aBA->abB->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’为：（0）S’->S（1）S->a（2）S->∧（3）S->(T)（4）T->T,S（5）T->SLR(0)项目集族及识别活前缀的DFA 如下图所示：LR(0)分析表:15. 写出表达式(a+b)/(a-b)-(a+b*c)的三地址码TAC及四元式。
解：三地址码T1≔a+bT2≔a−bT3≔b×cT4≔a+T3T5≔T1+T2T6≔T5−T4四元式(+,a,b,T1)(-,a,b,T2)(×,b,c,T3)(+,a,T3,T4)(+,T1,T2,T5)(-,T5,T4,T6)16、构造下列正规式相应的DFA：a((a|b)*|ab*a)* b 解：首先构造NFA然后确定化，用矩阵图表示：故DFA为：17. 简述 DFA 与 NFA 有何区别 ?答：DFA 与NFA 的区别表现为两个方面:一是NFA 可以若干个开始状态，而DFA 仅只一个开始状态。
另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集， 即映象M 将产生一个状态集合（可能为空集），而不是单个状态。
18.已知文法G[S]：S →MH|a H →LSo|ε K →dML|ε L →eHf M →K|bLM判断G 是否是LL （1）文法，如果是，构造LL （1）分析表。
（这道题目Follow 集要特别注意为ε的情形，特别是相邻字符连续为ε） 解：所以是LL （1）bb预测分析表如下19. 已知文法 G[S] 为：S→dABA→aA|aB→Bb|εG[S] 产生的语言是什么？解：L(G)={da n b m|n>0, m≥0}20. 已知文法 G[E] 为：E→T|E+T|E-TT→F|T*F|T/FF→（ E ）|i①该文法的开始符号（识别符号）是什么？②请给出该文法的终结符号集合 V T和非终结符号集合 V N。
③找出句型 T+T*F+i 的所有短语、简单短语和句柄。
答：①开始符号是E② V N为{E,T,F}, V T为{(,),i,+,-,*,/}③语有：i, T * F, E+T * F, E + T * F + i直接短语有： i, T * F句柄是：T * F21. 什么是句子？什么是语言 ?答：句子：有文法G，若S∗⇒x，且x∈V T∗，则称x是文法G的句子由文法G生成的语言记为L(G),它是文法G的一切句子的集合：L(G)={x|S ∗⇒x，其中S为文法的开始符号，且x ∈V T∗}22. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。
应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指令系统的的特点。
23. 简述常用的优化技术有哪些？答：删除公共子表示式；复写传播；删除无用代码；代码外提；强度削弱；删除归纳变量；合并常量。
24. 何谓“语法制导翻译”? 语法制导翻译方法的基本思想是什么?答：语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。
由源程序的语法结构所驱动的处理办法就是语法制导翻译法。
25. 常用的中间语言种类有哪几种？答：常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。
26. 已知文法A→aAd|aAb|ε该文法是SLR(1)文法，相应分析表如下，请对输入串ab#给出分析过程。
解：根据上述SLR(1)分析表文法编号应如下：1)A→ε2)A→aAb3)A→aAd移进归约分析过程27. 自底向上分析法的原理是什么？自底向上分析法:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。
一般是对句柄进行归约。
28. 对下面的文法G ：E →TE/E /→+E|εT →FT /T /→T|εF →PF /F /→*F /|ε P →(E)|a|b|^计算这个文法的每个非终结符的FIRST 集和FOLLOW 集。
证明这个方法是LL(1)的。
构造它的预测分析表。
解： 同第8题29. 1(0|1)*101对应的NFA 为请将此NFA 转换为DFA ： 解：故DFA 如下图：30. 1(1010* | 1(010)* 1)* 0对应的NFA为请用子集法将NFA转换为DFA。
解：用矩阵图表示故DFA如下图：31. 什么是编译程序答：编译程序也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。
编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；中间代码生成；代码优化；目标代码生成。
主要是进行词法分析和语法分析，又称为源程序分析，分析过程中发现有语法错误，给出提示信息。
32. 编译过程概述和编译程序的结构答：编译过程概述：一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段。
另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。
编译程序的结构：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。
