编译原理复习.docx

编译原理复习一、选择1、构造编译程序应掌握OA.源程序B.目标文件C.编译方法D.以上三项2、编译程序绝大多数时间花在O上A.出错处理B.词法分析C.目标代码生成D.表格管理3、编译程序是对OA.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译4、词法分析器的输出结果是OA.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值D.单词自身值5、正规式Ml和M2等价是指OA.M1和M2的状态数相等B.Ml和M22的有向变条数相等C.M1和M2所识别的语言集相等D.Ml和M2状态数和有向边条数6、DFAM接受的字集为OA.以O开头的二进制数组成的集合B.以O结尾的二进制数组成的集合C.含奇数个O的二进制数组成的集合D.含偶数个O的二进制数组成的集合7、文法GS:S-某S某Iy所识别的语言是OA.某y某B.(某y某)某C.某ny某n(n>0)D.某ny某n8、如果文法GS是无二义的，则它的任何句子Q()A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但它们对应的语法树相同9、采用自顶向下分析，必须OA.消除左递归B.消除右递归C.消除回溯D.提取公共左因子10、设&、b、c是文法的终结符，且满足有限关系a三b和b三c,则OA.必有a三cB.必有c=aC.必有b=aD.ac都不一定成立11、在规范规约中，用O开刻画可归约串A.直接短语B.句柄C.最左素短语D.素短语12、若a为终结符，则AfQaB为()项目A.规约B.移近C.接受D.待约13、若项目集合Ik含有AfQ，则在状态k时，仅当面临的输入符号aFOLLOW（八）时，才采取”动作的一定是OA.LALR文法B.LR(O)文法C.LR(D文法D.SLR(I)文法14、同心集合并有可能产生新的O冲突A.指示器B.临时变量C.符号表D.程序变量16、间接三元式表示法的优点为OA.采用间接码表，便于优化处理B.节省存储空间，不便于表的修改C.便于优化处理，节省存储空间D.节省存储空间，不便于优化处理17、表达式(-1AVB)A(CVD)的逆波兰表示为Oa.-1Abvacdvb.a-1bvcdvc.abv-1cdvd.a11bvcdvi8.过程的DlSPLAY表中记录了O.过程的连接数据B.过程的嵌套层次C.过程的返回地址D.过程的入口地址19、过程Pl调用P2是，连接数据不包含OA.嵌套层次显示表B.老SP值C.返回地址D.全局DISPLAY表地址20、堆式动态分配申请和释放存储空间遵守O原则A.先请先放B.先请后放C.后请先放D.任意21、.栈式动态分配与管理在过程返回时应做的工作有OA.保护SPB.恢复SPC.保护TOPD.恢复ToP22、如果活动记录中没有DISPLAY表，则说明OA.程序中不允许有递归定义的过程B.程序中不允许有嵌套定义的过程C.程序中不允许有嵌套定义的过程，也不允许有递归定义的过程D.程序中允许有递归定义的过程，也允许有嵌套定义的过程23、优化可生成O的目标代码A.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小24、下列O优化方法不是针对循环优化进行的A.强度削弱B.删除归纳变量C.删除多余运算D.代码外提25、基本块内的优化为OA.代码外提，删除归纳变量B.删除多余运算，删除无用赋值C.强度削弱，代码外提D.循环展开，循环合并26、在程序流图中，我们称具有下述性质O的节点序列为一个循环A.它们是非连通的且只有一个入口结点B.它们是强连通的但有多个入口结点C.它们是非连通的但有多个入口结点D.它们是强联通的且只有一个入口结点27、关于必经结点的二元关系，下列叙述中不正确的是OA.满足自反性B.满足传递性C.满足反对称性D.满足对称性28、有一语法制导翻译如下：SfbAbprint“1”Af(Bprint“2”Afaprint“3”B-Aa)print“4，若输入序列为b(aa)a)a)b,且采用自底向上的分析方法，则输出序列为OA.32224441B.34242421C.12424243D.3444221229>错误的局部化是OA.把错误理解成局部的错误B.对错误在局部范围内进行纠结C.当发现错误时，跳过错误所在的语法单位继续分析下去D.当发现错误时立即停止编译，待用户改正错误后再继续编译二、填空1、编译程序划分的类型2、编译程序是对高级语言的翻译一3、若文法是无二义的，则规范推导与规范归纳的关系4、词法分析程序输出的单词符号通常表示成二元式的形式5、语言的目标是，是一个特殊的非终结符6、描述语言L=ab！n>m21的文法为7、程序语言的生成系统是，而识别系统则是8、语法分析器的功能是输入输出9、两个自动机等价是指DFA和NFA10、文法四元组GS=VTVTSW11、词法分析器的输出结果是12、语法分析的方法种类13、文法符号的属性种类14、文法G所描述的语言是的集合15、为使编译程序能正确翻译，对程序设计语言必须使用的定义方法16、LR语法分析法是指扫描输入串和进行规范归纳17、首节点是指从它开始到控制流程图中任何一个结点都有一条通路的结点。18、生成中间代码时所依据的是19、划分基本块的关键问题是准确定义入口和出口语句20、错误的局部化是指当发现错误时，跳过错误所在的语法单位继续分析下去21、基本块是指22、基本块的优化方法，循环优化的方法23、优化可生成的目标代码24、优化对象所涉及的范围，优化的分类25、一个好的编译程序应具有较强的或能力。26、代码优化所遵循的原则是程序的等价变换原则。27、动态语义检查需要生成相应的目标代码，它是在运行时进行的。28、编译生成的目标代码不可能是。29、语法制导翻译。30、编译程序是将源程序成目标程序后再执行。31、中间代码。32、编译模型的最后一个阶段是代码生成。33、在编译程序的全过程中，都需对进行频繁地访问，耗费的时间占很大比例三、简答1.四类文法的关系与区别答：由四类文法的定义可知，从O型文法到3型文法逐渐增加限制。3型文法都属于O型文法，2、3型文法不一定属于1型文法（如果存在形如A-§的产生式，则不属于1型文法），3型文法属于2型文法。四类文法的区别如下：（1）1型文法中不允许有形如“A-§”的产生式存在，而2、3型文法则允许形如“A-§”的产生式存在。（2）0、1型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符，而2型和3型文法的产生式左部只允许是单个的非终结符号。2.中间代码的优化原则答：等价原则：有效原则：合算原则：源程序表格管理目标程序语义分析与中间代码生成器出词法分析器语法分析器错处优化目标代码生成器理3.编译程序的结构（图）4 .解释程序与编译程序的区别答：编译程序是将源程序翻译成目标程序后再执行该目标程序；而解释程序则逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。典型的解释型高级语言是BASIC语言。5.构造编译程序应掌握的内容。答：构造一个编译程序必须掌握下述三方面的内容：对被编译的源语言（如C、PASCAL等），要深刻理解其结构（语法）和含义。必须对目标机器的硬件和指令系统有深刻的了解。必须熟练掌握编译方法，编译方法掌握的如何将直接影响到编译程序的成败，一个好的编译方法可能得到事半功倍的效果。6.编译程序的工作过程。答：编译程序的工作过程是指从输入源程序开始到输出目标程序为止的整个过程。此过程是非常复杂的。一般来说，整个编译过程可以划分成五个阶段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、优化阶段和目标代码生成阶段。7 .堆式存储分配中需解决的问题。答：对于堆式存储分配来说，需要解决两个问题：一是堆空间的分配，即当运行程序需要一块空间时应分配哪一块给它；另一个问题是分配空间的回收，由于返回堆的不同空间是按任意次序进行的，所以需要研究专门的回收分配策略。8 .NFA和DFA的区别。答：NFA和DFA的区别主要有两点：其一是NFA可以有若干个初始状态，而DFA仅有一个初始状态；其二是NFA的状态转换函数f不是单值函数，而是一个多值函数，即f(i,a)=某些状态的集合(iS),它表示不能由当前状态和当前输入字符唯一地确定下一个要转换的状态，也即允许同一个状态对同一个输入字符可以有不同的输出边。四、计算1.文件GS:SfaSlbSla构造LR(O)项目集规范族；给出识别活前缀的DFA；构造SLR(1)分析表，判断是否为SLR(I)文法。2 .表达式(A+B某(C-D)+E(C-D)飞翻译成：逆波兰式、四元式、三元式、间接三元式。3 .程序：I=400J=200LLJ=J+lreadIifI<5000gotoL2writeJhaltL2:I=I某1gotoLl画控制流程图：求各个结点的必经结点集；求回边：求循环。4 .文件GS:Sf(L)IaSIaLfLSIS(I)(S,(a)最右推导,画语法树。(2)该句型中所有的短语，直接短语、句柄和最左素短语。5 .文件GS:S-*S÷aTIaT+aTTf某aT某a(l)aT+a某a某a最右推导，画语法树；(2)该句型中所有的短语、直接短语、句柄和最左素短语。6 .正规表达式(ab)某(aabb)(ab)某，(a；b)某aa,求出等价的简化版DFAM.7 .设有基本块：应用DAG进行优化，画出DAG图；假定变量L,M,N在出口之后是活跃的，写出优化后的四元式序列。