编译原理复习题

填空题 按Chomsky分类法，文法按照_规则定义的形式_进行分类。 词法分析基于_正则_文法进行，即识别的单词是该类文法的句子。 分析句型时，应用算符优先分析技术时，每步被直接归约的是_最左素短语_，而应用LR分析技术时，每步被直接归约的是_句柄_。 扫描器是_词法分析器_，它接受输入的_源程序_，对源程序进行_词法分析_并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有_递归_定义的规则。 语义分析阶段所生成的与源程序等价的中间表示形式可以有_逆波兰_、_四无式表示_与_三元式表示_等。 编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_表格处理_和 _出错处理_。 从功能上说，程序语言的语句大体可分为_执行性_语句和_说明性_语句两大类。 计算机执行用高级语言编写的程序主要有两种途径：_解释_和_编译_。 一个LR分析器包括两部分：一个总控程序和_一张分析表_。 语法分析基于_上下文无关_文法进行，即识别的是该类文法的句子。语法分析的有效工具是_语法树_。 在使用高级语言编程时,首先可通过编译程序发现源程序的全部_语法_错误和语义部分错误。 编译方式与解释方式的根本区别在于_是否生成目标代码_。 递归下降法不允许任一非终极符是直接_左_递归的。 局部优化是在_基本块_范围内进行的一种优化。 一个典型的编译程序中，不仅包括_词法分析_、_语法分析_、_中间代码生成_、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。 语法分析器的输入是_单词符号串_，其输出是_语法单位_。 自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行_直接归约_ ，力求归约到文法的_开始符号_。 产生式是用于定义_语法成分_的一种书写规则。 对编译程序而言,输入数据是_源程序_, 输出结果是_目标程序_。 若源程序是用高级语言编写的,_目标程序_是机器语言程序或汇编程序,则其翻译程序称为 _编译程序_ 。 一个句型中的最左简单短语称为该句型的_句柄_。 语法分析是依据语言的_语法_规则进行的，中间代码产生是依据语言的_语义_规进行的。 自顶向下的语法分析方法的基本思想是：从文法的_开始符号_开始，根据给定的输入串并按照文法的产生式一步一步的向下进行_直接推导_，试图推导出文法的_句子_，使之与给定的输入串_匹配_。 常用的参数传递方式有_传地址_，传值和传名。 对于文法的每个产生式都配备了一组属性的计算规则，称为 _语义规则_ 。 扫描器的任务是从_源程序_中识别出一个个_单词符号_。 一个名字的属性包括_类型_和_作用域_。 语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。 自上而下分析法采用_移进_、归约、错误处理、_接受_等四种操作。一、选择1.将编译程序分成若干个“遍”是为了_B_。A. 提高程序的执行效率B. 使程序的结构更加清晰C. 利用有限的机器内存并提高机器的执行效率D. 利用有限的机器内存但降低了机器的执行效率2.正规式 MI 和 M2 等价是指_C_。A. MI 和 M2 的状态数相等B. Ml 和 M2 的有向弧条数相等。C. M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等3.中间代码生成时所依据的是 _C_。A语法规则 B词法规则 C语义规则 D等价变换规则4.一个编译程序中，不仅包含词法分析，_A_，中间代码生成，代码优化， 目标代码生成等五个部分。A语法分析 B文法分析 C语言分析 D解释分析 5.语法分析器则可以发现源程序中的_D_。A语义错误 B语法和语义错误C错误并校正 D语法错误6.解释程序处理语言时 , 大多数采用的是_B_方法。A源程序命令被逐个直接解释执行B先将源程序转化为中间代码 , 再解释执行C先将源程序解释转化为目标程序 , 再执行D以上方法都可以7.如果L(M1)=L(M2)，则M1与M2( A )A等价 B都是二义的C都是无二义的 D它们的状态数相等8.有限状态自动机能识别( C )A上下文无关文法 B上下文有关文法C正规文法 D短语文法9.由文法的开始符经0步或多步推导产生的文法符号序列是( C )A短语 B句柄 C句型 D句子10.产生正规语言的文法为( D )A0型 B1型 C2型 D3型11.任何算符优先文法( D )优先函数A有一个 B没有 C有若干个 D可能有若干个12.采用自上而下分析，必须( C )A消除左递归 B消除右递归C消除回溯 D提取公共左因子13.在规范归约中，用( B )来刻画可归约串。A直接短语 B句柄 C最左素短语 D素短语14.如果文法是无二义的，那么规范归约是指( B )A最左推导的逆过程 B最右推导的逆过程C规范推导 D最左归约的逆过程15.使用间接三元式表示法的主要目的( A )A便于优化处理 B便于表的修改C节省存储空间 D生成中间代码更容易16.文法 G 所描述的语言是_C_的集合。A. 文法 G 的字母表 V 中所有符号组成的符号串B文法 G 的字母表 V 的闭包 V* 中的所有符号串C由文法的开始符号推出的所有终极符串D. 由文法的开始符号推出的所有符号串17.文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是_B_。 A. 短语文法B正则文法 C上下文有关文法 D上下文无关文法18. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一 组终结符号，一个开始符号，以及一组 _D_。A句子 B句型 C单词 D产生式19.通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目 标代码生成等五个部分，还应包括_C_。A模拟执行器 B解释器C表格处理和出错处理 D符号执行器20.一个句型中的最左_B_称为该句型的句柄。A短语 B简单短语 C素短语 D终结符号21.若一个文法是递归的，则它所产生的语言的句子_A_。A是无穷多个 B. 是有穷多个C是可枚举的 D个数是常量22.词法分析器用于识别_C_。A句子 B句型 C单词 D产生式23.在自底向上的语法分析方法中，分析的关键是_A_。A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 选择候选式24.在 LR 分析法中，分析栈中存放的状态是识别规范句型_C_的 DFA 状态。A. 句柄 B. 前缀 C. 活前缀 D. LR(0) 项目25.若文法 G 定义的语言是无限集，则文法必然是 _A_A递归的 B前后文无关的C二义性的 D无二义性的26.四种形式语言文法中，1 型文法又称为 _A_文法。A短语结构文法 B前后文无关文法C前后文有关文法 D正规文法27._B_和代码优化部分不是每个编译程序都必需的。A语法分析 B中间代码生成C词法分析 D目标代码生成28._B_是两类程序语言处理程序。A高级语言程序和低级语言程序 B解释程序和编译程序C编译程序和操作系统D系统程序和应用程序29.文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 2 型文法是_D_。A. 短语文法 B正则文法C上下文有关文法 D上下文无关文法30._A_是一种典型的解释型语言。ABASIC语言 BC语言 CFORTRAN语言DPASCAL语言 31.与编译系统相比，解释系统_D_。A比较简单 , 可移植性好 , 执行速度快B比较复杂 , 可移植性好 , 执行速度快C比较简单 , 可移植性差 , 执行速度慢D比较简单 , 可移植性好 , 执行速度慢32.用高级语言编写的程序经编译后产生的程序叫_B_。A源程序 B目标程序 C连接程序 D解释程序 33.把汇编语言程序翻译成机器可执行的目标程序的工作是由_A_完成的。A编译器 B汇编器C解释器 D预处理器 34.如果文法 G 是无二义的，则它的任何句子_A_。A最左推导和最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同D可能存在两个不同的最左推导，但它们对应的语法树相同 35.构造编译程序应掌握_D_。A源程序 B目标语言C编译方法 D以上三项都是36.四元式之间的联系是通过_B_实现的。A指示器 B临时变量C符号表 D程序变量37.表达式( A B)(CD)的逆波兰表示为_B_。A. ABCD BA BCDCAB CD DA B CD38.优化可生成_D_的目标代码。A运行时间较短B占用存储空间较小C运行时间短但占用内存空间大 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.在规范归约中，用_B_来刻画可归约串。A直接短语B句柄C最左素短语D素短语44.间接三元式表示法的优点为_A_。A采用间接码表，便于优化处理 B节省存储空间，不便于表的修改C便于优化处理，节省存储空间 D节省存储空间，不便于优化处理45.基本块内的优化为_B_。A. 代码外提，删除归纳变量 B删除多余运算，删除无用赋值C强度削弱，代码外提 D循环展开，循环合并46.在目标代码生成阶段，符号表用_D_。A目标代码生成B语义检查 C语法检查 D地址分配47.堆式动态分配申请和释放存储空间遵守_D_原则。A. 先请先放 B先请后放C后请先放 D. 任意48.文法 G 产生的_ D._ 的全体是该文法描述的语言。A. 句型B. 终结符集C. 非终结符集D. 句子49.一个文法所描述的语言是_A_ A. 唯一的B. 不唯一的C. 可能唯一,D. 可能不唯一50.描述一个语言的文法是_B_ 。A. 唯一的B. 不唯一的C. 可能唯一D. 可能不唯一51.数组的内情向量中肯定不含有数组的_A_的信息A. 维数B. 类型C. 维上下界D. 各维的界差52.两个有穷自动机等价是指它们的 C 。A状态数相等 B有向弧数相等C所识别的语言相等D状态数和有向弧数相等53.设a,b,c为文法的终结符，且有优先关系ab和bc，则 D 。A必有ac B必有ca C必有ba D选项A、B和C都不一定成立54.生成中间代码时所依据的是 C 。A语法规则 B词法规则 C语义规则 D等价变换规则55.基本块 A A只有一个入口语句和一个出口语句 B有一个入口语句和多个出口语句C有多个入口语句和一个出口语句 D有多个入口语句和多个出口语句56.若a为终结符，则A a.ab为_A_A. 移进项目 B. 归约项目 C. 接受项目 D. 后继项目57.同心集的合并不会产生_C_A. 二义冲突 B. 移进/归约冲突C. 移进/移进冲突 D. 归约/归约冲突58.在程序运行前就确定所需的数据空间的存储分配方法是_A_A. 静态的 B. 动态的 C. 栈式的 D. 堆式的59. B 型文法也称为上下文有关文法。A. 0 B. 1 C. 2 D. 360.确定有限自动机的化简是要实现 _A_ 。A. 状态最少化 B. 转换函数确定化C. 符号最少化 D. 边的最少化61.局部优化是对 D 进行的优化。A. 表达式 B. 部分代码 C. 循环体 D. 基本块62.由文法的开始符推导产生的文法符号序列是 C 。A. 短语 B. 句柄 C. 句型 D. 句子63._D_型文法也称为正规文法。A. 0 B. 1 C. 2 D. 364._D_文法不是LL(1)的。A. 递归 B. 右递归 C. 2型 D. 含有公共左因子的65.同心集合并可能会产生的新冲突为 D 。A. 二义 B. 移进/移进 C. 移进/归约 D. 归约/归约66.过程的DISPLAY表记录了 B 。A. 过程的连接数据 B. 过程的嵌套层次C. 过程的返回地址 D. 过程的入口地址67.代码优化时所依据的是 C 。A. 语法规则 B. 词法规则 C. 等价变换规则 D. 语义规则68.编译原理各阶段工作都涉及 B A. 词法分析 B. 表格管理 C. 语法分析 D. 语义分析69.正则表达式R1和R2等价是指 C A. R1和R2都是定义在一个字母表上的正则表达式B. R1和R2中使用的运算符相同C. R1和R2代表同一正则集D. R1和R2代表不同正则集70.在以下的语法分析中， D 特别适合于表达式的分析。A. LR分析B. LL(1)分析C. 递归下降分析D. 算符优先分析71.在语法制导翻译中不采用拉链回填技术的语句是 B 。A. 跳转语句 B. 赋值语句 C. 条件语句 D. 循环语句72.在属性文法中，终结符只具有 D 属性。A. 传递 B. 继承 C. 抽象 D. 综合73.不可能是目标代码的是( D )A汇编指令代码 B可重定位指令代码C绝对指令代码 D中间代码74.词法分析器的输入是( B )A单词符号串 B源程序C语法单位 D目标程序75.词法分析应遵循( C )A语义规则 B语法规则C构词规则 D等价变换规则76.词法分析器的输出结果是( C )A单词的种别编码 B单词在符号表中的位置C单词的种别编码和属性值 D单词属性值 判断题 1“ 用高级语言书写的源程序都必须通过编译, 产生目标代码后才能投入运行 ”这种说法。( )1编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( )22型文法一定是3型文法。 （ ）33型文法一定是2型文法。 ( )4LR 法是自顶向下语法分析方法。 ()5LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 ( ) 6LR 分析技术无法适用二义文法。 ( )7LR 分析器的任务就是产生 LR 分析表。 ( ) 8r 和 s 分别是正规式，则有 L(r|s)=L(r)L(s)。( ) 9编译程序是对高级语言程序的解释执行。( ) 10编译程序与具体的机器有关,与具体的语言无关。 ( ) 12并不是每个文法都能改写成LL(1)文法。 ( )13采用三元式实现三地址代码时，不利于对中间代码进行优化。 ( ）14产生式是定义语法范畴的一种书写规则。()15产生式是用于定义词法成分 的一种书写规则。 ( )16程序语言的语言处理程序是一种应用软件。( ) 17词法分析作为单独的一遍来处理较好。 ( )18从一个句型到另一个句型的推导过程是唯一的。( )19递归下降法不允许任一非终极符是直接左递归的。 () 20递归下降分析法是一种自下而上分析法。 ( )21递归下降分析法是自顶向上分析方法。( )22对任何正规式e，都存在一个DFA M，满足L(M)=L(e)。()23对任意一个右线性正规文法G，都存在一个DFA M，满足L(G)= L(M)。()24对于数据空间的存贮分配， FORTRAN 采用动态贮存分配策略。 ( )25二义文法不是上下文无关文法。( )26分析作为单独的一遍来处理较好。 ( )27符号表中的信息栏中登记了每个名字的 属性和特征等有关信息 ，如类型、种属、所占 单元大小、地址等等。 ( )28归约和规范推导是互逆的两个过程。 ( )29计算机高级语言翻译成低级语言只有解释一种方式。() 30甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系 统功能完全相同。 ( )31简单优先文法允许任意两个产生式具有相同右部。 () 32仅考虑一个基本块，不能确定一个赋值是否真是无用的。 ( )33进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 ()34静态数组的存储空间可以在编译时确定。 ( ) 35两个正规集相等的必要条件是他们对应的正规式等价。 ( )36每个过程的活动记录的体积在编译时可静态确定。 （ ）37每个基本块可用一个DAG表示。 （ ）38每个基本块只有一个入口和一个出口。 ( )39每个文法都能改写为 LL(1) 文法。 () 40目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( )41逆波兰表示法表示表达式时无须使用括号。 ( )42逆波兰法表示的表达式亦称后缀式 。 ( )43逆波兰法表示的表达试亦称前缀式。 ( )44确定的的自动机以及不确定的自动机都能正确地识别正集()45确定有限自动机以及非确定有限自动机都能正确地识别正规集。 ()46如果文法G是无二义的，那么规范归约和规范推导是互逆的两个过程。()47如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 ( )48若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。( )49设R和S分别是字母表上的正规式，则有L(R|S)=L(R)L(S)。 ()50树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。 ( )51数组元素的地址计算与数组的存储方式有关。 ( )52算符优先分析法每次都是对句柄进行归约。 ( )53算符优先关系表不一定存在对应的优先函数。 () 54同心集的合并有可能产生新的“移进”/ “归约” 冲突 ()55文法是描述语言的语法结构的形式规则。()56削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。 ( )57序中的表达式语句在语义翻译时不需要回填技术。 ( ) 58要构造行之有效的自上而下的分析器，则必须消除左递归。( )59一个 LL(l)文法一定是无二义的。 ( ) 60一个句型的句柄一定是文法某产生式的右部。 ( )61一个句型的直接短语是唯一的。 （ ）62一个句型一定句子。 ( )63一个确定有限状态自动机中，有且仅有一个唯一的终态。 ( )64一个上下文无关文法的开始符，可以是终结符或非终结符。( )65一个算符优先文法可能不存在算符优先函数与之对应。 ( )66一个优先表一定存在相应的优先函数。 ( )67一个有限状态自动机中，有且仅有一个唯一的终态。( ) 68一个语义子程序描述了一个文法所对应的翻译工作。 ( )69一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( )70语法分析时必须先消除文法中的左递归 。 ()71在编译中进行语法检查的目的是为了发现程序中所有错误。()72在程序中标识符的出现仅为使用性的。 ( )73在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 ( )74自底而上语法分析方法的主要问题是候选式的选择。 ()75自动机M1和M2的状态数不同，则二者必不等价。 ( )76自上而下分析法是一种“移进归约”法。( )77自下而上的分析法是一种“移进归约”法。()78综合属性是用于 “ 自上而下 ” 传递信息。( )简答题语法分析的主要任务是什么？常分为哪二类方法？答案：任务是在词法分析的基础上将单词序列组合成各类语法短语 .常分为：自顶而下，自底而上二类方法。编译程序大致有哪几种开发技术？答案：（1）自编译（2）交叉编译 （3）自展 （4）移植：编译程序的实现应考虑的问题有那些？答案：编译程序的实现应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护性、可扩充性等。编译过程中可进行的优化如何分类？答案：依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。（1） else 没有匹配的if（2） 数组下标越界（3） 使用的函数没有定义（4） 在数中出现非数字字符答案：（1） 语法分析（2） 语义分析（3） 语法分析（4） 词法分析何谓代码优化？进行优化所需要的基础是什么？答案：对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。何谓翻译程序、编译程序和解释程序？答案：翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。解释程序是解释、执行高级语言源程序的程序。寄存器分配的原则是什么？答案：寄存器分配的原则是：(1) 当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中，直到寄存器不够分配时为止。(2) 当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一个变量名在不同前驱结点的基本块内出口前存放的寄存器可能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中。(3) 对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用效率。什么是语法制导翻译？中间代码通常有哪几种主要形式？答案：由一个源语言、一个目标语言和一组翻译规则组成，遮住规则可将任何源语言符号串翻译成对应的目标语言。主要形式: 三元式、 四元式 、逆波兰式为什么在代码生成时要考虑充分利用寄存器？答案：因为当变量值存在寄存器时，引用的变量值可直接从寄存器中取，减少对内存的存取次数，这样便可提高运行速度。因此如何充分利用寄存器是提高目标代码运行效率的重要途径。计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?答案：计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。像Basic 之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。总而言之，是边翻译边执行。像C，Pascal 之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上看，编译型的高级语言比解释型的高级语言更快。决定目标代码的因素有哪些？答案：决定目标代码的因素主要取决于具体的机器结构、指令格式、字长及寄存器的个数和种类，并与指令的语义和所用操作系统、存储管理等都密切相关。又由于目标代码的执行效率在很大程度上依赖于寄存器的使用，所以目标代码与寄存器的分配算法也有关。一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。最常用的代码优化技术有哪些？答案：1. 删除多余运算2. 代码外提3. 强度削弱4. 变换循环控制条件5. 合并已知量与复写传播6. 删除无用赋值二义文法1. 已知文法 GS: ，证明文法GS为二义文法。2. 已知文法GS：3.设有文法GS: , 证明文法GS为二义文法。4已知文法GP：, 证明文法GP为二义文法。5已知文法GP：, 证明文法GP为二义文法。语言变文法：1. 构造产生语言的上下文无关文法。 2. 构造产生语言的上下文无关文法。 3. 构造产生语言的上下文无关文法。 4. 构造产生语言的上下文无关文法。5. 构造产生语言的上下文无关文法。问题1：给出下述文法所对应的正规式：12.3.4.5：已知文法GA，写出它定义的语言描述GA: 将下面的语句翻译成四元式序列：1. 2.3. 4.5.样题： 对文法GS：SAa|bASBBab(1) 对文法GS，进行改写成每个非终结符不带回溯文法G1S。(2)对文法G1S的每个非终结符求First集合(3)对文法G1S的每个非终结符求Follow集合(4)构造文法G1S 预测分析表。判断文法G1S是否是LL(1) 文法？用A 的产生式右部代替S 的产生式右部的A 得：SSBa|bBab消除左递归后文法变为：0) Sb N1) NB a N2) N3) Ba b(2)(3)非终结符FIRST集FOLLOW集Sb.#Ba.aN,a#(4)Ab#Sb NBa bNB a N(5)预测分析表中无多重入口判定文法是LL(1)的。