编译原理在线考试考前辅导资料新

1、编译原理在线考试考前辅导资料（新）考试复习所用教材：程序设计语言编译原理，陈火旺、刘春林，国防工业出版社。考试题型及分值介绍： 单项选择题（每题4分，共10题，总分40分）、判断题（每题2分，共10题，总 分20分）、综合题（每题20分，共1题，总分20分）、简答题题（每题10分，共2题，总分20分），满 分100分。考试相关概念、知识点、复习题、例题归纳：编译程序和高级语言。用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过 的汇编语言源文件。编译程序转换过的叫目标程序

2、，也就是机器语言。编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程 序，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器 语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序为止。用 解释型编译程序，执行速度很慢，但可以进行人和计算机的"对话"，随时可以修改高级语言的程序。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过 程中，不能进行人机对话修改。编译方式:先将源程序翻译成汇编语言程序或机器语言程序，然后在执行它。在编译方式

3、中 ，如果目标程序是汇编语言，。那么还需要由另一个称为汇编程序的翻译程序将它进一步翻译成机器语言程序。解释方式：解释方式不是先产生目标程序然后再执行，而且对源程序边翻译边执行。优点是 ：便于对源程序进行调试和修改，但其加工处理过程的速度较慢。例题：运行阶段的存储组织与管理的目的是（ D）。 提高编译程序的运行速度 节省编译程序的存储空间提高目标程序的运行速度为运行阶段的存储分配做准备A.B. C. D.二义性理解二义性，并判断文法是否为二义性的。如果文法G中的某个句子存在不只一棵语法树，则称该句子是二义性的。如果文法含有二义性的句子，则称该文法是二义性的。例已知文法G1:P->PaP|P

4、bP|cP|Pe|f 是二义文法。编译程序包含的步骤：一个典型的编译程序不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。 例题：在编译程序中，语法分析分为自顶向下分析和自底向上分析两类：算符优先分析法和LR分析法属于自底向上分析。中间代码：也叫中间语言：是源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表 示。常见的几种形式：后缀式，图表示法和三地址代码（三元式，四元式，间接三元式）。中间代码 不可能是目标代码。一个可执行程序所使用的存储空间被分为四个区：代码区、数据区、栈区、堆区。LR分析法：“L”是指从左至右扫描输

5、入符号串“R”是指构造一个最右推导的逆过程三元式和四元式的比较 ：相同点： 无论在一个三元式序列还是四元式序列中，各个三元式或四元式都是按相应表达式的实际运算顺序出现的。对同一表达式而言，所需的三元式或四元式的个数一般都是相同的。不同点：由于三元式没有result字段，且不需要临时变量，故三元式比四元式占用的存储空间少；在进行代码优化处理时，需要从现有的运算序列中删去某些运算或挪动一些运算的位置这对三元 式来说是很困难的，但四元式之间的相互联系是通过临时变量来实现的，所以影响就比较小。三元式与间接三元式之间的区别： 由于间接三元式在执行表中已经依次列出每次要执行的那个三元式，若其中有相同的三元

6、式，则仅需在三元式表中保存其中之一，即就是说三元式的项数一般比执行表的项数少；当进行代码优化需要挪动运算顺序时，则只需对执行表进行相应地调整，而不必再改动三元式本身，这样，就避免了 前面讲到的因改变三元式的顺序所引起的麻烦。符号表：编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息， 这些信息通常记录在一张或几张符号表中。符号表的每一项包含两部分：名字（标识符），和此名字的 有关信息。作用：这些信息将用于语义检查，产生中间代码以及最终生成目标代码等不同阶段。编译程序概念及其基本过程？将源程序为高级语言（如 Fortran、Pascal、C等），翻译成目标语言是

7、诸如汇编语言或机器语言之 类的“低级语言”的一个翻译程序成为编译程序。基本过程：词法分析、语法分析、语义分析与中间代码生成、优化、目标代码生成。词法分析器的功能和输出形式。输出的单词符号包括哪几种？功能：输入源程序，输出单词符号。词法分析遵循构词规则种类：关键字、标识符、常数、运算符、界符。例题：词法分析器的输出结果是（单词的种别编码和属性值 ）（初始状态集合）不是DFA的成分。在属性文法中，终结符只具有 综合属性。编译程序绝大多数时间花在表格管理上语法分析器。语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定 程序的语法结构是否符合语法规则。两种分析方法：

