《编译原理》期末复习题.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、静态链和DISPLAY作何⽤途？⼆者的区别是什么？都是为了实现⾮局部名字的访问；静态链是⼀个过程的当前活动记录指向其直接外层的最新活动记录，DISPLAY是引⽤⼀个指针数组来记录现⾏层，直接外层的最新活动记录。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和FOLLOW。解：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={C,