搜索
-1-XY001最新编译原理复习题和答案一、选择题(1)构造编译程序应掌握。a.源程序b.目标语言c.编译方法d.以上三项都是(2)编译程序绝大多数时间花在上。a.出错处理b.词法分析c.目标代码生成d.表格管理(3)编译程序是对。a.汇编程序的翻译b.高级语言程序的解释执行c.机器语言的执行d.高级语言的翻译(4)词法分析器的输出结果是。a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值(5)正规式M1和M2等价是指。a.M1和M2的状态数相等b.M1和M2的有向边条数相等c.M1和M2所识别的语言集相等d.M1和M2状态数和有向边条数相等(6)DFAM(见图)接受的字集为。a.以0开头的二进制数组成的集合b.以0结尾的二进制数组成的集合c.含奇数个0的二进制数组成的集合d.含偶数个0的二进制数组成的集合(7)文法G：S→xSx|y所识别的语言是。a.xyxb.(xyx)*c.xnyxn(n≥0)d.x*yx*(8)如果文法G是无二义的，则它的任何句子α。a.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导和最右推导必定相同d.可能存在两个不同的最左推导，但它们对应的语法树相同(9)采用自上而下分析，必须。-2-a.消除左递归b.消除右递归c.消除回溯d.提取公共左因子(10)设a、b、c是文法的终结符，且满足优先关系ab和bc，则。a.必有acb.必有cac.必有bad.a～c都不一定成立(11)在规范归约中，用来刻画可归约串。a.直接短语b.句柄c.最左素短语d.素短语(12)若a为终结符，则A→α·aβ为项目。a.归约b.移进c.接受d.待约(13)若项目集Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是。a.LALR文法b.LR(0)文法c.LR(1)文法d.SLR(1)文法(14)同心集合并有可能产生新的冲突。a.归约b.“移进”/“移进”c.“移进”/“归约”d.“归约”/“归约”(15)四元式之间的联系是通过实现的。a.指示器b.临时变量c.符号表d.程序变量(16)间接三元式表示法的优点为。a.采用间接码表，便于优化处理b.节省存储空间，不便于表的修改c.便于优化处理，节省存储空间d.节省存储空间，不便于优化处理(17)表达式(┐A∨B)∧(C∨D)的逆波兰表示为。a.┐AB∨∧CD∨b.A┐B∨CD∨∧c.AB∨┐CD∨∧d.A┐B∨∧CD∨(18)有一语法制导翻译如下所示：S→bAb{print″1″}A→(B{print″2″}A→a{print″3″}B→Aa){print″4″}若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为。a.32224441b.34242421c.12424243d.34442212-3-(19)优化可生成的目标代码。a.运行时间较短b.占用存储空间较小c.运行时间短但占用内存空间大d.运行时间短且占用存储空间小(20)下列优化方法不是针对循环优化进行的。a.强度削弱b.删除归纳变量c.删除多余运算d.代码外提(21)基本块内的优化为。a.代码外提，删除归纳变量b.删除多余运算，删除无用赋值c.强度削弱，代码外提d.循环展开，循环合并(22)在程序流图中，我们称具有下述性质的结点序列为一个循环。a.它们是非连通的且只有一个入口结点b.它们是强连通的但有多个入口结点c.它们是非连通的但有多个入口结点d.它们是强连通的且只有一个入口结点(23)关于必经结点的二元关系，下列叙述中不正确的是。a.满足自反性b.满足传递性c.满足反对称性d.满足对称性(24)过程的DISPLAY表中记录了。a.过程的连接数据b.过程的嵌套层次c.过程的返回地址d.过程的入口地址(25)过程P1调用P2时，连接数据不包含。a.嵌套层次显示表b.老SPc.返回地址d.全局DISPLAY地址(26)堆式动态分配申请和释放存储空间遵守原则。a.先请先放b.先请后放c.后请先放d.任意(27)栈式动态分配与管理在过程返回时应做的工作有。a.保护SPb.恢复SPc.保护TOPd.恢复TOP(28)如果活动记录中没有DISPLAY表，则说明。a.程序中不允许有递归定义的过程b.程序中不允许有嵌套定义的过程c.程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程d.程序中允许有递归定义的过程，也允许有嵌套定义的过程(29)编译程序使用区别标识符的作用域。a.说明标识符的过程或函数名b.说明标识符的过程或函数的静态层次c.说明标识符的过程或函数的动态层次-4-d.标识符的行号(30)在目标代码生成阶段，符号表用于。a.目标代码生成b.语义检查c.语法检查d.地址分配(31)错误的局部化是指。a.把错误理解成局部的错误b.对错误在局部范围内进行纠正c.当发现错误时，跳过错误所在的语法单位继续分析下去d.当发现错误时立即停止编译，待用户改正错误后再继续编译二．应用题1.请画出编译程序的总框图。2.构造单词的状态转换图Goodintbreak1233.构造下述文法的算符优先关系表G[E]:E-E+T|TT-T*F|FF-(E)|i4.令文法G[N]为G[N]:N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G[N]的语言L(G[N])是什么?(2)给出句子0127、34和568的最左推导和最右推导。5.有文法G[S]:S→aAcB|BdA→AaB|cB→bScA|b(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)写出句子acabcbbdcc的最左推导过程。6.对于文法G[S]:S→(L)|aS|aL→L,S|S(1)画出句型(S,(a))的语法树；(2)写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。7.下述文法描述了C语言整数变量的声明语句：G[D]:D→TLT→int|long|shortL→id|L,id(1)改造上述文法，使其接受相同的输入序列，但文法是右递归的；(2)分别用上述文法G[D]和改造后的文法G[D′]为输入序列inta,b,c构造分析树。8.考虑文法G[S]:S→(T)|a+S|aT→T,S|S消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子-5-程序。9.对文法G[E]:E→E+T|TT→T*P|PP→i(1)构造该文法的优先关系表(不考虑语句括号#)，并指出此文法是否为算符优先文法；(2)构造文法G的优先函数。10.设有文法G[S]:S→a|b|(A)A→SdA|S(1)构造算符优先关系表；(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；(3)给出输入串(adb)#的分析过程。11.按照三种基本控制结构文法将下面的语句翻译成四元式序列：while(AC∧BD){if(A≥1)C=C+1;elsewhile(A≤D)A=A+2;}12.对下面四元式代码序列：A=0I=1L1:B=J+1C=B+IA=C+AifI=100gotoL2I=I+1gotoL1L2:writeAhalt(1)画出其控制流程图；(2)求出循环并进行循环的代码外提和强度削弱优化。13.试画出如下中间代码序列的程序流图，并求出：(1)各结点的必经结点集合D(n)；(2)流图中的回边与循环。J=0L1：I=0-6-ifI8gotoL3L2：A=B+CB=D*C14.对于基本块P：S0=2S1=3/S0S2=T-CS3=T+CR=S0/S3H=RS4=3/S1S5=T+CS6=S4/S5H=S6*S2(1)应用DAG对该基本块进行优化；(2)假定只有R、H在基本块出口是活跃的，试写出优化后的四元式序列。答案D,D,D,C,C,D,C,A,C,D,B,B,D,D,B,A,B,B,D,C,B,D,D,B,A,D,B,B,B,D,C