8、自上而下分析法、自下而上分析法。例题：编译过程中，语法分析器的任务是（A ）1 .分析单词的构成2 .分析单词串如何构成语句3 .分析语句是如何构成程序4 .分析程序的结构A.B.C.D.理解自顶向下的语法分析方法和自底向上的语法分析方法的区别。它是编译过程中哪个阶段用到的?自顶向下语法分析方法的基本思想是从文法的开始符号开始，根据给定的输入串并按照文法的产生 式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹。自底向上的语法分析方法的基本思想是从给定的输入串（终结符串）开始，根据文法的规则一步一 步的向上进行直接归约，试图归约到文法的开始符号。理解什么是动态存储分配。动

9、态存储分配是指在程序执行的过程中动态地分配或者回收存储空回空也虫存的方法。动态内存 分配不像 数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配,且 分配的大小就是程序要求的大小。掌握LL（1）文法，给出一个文法，判断是否为LL（1）文法，能够计算出非终结符的FIRST集和FOLLOW集，证明它是LL（1）文法，并能够构造它的预测分析表。例题：判断下列文法是否是LL（1）文法？G: Sf aASfdZ bASAr £解： select（S 一 aA）=aselect（S 一d）=dselect（S 一 aA） n select（S 一d）=?select

10、（A 一 bAS）=bselect（A 一 e ）=First（ £ ） - £ U Follow（A）=Follow（A）=a,d,#select（A 一 bAS）C select（A 一 e ）=?所以，该文法是 LL（1）文法。如果文法G是无二义的，则它的任何句子 最左推导和最右推导对应的语法树必定相同。一个LR （1）文法合并同心集后，如果不是LALR（1）文法必定存在 归约-归约冲突。一个 LL（l）文法一定是无二义的。（错误）有穷自动机只有一个初态（错误）包含左递归的文法肯定不能直接用LL分析法来分析。（正确）若文法G定义的语言是无限集，则文法必然是（递归文法）

11、掌握短语、句柄和直接短语短语：就是某个子树的叶子节点的序列。直接短语：就是二级子树的叶子节点的序列句柄：就是最左直接短语。对编译程序而言，输入数据是源程序，输出结果是目标程序。作为编译程序的源语言不能是低级语言。规范归约和规范推导是互逆的两个过程。（ 错误）逆波兰式。逆波兰式（Reverse Polish notation , RPN或逆波兰记法），也叫后缀表达式（将运算符写在操 作数之后）。例如：3* （2- （5+1）,用逆波兰式来表示是：3 2 5 1 + - *,也就是把操作运算符往操作数后面放。DFA与NFA的基本概念及其区别？DFA与NFA定义见课本，区别：DFA与NFA的区别表现

12、为两个方面：一是NFA可以若干个开始状态， 而DFA仅只一个开始状态。另一方面，DFA的映象M是从KX汇到K,而NFA的映象M是从KX汇到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。代码优化代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变 换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间 少。常用的代码优化技术也需要了解一下。例题：含有代码优化功能的编译器的执行效率通常较高。（ 错误）两个正规集相等的必要条件是他们对应的正规式等价。（ 错误 ）综合题：将下面的文法改写为 LL（1）文法。布尔表

13、达式一布尔表达式V布尔因子布尔表达式一布尔因子布尔因子一布尔因子A布尔二次量布尔因子一布尔二次量布尔二次量一布尔初等量布尔二次量一布尔初等量布尔初等量一（布尔表达式）布尔初等量一 true | false答案：为方便书写，记：布尔表达式 > 为A,<布尔因子 > 为B,布尔二次量 > 为C,布尔初等量 > 为D,原文法可以简化为：Z AV B | B B-BAC | C8 n D | DA （A）| true | false,显然，文法含有左递归，消去后等价LL（1）文法为：Z BA'A'一 VBA' | 3 B一 CB ,B'一A

