编译原理考点最新爆料哦--.docx

1、1、 编译程序涉及的三个语言 答：源语言 目标语言 实现语言2、 编译程序的概念及其结构(五个)答：编译程序(compiler)是一种翻译程序，它特指把某种高级程序设计语言翻译成具体计算机上的低级程序设计语言。源程序 词法分析 语法分析 语义分析 优化处理 目标代码生成 目标程序3、 什么是二义性文法。答：若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。4、 超前搜索技术答：词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。5、“遍”的概念答：编译程序对源程序或等价程序从头至尾扫描的次数。6、

2、上下文无关文法的定义答：文法是规则的有限集,其中的上下文无关文法可定义为四元组： G(Z)=(VN, VT, Z, P)每个元素：1、 VN : 非终结符集（定义的对象集，如：语法成分等)，它的每个元素是非终结符号。2、 VT : 终结符集（字母表），它的每个元素是终结符号。3、 Z : 开始符号（研究范畴中，最大的定义对象）；4、 P : 规则集（又称产生式集）；每个规则：1、 A - 或者 A - | 2、 其中： 描述符号 ： -(定义为)，|(或者是)3、 文法符号 ： Z,AVN，(VN+VT)*7、词法分析，自上而下以及自下而上语法分析的基本概念，输入，输出，分析方法。答：(1)

3、词法分析是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍。i. 输入：源程序字符串ii. 输出：等价的属性字序列（内部表示形式）iii. 词法分析器又称扫描器，是执行词法分析的程序。任务有二： (1) 识别单词 从用户的源程序中把单词分离出来; (2) 翻译单词 把单词转换成机内表示，便于后续处理。(2) 自上而下语法分析是从文法的开始符号出发，反复使用不同产生式向下推导以谋求与输入符号串相匹配。对任何输入串，试图用一切可能的办法，从文法开始符号(根结)出发，自上而下地为输入串建立一棵语法树。i. 输入符号串指的是由单词符号(文法的终结符)组成的有限序列(3) 自下

4、而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根结。i. 输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列(单词种别，单词符号的属性值)。8、LL(k)的含义，以及LL(1)文法的判定。P73答：判断某给定文法是否为LL(1)文法其条件为： (1)文法不含左递归。 (2)对于文法中每个非终结符A的各个产生式的候选首符集两两不相交。即，若 A a1 | a2 |。| an 则： FIRST(ai) FIRST(aj) =f （i j ) (3) 对文法中每一个终结符A，若它存在某个候选首符集包含e，则 FI

5、RST(A) FLLOW(A)= f 一个文法若满足以上条件，则称该文法G为LL(1)文法.9、LR分析法答：LR(0)分析法SLR(1) 分析法LR分析法 LR(1)分析法LALR(1)分析法10、中间代码生成的依据，形式，目的。P166答：(1) 中间代码的生成方法：属性文法制导翻译语义制导翻译(2) 中间代码的形式：逆波兰式图表示法三元式四元式：最常用的形式(3) 中间代码：不是机器语言，便于生成机器语言，便于代码优化11、四元式p172答：一个四元式是一个带有四个域(field)的记录结构，这四个域分别称为op、arg1、arg2及result。域op包含一个代表运算符的内部码。三地址

6、语句x:=y op z可表示为：将y置于arg1域，z置于arg2域，x置于result域，:=为算符。带有一元运算符的语句如x:= -y或x:= y的表示中不使用arg2。而像param(过程调用)这样的运算符仅适用arg1。条件和无条件转移语句将目标标号置于result域中。通常，四元式中的arg1、arg2和result的内容都是一个指针，此指针指向有关名字的符号表入口。12、栈式存储分配p255 p245答：动态存储分配（1）栈式存储分配运行时，每进入一个过程，就在栈顶为该过程分配一块数据区，一旦退出该过程，它所占的空间也退还给系统。（2）堆式存储分配 栈式存储分配 使用栈式存储分配法

