编译原理复习题(经典)

1编译原理复习题一、是非题1．计算机高级语言翻译成低级语言只有解释一种方式。(×)3．每个文法都能改写为LL(1)文法。(×)4．算符优先关系表不一定存在对应的优先函数。(√)5．LR分析方法是自顶向下语法分析方法。(×)6．“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(×)7．一个句型的句柄一定是文法某产生式的右部。(√)8．仅考虑一个基本块，不能确定一个赋值是否真是无用的。(√)9．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。(×)10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×)11．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(×)12．递归下降分析法是自顶向下分析方法。(√)13．产生式是用于定义词法成分的一种书写规则。(×)14．在SLR(1)分析法的名称中，S的含义是简单的。(√)15．综合属性是用于“自上而下”传递信息。(×)16．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×)17．程序语言的语言处理程序是一种应用软件。(×)18．解释程序适用于COBOL和FORTRAN语言。(×)19．一个LL(l)文法一定是无二义的。(√)20．正规文法产生的语言都可以用上下文无关文法来描述。(√)21．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。(×)22．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(√)22．逆波兰法表示的表达式亦称后缀式。(√)23．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。(√)24．数组元素的地址计算与数组的存储方式有关。(√)25．算符优先关系表不一定存在对应的优先函数。(×)26．编译程序是对高级语言程序的解释执行。(×)27．一个有限状态自动机中，有且仅有一个唯一的终态。(×)28．一个算符优先文法可能不存在算符优先函数与之对应。(√)29．语法分析时必须先消除文法中的左递归。(×)30．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√)31．逆波兰表示法表示表达式时无须使用括号。(√)32．静态数组的存储空间可以在编译时确定。(√)33．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(√)34．两个正规集相等的必要条件是他们对应的正规式等价。(√)35．一个语义子程序描述了一个文法所对应的翻译工作。(×)36．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×)37．确定的自动机以及不确定的自动机都能正确地识别正规集。(√)38．词法分析作为单独的一遍来处理较好。(×)39．构造LR分析器的任务就是产生LR分析表。(√)40．规范归约和规范推导是互逆的两个过程。(√)41．同心集的合并有可能产生新的“移进”/“归约”冲突。(×)42．LR分析技术无法适用二义文法。(×)43．树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。(×)244．程序中的表达式语句在语义翻译时不需要回填技术。(√)45．对中间代码的优化依赖于具体的计算机。(×)46．若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。(×)47．在程序中标识符的出现仅为使用性的。(×)48．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。(×)49．编译程序与具体的机器有关，与具体的语言无关。(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)1．一个编译程序中，不仅包含词法分析，(A)，中间代码生成，代码优化，目标代码生成等五个部分。A．语法分析B．文法分析C．语言分析D．解释分析2．语法分析器则可以发现源程序中的(D)。A．语义错误B．语法和语义错误C．错误并校正D．语法错误3．解释程序处理语言时,大多数采用的是(B)方法。A．源程序命令被逐个直接解释执行B．先将源程序转化为中间代码,再解释执行C．先将源程序解释转化为目标程序,再执行D．以上方法都可以4．编译程序是一种(B)。A．汇编程序B．翻译程序C．解释程序D．目标程序5．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是(B)。A.短语文法B．正则文法C．上下文有关文法D．上下文无关文法6．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括(C)。A．模拟执行器B．解释器C．表格处理和出错处理D．符号执行器7．一个句型中的最左(B)称为该句型的句柄。A．短语B．简单短语C．素短语D．终结符号8．文法G[E]：E→T∣E＋TT→F∣T﹡FF→a∣（E）该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的(B)。①（E＋T）②E＋T③F④F﹡(E＋T)A．①和③B．②和③C．③和④D．③9．词法分析器用于识别(C)。A．句子B．句型C．单词D．产生式10．在自底向上的语法分析方法中，分析的关键是(A)。A．寻找句柄B．寻找句型C．消除递归D．选择候选式11．文法G产生的(D)的全体是该文法描述的语言。A．句型B．终结符集C．非终结符集D．句子12．若文法G定义的语言是无限集，则文法必然是(A)。A．递归的B．前后文无关的C．二义性的D．无二义性的13．四种形式语言文法中，1型文法又称为(C)文法。A．短语结构文法B．前后文无关文法C．前后文有关文法D．正规文法14．一个文法所描述的语言是(A)。A．唯一的B．不唯一的C．可能唯一，好可能不唯一D．都不对15．(B)和代码优化部分不是每个编译程序都必需的。A．语法分析B．中间代码生成C．词法分析D．目标代码生成16．(B)是两类程序语言处理程序。A．高级语言程序和低级语言程序B．解释程序和编译程序3C．编译程序和操作系统D．系统程序和应用程序17．数组的内情向量中肯定不含有数组的(D)的信息。A．维数B．类型C．维上下界D．各维的界差18.一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组(D)。A．句子B．句型C．单词D．产生式19．文法分为四种类型，即0型、1型、2型、3型。其中2型文法是(D)。A．短语文法B．正则文法C．上下文有关文法D．上下文无关文法20．文法G所描述的语言是(C)的集合。A．文法G的字母表V中所有符号组成的符号串B．文法G的字母表V的闭包V*中的所有符号串C．由文法的开始符号推出的所有终极符串D．由文法的开始符号推出的所有符号串21．词法分析器用于识别(C)。A．字符串B．语句C．单词D．标识符22．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是(A)。A．短语文法B．正则文法C．上下文有关文法D．上下文无关文法24．(A)是一种典型的解释型语言。A．BASICB．CC．FORTRAND．PASCAL25．与编译系统相比，解释系统(D)。A．比较简单,可移植性好,执行速度快B．比较复杂,可移植性好,执行速度快C．比较简单,可移植性差,执行速度慢D．比较简单,可移植性好,执行速度慢26．用高级语言编写的程序经编译后产生的程序叫(B)。A．源程序B．目标程序C．连接程序D．解释程序27．词法分析器用于识别(A)。A．字符串B．语句C．单词D．标识符28．编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过(B)这几步:(1)编辑(2)编译(3)连接(4)运行A．(1)(2)(3)(4)B．(1)(2)(3)C．(1)(3)D．(1)(4)29．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。A．编译器B．汇编器C．解释器D．预处理器31．词法分析器的输出结果是(C)。A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身值D．单词自身值32．正规式M1和M2等价是指(C)。A．M1和M2的状态数相等B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等33．文法G：S→xSx|y所识别的语言是(C)。A．xyxB．(xyx)*C．)0(nyxxnnD．x*yx*34．如果文法G是无二义的，则它的任何句子α(A)。A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同35．构造编译程序应掌握(D)。A．源程序B．目标语言C．编译方法D．以上三项都是36．四元式之间的联系是通过(B)实现的。A．指示器B．临时变量C．符号表D．程序变量37．表达式(┐A∨B)∧(C∨D)的逆波兰表示为(B)。A．┐AB∨∧CD∨B．A┐B∨CD∨∧C．AB∨┐CD∨∧D．A┐B∨∧CD∨38.优化可生成(D)的目标代码。A．运行时间较短B．占用存储空间较小4C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小39．下列(C)优化方法不是针对循环优化进行的。A．强度削弱B．删除归纳变量C．删除多余运算D．代码外提40．编译程序使用(B)区别标识符的作用域。A．说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次C．说明标识符的过程或函数的动态层次D．标识符的行号41．编译程序绝大多数时间花在(D)上。A．出错处理B．词法分析C．目标代码生成D．表格管理42．编译程序是对(D)。A．汇编程序的翻译B．高级语言程序的解释执行C．机器语言的执行D．高级语言的翻译43．采用自上而下分析，必须(C)。A．消除左递归B．消除右递归C．消除回溯D．提取公共左因子44．在规范归约中，用(B)来刻画可归约串。A．直接短语B．句柄C．最左素短语D．素短语45．若a为终结符，则A-α·aβ为(B)项目。A．归约B．移进C．接受D．待约46．间接三元式表示法的优点为(A)。A．采用间接码表，便于优化处理B．节省存储空间，不便于表的修改C．便于优化处理，节省存储空间D．节省存储空间，不便于优化处理47．基本块内的优化为(B)。A．代码外提，删除归纳变量B．删除多余运算，删除无用赋值C．强度削弱，代码外提D．循环展开，循环合并48.在目标代码生成阶段，符号表用(D)。A．目标代码生成B．语义检查C．语法检查D．地址分配49．若项目集Ik含有A-α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A-α·”动作的一定是(D)。A．LALR文法B．LR(0)文法C．LR(1)文法D．SLR(1)文法50．堆式动态分配申请和释放存储空间遵守(D)原则。A．先请先放B．先请后放C．后请先放D．任意三、填空题1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和___出错处理__。2．编译方式与解释方式的根本区别在于__是否生成目标代码___。3．产生式是用于定义___语法成分__的一种书写规则。4．设G是一个给定的文法，S是文法的开始符号，如果S-x(其中x∈VT*),则称x是文法的一个__句子___。5．自顶向下的语法分析方法的基本思想是：从文法的__开始符号____开始，根据给定的输入串并按照文法的产生式一步一步的向下进行__直接推导____，试图推导出文法的__句子____，使之与给定的输入串___匹配___。6．常用的参数传递方式有___传地址__，传值和传名。7．一个句型中的最左简单短语称为该句型的___句柄__。8．对于文法的每个产生式都配备了一组属性的计算规则，称为__语义规则___。9．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。10．从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。11．