资源描述：
《编译原理试题库1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、填空题(共30分，30个空，每空1分)1、典型高级程序设计语言编译系统的工作过程一般分为六个阶段，即词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成C编译阶段的两种组合方式是前后端组合法和按遍组合法,这两种组合方式的主要参考因素都是源语占和目标机器的特征。2、Chomsky将文法按其所表示语言的表达能力，由高往低分为四类：0型，1型，2型,3型文法。其中，2型文法也称上下文无关文法，它的所有规则卩都满足：aevN_,卩丘((VNUVT)*且B长度人于等于a—,仅当卩=£时例外。3、现代编译系统多采用语法制导翻译方法,即在语法分析过程中根据各个规则所相联的语义动作或所
2、对应的语义子程序进行翻译的办法。该方法使用属性文法为工具来说明程序设计语言的语义。4、构造与NFAM等价的正规文法G的方法如下：(1)对转换函数f(A,a)=B或f(A,£)=B,改成形如_A->aB—或A->B—的产生式；(2)对可识别终态乙增加一个产生式:Z—£_o—5.代码生成要考虑的主要问题：充分利用寄存器的问题、选择计算机指令系统的问题、选择计算次序的问题。6、设有穷自动机M=(K,Z,f,S,Z),若当M为NFA吋，满足zOEf(S,a)且z0W乙或当M为DFA时,满足f(S,a)=Pe乙贝【J称符号串aEL*可被M所接受。7、符号表中每一项对应一个多元组。符号表项的组织可分
3、为线性组织、排列组织、散列组织等。8、对于AeVVN定义A的后续符号集：FOLLOW(A)={a
4、S=*>uAp,aeVT,且aeFIRST(P)—,ueVT*,卩WV+；若卩/>w,贝I」#EFOLLOW(A)。也可以定义为：FOLLOW(A)={a
5、S=*>...Aa...,aEVT}0若有S=*>...A,则规定#WFOLLOW(A)。9、基本块的定义：一个基本块是指程序中一个顺疗；执行的语句序列,其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序最后1个语句或转移语句。在基本块范围内的优化称为局部优10、预测分析器由预测分
6、析表、先进后出栈(用来存放分析过程的语法符号)和预测分析程序三部分组成。其中预测分析表是一个二维矩阵，其形式为M[A,a],其-PAeVn，aevT或#。若有产生式At(z,使得aeSELECT(A-xx)_,则将A->a填入M[A,a]中。(书写时，通常省略规则左部，只填一>a)。对所有没有值的M[A,a]标记为出错。二、简述题(共20分，4个小题，每小题5分)1、简述将7FA转换为最小化DFA的步骤。笫一步：将NFA确定化。用造表法将NFA确定化过程如下：(0)表的第0行和第0列作标识行列的值。(1)将s-closure(I)作为表中第1行第1列。(2)假定2>{al,a2,...a
7、n},设第i行第一列已确定状态集为I,则置该行第i列为lai,如lai未曾在任何行第一列出现过，则将lai加入下一空行i+1的第一列，并在笫0列标记为Ti+U(3)反复重复第(1)步，直至无新状态出现为止。(4)重新命名新状态。(3分)第二步：将DFA最小化。DFA最小化具体过程：用子集分割法将不含多余状态的DFA分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。分割时，首先将DFA状态分成终态子集和非终态子集，再根据输出弧所达到状态的性质逐步细分。(2分)2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。(1)静态存储分配的特点
8、：编译时刻确定存储位置；访问效率高。主要用途：子程序的目标代码段、全局数据目标(全局变量)。(2分)（2）栈（Stack）式存储分配的特点：嵌套调用次序、先进后出、生存期限于本次调用、白动释放。用途：过程的局部环境、活动记录。（1分）（3）堆（Heap）式存储分配的特点：将内存空间分为若干块，根据用户要求分配；无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配。主要用途：用于动态数据结构：存储空间的动态分配和释放。（2分）3、以表达式a:=b*（-c）+b/（-d）为例，简述常用的三种中间代码表示形式3、（1）逆波兰式：abc-*bd-/+：=。（1分）（2）三元式：①（-，c
9、,_）②*,b，①）③（-,d,_）④（/,b,③）⑤（+，②，④）⑥（:二，③，a）。（2分）（3）四元式：①（-，c,,tl）②仕，b,tl,t2）③（-，d,,t3）④“,b,t3,t4）©（+,t2,t4,t5）⑥（：=,t5,a）o（2分）o4、简述判别文法G是否为I丄⑴文法的步骤和将一个非LL（1）文法转换为I丄（1）文法的方法。（1）判别步骤：先画出各非终结符能否推导出w的情况表；然后，用定义法或关系图法计算FIRST