7、意味着把存储组成一个栈，运行时，每当进入一个过程（一个新的活动开始）时， 就把它的活动记录压入栈（累筑于栈顶），从而形成过程工作时的数据区，一个过程的活动记录的体积在编译时是可静态确定的。当该过程结束（过程退出）时，再把它的活动过程弹出栈。这样在栈顶的数据区也随即不复存在。允许过程(函数)递归调用的数据存储管理 1)语言特点：允许过程(函数)的递归调用，但不允许定义嵌套的过程(函数)，也不许使用可变数组。如C语言。2)栈式存储分配：每进入一个过程，就有相应的数据区建立在栈顶。当程序开始运行前，用于建造数据区的栈是空栈。当开始进入主程序执行语句前，便在栈中建立全局变量和主程序数据区。在主程序中若

8、有调用过程的语句时，便在栈顶累筑该过程的活动记录。在进入过程后执行过程的可执行语句前再把局部数组累筑于栈顶，若还有调用过程的语句就重复上述过程。唉，太多了，还是看书吧13、循环优化的具体措施。P287答：主要方法循环不变运算外提（代码外提）降低运算强度（强度削弱）删除归纳变量找出程序中的循环循环语句条件转移和无条件转移构成循环找程序中的循环的方法程序数据流程分析程序控制流程分析是数据流程分析的基础14、翻译程序，编译程序的异同。答： 翻译程序：将一种语言程序转换为另一种语言程序的程序, 按照对象不同分别有： 转换程序 - 把一种高级语言转换成另一种高级语言； 编译程序 - 把某种高级语言转换成

9、某种低级语言; 解释程序 - 把某种高级语言转换成某种低级语言; 汇编程序 - 把汇编语言转换为机器语言的翻译程序。 编译程序(compiler)是一种翻译程序，它特指把某种高级程序设计语言翻译成具体计算机上的低级程序设计语言。解释程序(interpreter)也是一种翻译程序，将某高级语翻译成具体计算机上的低级程序设计语言。 编译程序与解释程序的主要区别: 前者有目标程序而后者无目标程序； 前者运行效率高而后者便于人机对话。15、NFA、DFA的定义，区别，以及转换。DFA的最小化。答：(1) DFA定义：一个确定的有穷自动机（DFA）M是一个五元组： M=（S，s0，F）其中1.S是一个有

10、穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；3. 是转换函数，是在SS上的映射，即，如 （s，a）=s，（sS，sS）就意味着，当前状态为s，输入符为a时，将转换为下一个状态s，我们把s称作s的一个后继状态；4. s0S是唯一的一个初态；5.F S是一个终态集，终态也称可接受状态或结束状态。(2) NFA定义：一个不确定的有穷自动机（NFA）M是一个五元组： M=（S，S0，F）其中1.S是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；3. 是转换函数，是在S*S上的

11、映射，有: S 2S ；4. S0 S是一个非空初态集；5.F S是一个终态集(可空)。(3) 区别：DFANFA开始状态唯一一个或多个映像单个状态状态集合(4) DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的. 算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.DFA的最小化算法（参看P56）构造DFA M的最小状态DFA M，以书上例子来说明该过程。16、逆波兰表达式的求得。答：后缀式(逆波兰式

12、) 后缀式表示法有称逆波兰表示法。这种方法是，把运算量(操作数)写在前面，把算符写在后面(后缀)。 一个表达式的后缀式可以如下定义： (1)如果E是一个变量或常量，则E的后缀式是E自身。 (2)如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为 E1 E2op,这里E1 和E2分别为E1和E2的后缀式。 (3)如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。后缀式 把表达式翻译为后缀式的语义规则： 产生式 语义规则 EE1 op E2 E.code:=E1.code|E2.code|op E (E1) E.code:=E1.code Eid E.code

13、:=id 其他语法成分翻译为后缀式： 产生式 语义规则单目运算“-”： -E E.code|-赋值语句“=”： E=T E.code|T.code|=17、DISPLAY表的概念。P257-259答：18、提高程序运行效率的途径 p273答：对于源程序级，程序员可安排适当的实现语言和选择适当的算法级其次，在设计语义动作时，可以考虑产生更加高效的中间代码，还可以为后面的优化阶段做一些预备工作。对编译产生的中间代码，安排专门的优化阶段，进行各种等价变换，以改进代码的效率。主要优化内容，与计算机硬件无关。对于目标代码级，应该考虑如何有效地利用寄存器，如何选择指令，以及进行窥孔优化等等。19、根据正规

