编译原理-简答题.doc

名词解释题：

Display表: 嵌套层次显示表
由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display表就是用于登记每个外层过程的最新活动记录起始地址。
LL(1)文法
若文法的任何两个产生式A ® a | b都满足下面两个条件：
（1）FIRST(a ) Ç FIRST(b ) = f；
（2）若b Þ* e ，那么FIRST(a ) Ç FOLLOW( A ) = f。
我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左
向右扫描输入，第二个L表示产生最左推导1代表在决定分析器的每步
动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一
些明显的性质，它不是二义的，也不含左递归。

LR(0)分析器
所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。
编译程序大致有哪几种开发技术？
答案：
（1）自编译（2）交叉编译 （3）自展 （4）移植：
编译程序的工作分为那几个阶段
答：词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端) ，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为
编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。
编译程序的实现应考虑的问题有那些？
答案：
编译程序的实现应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护
性、可扩充性等。
编译程序和高级语言有什么区别?
答：用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器
语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程
的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转
换过的叫目标程序，也就是机器语言。
编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来
将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。
解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，
然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序
止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的"对话"，随时
可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将
级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，
在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。
编译过程中可进行的优化如何分类？
答案：
依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。
词法分析
词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则
从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，
并转换成统一的内部表示(token)，送给语法分析程序。
从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？
答：从优化的范围的角度，优化可以分为局部优化和全局优化两类；
对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强
度削减。
对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、
代码生成）报告的。
（1） else 没有匹配的if
（2） 数组下标越界
（3） 使用的函数没有定义
（4） 在数中出现非数字字符
答案：
（1） 语法分析
（2） 语义分析
（3） 语法分析
（4） 词法分析
何谓代码优化？进行优化所需要的基础是什么？
答案：
对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行
速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。

何谓翻译程序、编译程序和解释程序？
答案：
翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程
序和汇编程序等。
编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编
写的目标程序的翻译程序。
解释程序是解释、执行高级语言源程序的程序。
划分程序的基本块时，确定基本块的入口语句的条件是什么？
答：程序第一个语句，或能由条件转移语句或无条件转移语句转移到的语句，或紧跟在条件转移语句后面的语句。
计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?
答案：
计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。
像Basic 之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。总而言之，是边翻译边执行。
像C，Pascal 之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上看，编译型的高级语言比解释型的高级语言更快。
寄存器分配的原则是什么？
答案：
寄存器分配的原则是：
(1) 当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中，直到寄
存器不够分配时为止。
(2) 当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结
点或多个前驱结点，同一个变量名在不同前驱结点的基本块内出口前存放的寄存器可能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中。
(3) 对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄
存器的利用效率。
简述编译程序的工作过程。
答：编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；④代码优化，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。
简述代码优化的目的和意义。
答：代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。
简述自下而上的分析方法。
所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的
开始符号；或者说从语法树的末端开始步步向上“归约”，直到根节点。
决定目标代码的因素有哪些？
答案：
决定目标代码的因素主要取决于具体的机器结构、指令格式、字长及寄存器的个数和种
类，并与指令的语义和所用操作系统、存储管理等都密切相关。又由于目标代码的执行效率
在很大程度上依赖于寄存器的使用，所以目标代码与寄存器的分配算法也有关。
什么是句柄？什么是素短语？
一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分）
什么是语法制导翻译？中间代码通常有哪几种主要形式？
答案：
由一个源语言、一个目标语言和一组翻译规则组成，遮住规则可将任何源语言符号串翻译成对应的目标语言。
主要形式: 三元式、 四元式 、逆波兰式
为什么在代码生成时要考虑充分利用寄存器？
答案：
因为当变量值存在寄存器时，引用的变量值可直接从寄存器中取，减少对内存的存取次数，这样便可提高运行速度。因此如何充分利用寄存器是提高目标代码运行效率的重要途径。
一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？
答案：
一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语
义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和
错误处理程序。
语法分析的主要任务是什么？常分为哪二类方法
答案：
任务是在词法分析的基础上将单词序列组合成各类语法短语 .
常分为：自顶而下，自底而上二类方法。
运行时的DISPLAY表的内容是什么？它的作用是什么？
答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。
最常用的代码优化技术有哪些？
答案：
1. 删除多余运算
2. 代码外提
3. 强度削弱
4. 变换循环控制条件
5. 合并已知量与复写传播
6. 删除无用赋值