《编译原理》期末复习题.pdf

《编译原理》期末复习题一、简答题1.DFA和NFA的区别是什么？答：dfa与nfa的区别表现为两个方面:一是nfa可以若干个开始状态，而dfa仅只一个开始状态。另一方面，dfa的映象m是从k×∑到k，而nfa的映象m是从k×∑到k的子集，即映象m将产生一个状态集合（可能为空集），而不是单个状态。2、何谓优化？按所涉及的程序范围可分为哪几级优化？1）优化：对程序进行各种等效转换，以便从转换后的程序开始，生成更有效的目标代码。（2）三个层次：局部优化、循环优化和全局优化。3.短语、简单短语和句柄之间的关系？语法树子树的末端节点符号串既是语法树所描述与对子子树的根的短语；简单子树的标点符号串既是简单短语；最左简单子树的末端符合既是句柄。4、语法分析的任务是什么？输入、输出分别是什么？任务是在词法分析识别出单词符号串的基础上。分析并判定程序的语法结构是否符合语法规则；输入：源程序；输出：单词符号串。5.静态链和动态链分别存储哪些值？为了什么？静态链是指向静态直接外层最新活动记录地址的指针，作用是用来访问非局部数据；动态链是指向调用该过程前的最新活动记录的指针。作用是运行时使运行栈上个数据区按动态建立次序结成链。6.综合属性和继承属性的区别是什么？它的值在语法树中的传递方向是什么？区别：综合属性用于自上而下传递信息，继承属性用于自上而下传递信息。方向：在语法树中，一个节点的综合属性的值由其子节点的综合属性值决定;一个节点的继承属性由此节点的父节点和/或兄弟节点的属性确定的。7.什么是优化？优化效果的两个方面是什么？对程序进行各种等价变换，使得从变化后的程序出发，能生成更有效的目标代码。通称为优化。①、在目标代码生成以前，对语法分析后的中间代码进行的，这类优化不依赖于具体的计算机；②、在目标代码生成时进行的，它在很大程度上依赖于具体的计算机。8、编译程序和解释程序的区别？哪个更通用？区别：编译器是一种程序，其中源语言是高级语言，目标语言是汇编语言或机器语言的低级语言。翻译程序以该语言编写的源程序作为输入，但不生成目标程序，而是在口译时执行源程序本身。编译器更通用。9、什么是算符文法？什么是算符优先文法？一个文法，如果它的任一产生式的右部都不含两个相继的非终结符则称算符文法；而算符优先文法就是在算符文法中加上了优先关系10、静态存储分配和动态存储分配的区别？11.静态链和显示器的用途是什么？两者之间有什么区别？实现非本地名称的访问；静态链是指流程的当前活动记录，指向其直接外层的最新活动记录。显示是指一个指针数组，用于记录当前层和直接外层的最新活动记录。12.堆存储分配的两种管理方法？其中一种有三种内存分配方法。它们是什么？定长块管理和变长块管理。①、首次满足法：只要在空闲块链表中找到满足需要的一块，就进行分配。②、最优满足法：将空闲块中的一个不小于申请块且最接近申请块的与空闲块分配给用户。③、最差满足法：将空闲块表中不小于申请块且是最大的空闲的一部分分配给用一家人13、编译程序的前端与后端的区别？区分前后端的好处是什么？区别：后端不依赖于源语言，而只依赖于中间语言；前端：它与源程序语言有关，与目标代码无关。后端：与目标代码相关。14、写出编译过程的五个阶段？词法分析、语法分析、语义分析和中间代码生成、优化、目标代码优化15。编写标准公式：（1）以01（0/1）01结尾的二进制字符串（2）、能被五整除的十进制整数：（0/1/2/3/4/5/6/7/8/9）(0/5)16、目标代码生成阶段的主要问题是：如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。**二、计算问题1、设文法g(s)：s→(l)|as|al→l，s|s计算每个非终止符的首字母和首字母。解：first（s)＝{(，a}follow(s)＝{#，，，)}first(s')＝{，a,ε}follow(s')＝{#，，，)}first(l)＝{(，a}follow(l)＝{)}first(l')＝{，，ε}follow(l'〕＝{)}2、已知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并最小化它。解：根据题意有nfa图:下表面由儿子集方法将nfa转改变为dfa：将此DFA最小化，如下所示：(1)首先将它的状态集分成两个子集：p1={a,d,e},p2={b,c,f}（2）区分P2：因为f（f，1）=f（C，1）=e，f（f，0）=f和f（C，0）=C，f和C是等价的。因为f（B，0）=f（C，0）=C，f（B，1）=D，f（C，1）=e，D和e是不等价的（参见下一步），B可以与C和f区分开来。有p21