14、式画出转换图（NFA），通过状态转移矩阵把NFA确定化后变成DFA，把DFA最小化。答：（1） NFA到相应的DFA的构造的基本思路 DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态（2） NFA确定化算法(1)假设NFA M=(S,S0,F)按如下办法构造一个DFA M，使得L(M)=L(N)：引进新的初态结点X和终态结点Y，X,Y不属于S，从X到S0中任意状态结点连一条弧，从F中任意状态结点连一条弧到Y。对M的状态转换图进一步施行下图所示的替换，直至状态转换图中每条弧上标记为，或为中的单个字母。 (2)将M进一步变换为DFA，方

15、法如下：假定I是M的状态集的子集，定义I的-闭包_closure(I)为 (a)若qI，则q_closure(I); (b)若qI，那么从q出发经任意条弧而能到达的任何状态q都属于_closure(I)。假定I是M的状态集的子集，a，定义Ia=_closure(J)，其中，J是那些可从I中的某一状态结点出发经过一条a弧而能到达的状态结点的全体。假定=a1,ak。构造一张表，此表的每一行含有k+1列，置表的首行首列为_closure(X)。（3） DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的. 算法

16、假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.唉，太复杂了，还是看书吧20、根据文法推导给定的句型，并会画分析树。答：语法树句型(句子)产生过程的一种树结构表示；树根-开始符号；树叶给定的句型(句子)【语法树的构造算法】 置树根为开始符号； 若采用了推导产生式： A - x1x2xn，则有子树： 重复步骤，直到再没有推导产生式为止 如此构造的语法树，其全体树叶（自左至右）恰好是给定的句型。21、给定文法，学会消除左递归，并提取左公因子从而产生新文法，然后从新文法中构造相应的FIRST集和FOL

17、LOW集。最后学会构造新文法的预测分析表。答：没法写，孩子还是看书把22、对某一语法树找出其短语，直接短语，句柄和素短语。答：关于语法树： 子树 ：以任何具有分支的结点为根所形成的树，称为原树的子树。 简单子树 ：仅具有单层分支的子树。 任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语； 任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语； 一个句型的最左简单短语称为该句型的句柄23、对给定文法，计算其FIRSTVT集和LASTVT集，并学会构造该文法的优先关系矩阵。答：没法写，孩子还是看书把24、画出给定基本块的DAG图，并学会优化。答：太多了，我们还是看书吧25、给定

18、控制语句，翻译成四元式序列。答：对于产生式Swhile E do S1，标号S.begin和E.true分别标记整个语句S的代码的头一条指令和其中的循环体S1的代码的头一条指令。因此，在下面产生式中引入了标记非终结符M，以记录这些位置的四元式标号： Swhile M1 E do M2 S1其中M,其语义动作是把下一条四元式的标号赋给属性M.quad。当while语句中S1的代码执行完毕，控制流转向S的开始处。因此，当归约while M1 E do M2 S1为S时，我们回填表S1.nextlist中所有相应的转移指令的目标标号为M.quad。对于if E then S1 else S2的代码生

19、成，执行完S1的代码后，应跳过S2的代码。因此，在S1的代码之后应有一条无条件转移指令。我们用一个标记非终结符N来生成这条跳转指令，N的产生式为N，它具有属性N.nextlist，链中包含由N的语义动作所产生的跳转指令的标号。修改后文法的翻译模式：(1) Sif E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad); backpatch(E.falselist, M2.quad); S.nextlist:=merge(S1.nextlist, N.nextlist, S2.nextlist)对E为真的四元式(E.truelist所链的

20、四元式)需回填为M1.quad，即S1的第一条四元式的标号。同样，对E为假的四元式需回填S2的第一条语句的标号。链表S.nextlist中包含跳出S1、S2的转移指令和N生成的转移指令。(2) N N.nextlist:=makelist(nextquad); emit(j,-,-,-)(3) M M.quad:=nextquad(4) Sif E then M1 S1 backpatch(E.truelist,M1.quad); S.nextlist:=merge(E.falselist,S1.nextlist)(5) Swhile M1 E do M2 S1 backpatch(S1.nextlist,M1.quad); backpatch(E.truelist,M2.quad); S.nextlist:=E.falselist