14、 CB | coCHn D|DA （A）| true|false证明下述文法不是 LL(1)文法。 S->C$ C-> bA|aB A->a|aC|bAA B->b|bC| aBB 你能否构造一等价的文法，使其是 LL (1) ?并给出判断过程。答案：因为 SELECT(A->a)nSELECT(A->aC)w，根据LL (1)文法的判定条件： (1)文法不含左递归(2)对于文法U的任意两个不同的规则有：Select(U - a ) n Select(U -b尸一个文法若满足以上条件，称该文法G为LL(1)文法。得出该文法不是LL (1)文法。该文法含公共因

15、子，消除后的文法为： S->C$ C-> bA|aB A->aA'|bAA A' ->C| £ B->bB'| aBB B' ->C| £【证明】因为 SELECT(C-> bA) n SELECT(C->aB)= SELECT(A->Aa) n SELECT(A->bAA)=SELECT(A ->C) ASELECT(A -> e )=(FIRST(C)-£ ) n FOLLOW(A ) w 因此消除公共因子后得到文法也不是LL (1)文法。对于如下的文法 G

16、 S:5- SbS- Ab6- bA- AaZ a(1) 构造一个与 G等价的LL(1)文法G ;(2) 对于G',构造相应的LL(1)分析表。答案：解：(1)消除左递归性，得：Sf bZ11|aZ21A f bZ121az22Z11 -bZ11| £ Z12fbz12Z21fbz111az21Z22 fbz121az22| £消除无用产生式得：SfbZ111az21Z11-bZ11| e Z21fbz111az21此文法已满足LL(1)文法的三个条件，所以G' S:SfbZ111az21Z11-bZ11| e Z21fbz111az21(2) G'

17、文法的各非终结符的FIRST集和FOLLOW:产生式FIRST 集FOLLOWSf bZ11faZ21ba#Z11fbZ11b & #Z21fbz11faZ21ba#LL(1)分析表为:ab#SaZ21bZ11Z11bZ11Z21aZ21bZ11说明属性文法与属性番S译文法有何异同？答案：解：属性文法是文法符号带有语义属性的前后文无关文法；属性翻译文法首先是对文法的属性依赖关系作出限制，不允许出现属性的直接或间接的循环定义，即 要求属性文法是良定义的；其次还应将属性定义规则改造为计算属性值的语义程序，即将静态的定义 规则改写为可动态执行的语义动作；属性文法是静态描述，而属性翻译文法是动

18、态描述，有语义动作。写出一个LEX正规式，它能匹配 C语言的所有无符号整数(例如：OX89ab 0123, 45, ' Z't ' , ' xab' , ' 012',等等)。答案：'(a-zA-Z|Xx0-70-7a-fA-F|0010-70-，)Whilea>0Vbv0 doBeginX： = X+ 1;if a> 0 then a： = a 1else b： = b + 1End;翻译成四元式序列。答案：解：(1) (j >, a, 0, 5)(2) (j ,3)(5) ( + , x, 1, T1)(6)

19、 (: =, T1, , X )(7) (j >, a, 0, 9)(8) (j ,12)(9) (-, a, 1, T2)(10) (: =, T2,a)(11) (J,-,-, 1)(12) (+, b, 1,T3)(13) (: =, T3,b)(14) (J ,1)(15)试证明： 文法Sf ABSH> DCA aAA a8- bBcBf bcg cC8 cA aDbA ab为二义性文法。答案：证明：因为存在句子：abc,它对应有两个最右推导:STABTAbcTabcSTDCTDcTabc所以，本文法具有二义性。一个C语言程序如下:func(i1,i2,i3)long i1

20、,i2,i3;=%o,%o,%on”,&i1,&i2,&i3);=%o,%o,%on”,&J1,&J2,&J3);long j1,j2,j3;printf("Addressesofi1,i2,i3printf("Addressesof J1,J2,J3main()long i1,i2,i3;func(i1,i2,i3);该程序在某种机器的Linux上的运行结果如下:Addressesofi1,i2,i3AddressesofJ1,J2,J3=27777775460,27777775464,27777775470=2777777

21、5444,27777775440,277777754343个局部变量的地址依次降从上面的结果可以看出，func 函数的3个形式参数的地址依次升高，而 低。试说明为什么会有这个区别。答案：由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。设已给文法 G=(VN,VT,P,S),其中：VN=SVT=a1,a2,an, V , A , 1 P=Sfai|i=1,2,n USfS,S- SV S ,Sf SA S ,试指出此文法所产生的语言。答案：此文法产生的语言是：以终结符al 、a2 - an为运算对象，以A、V、为运算符，以、为分隔符的布尔表达式串一个C语言程序如下:int f

22、act(i) int i;if(i=0) return1;else returni*fact(i-1);main() printf("%dn",fact(5);printf("%dn", fact(5,10,15);printf("%dn",fact(5.0);printf("%dn",fact(); 该程序在X86/Linux机器上的运行结果如下： 120 120Segmentation fault请解释下面问题：(core dumped)? 第二个fact? 第三个fact? 第四个fact调用调用调用结果为什

23、么没有受参数过多的影响？为什么用浮点数 5.0作为参数时结果变成1?为什么没有提供参数时会出现Segmentation fault ?答案：(1)参数表达式逆序计算并进栈，fact能够取到第一个参数。(2)参数5.0转换成双精度数进栈，占 8个字节。它低地址的 4个字节看成整数时正好是 0。(3)由于没有提供参数，fact把老ebp (控制链)(main的活动记录中保存的 ebp)当成参数, 它一定是一个很大的整数，使得活动记录栈溢出。设有某程序语言的循环语句的产生式- for i:= downto do其语义是：T1:=;T2:=;i:=T1;L1:if i-T2<0 nbsp="" then="" goto="&