编译原理期末复习

1、编译原理一、单选题1、将编译程序分为若干个“遍”是为了（）。B A. 提高程序的执行效率B. 使程序的结构更加清晰C. 利用有限的机器内存并提高机器的执行效率D. 利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握（）。D A. 源程序 B.目标语言C.编译方法 D.以上三项都是3、变量应当（）。CA. 持有左值 B. 持有右值C. 既持有左值又持有右值D. 既不持有左值也不持有右值4、编译程序绝大多数时间花在（）上。DA. 出错处理 B.词法分析C.目标代码生成 D.管理表格5、（）不可能是目标代码。DA. 汇编指令代码 B.可重定位指令代码C.绝对指令代码 D.中间代码6、 编

2、译程序是对（）。DA. 汇编程序的翻译 B.高级语言程序的解释执行C.机器语言的执行 D.高级语言的翻译7、 正规式M1和M2等价是指（）。CA. M1和M2的状态数相等 B.M1和M2的有象弧条数相等C.M1和M2所识别的语言集相等 D.M1和M2状态数和有象弧条数相等8、 如果文法G是无二义的，则它的任何句子（）。AA. 最左推导和最右推导对应的语法树必定相同。B. 最左推导和最右推导对应的语法树可能相同。C. 最左推导和最右推导必定相同。D. 可能存在两个不同的最左推导，但它们对应的语法树相同。9、 文法G：SS+T|TTT*P|PP(S)|i句型P+T+i的短语有（）BA. i，P+T

3、 B. P，P+T，i，P+T +i B.P+T + i D. P，P+T，i10、 产生正规语言的文法为（）。DA.0型B.1型C.2型D.3型11、 文法G：Sb|(T)TTS|S则FIRSTVT(T)=() CA. b，( B.b，)C.b，(， D.b，)，12、 给定文法：AbA | cc，下面的符号串中，为该文法句子的是（）。 Accbcbcbcbccbccbccbbbcc可选项有：A. B.C.D.13、 采用自上而下分析，必须（）。CA. 消除左递归B.消除右递归C.消除回溯 D.提取公共左因子14、 由文法的开始符经0步或多步推导产生的文法符号序列是（）。CA. 短语B.句柄

4、C.句型D.句子15、 后缀式ab+cd+/可用表达式（）来表示。 BA. a+b/c+d B.(a+b)/(c+d) C.a+b/(c+d) D.a+b+c/d16、 语法分析器则可以发现源程序中的（）。DA. 语义错误B.语法和语义错误C.错误并矫正D.语法错误17、 在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是（）。BA. 非终极符集 B.终极符集 D.字母表 D.状态集18、四种形式语言文法中，1型文法又称为（）。CA. 短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法19、 优化可生成（）的目标代码。DA. 运行时间较短B.占用存储空间较小C.

5、运行时间短但占用内存空间大D.运行时间短且占用内存空间小20、四元式之间的联系是通过（）实现的。BA. 指示器B.临时变量C.符号表D.程序变量2、 多选题1、如果在文法G中存在一个句子，当其满足下列条件（ BCD ）之一时，则称该文法是二义文法。A.其最左推导和最右推导相同  B.该句子有两个不同的最左推导C.该句子有两个不同的最右推导 D.该句子有两棵不同的语法树E.该句子对应的语法树唯一2、下面（BCD）语法制导翻译中，采用拉链回填技术。A、赋值语句    B、布尔表达式的计算 C、条件语句   D

6、、循环语句3、一般程序设计语言的定义都涉及到（ ABC ）3个方面。A、 语法 B、语义 C、语用 D、程序基本符号的确定4、程序语言一般分为（ A ）和（ B ）。A高级语言 B低级语言 C专用程序语言 D通用程序语言5、编译程序工作时，通常有（ABCD ）阶段。A、词法分析 B、语法分析 C、中间代码生成 D、语义检查 E、目标代码生成6、编译过程中，语法分析的任务是（ BCD ）。A、分析单词是怎样构成的   B、分析单词是如何构成语句和说明的C、分析语句和说明是如何构成程序的 D、分析程序的结构

7、7、语法分析的常用方法有 （ AB ）。A、自顶向下 B、自底向上 C、自左向右 D、自右向左   8、程序设计语言常见的数据类型有：（ABCD）  A、数值型数据 B、逻辑数据 C、字符数据 D、指针类型9、构造编译程序应掌握（ABC）。A、源程序 B、目标语言   C、编译方法 D、以上都不是10、编译程序前三个阶段完成的工作是（ABC）A、词法分析 B、语法分析C、语义分析和中间代码生成 D、代码优化11、一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，以及（B

8、C）。A、一组字符串 B、一组产生式 C、一个开始符号 D、一个文法12、描述一个语言的文法是（C、D）。 A、唯一的 B、不唯一的  C、可能唯一 D、也可能不唯一13、设有文法GI：II1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（BCD）。 A、ab0  B、a0c01   C、aaa     D、bc10  14、运行阶段的存储组织与管理的目的是（CD）。A、提高编译程序的运行速度 B、节省编译程序的存储空间 C

9、、提高目标程序的运行速度 D、为运行阶段的存储分配做准备 15、已知文法GE：ETE E+TE  TFT  T*FT  F（E）id 求：FOLLOW（F）=（ D ），FIRST（T）=（ B ）A、*，+ B、*， C、+,#，）D、*，+，#，） E、#，） F、*，+，#，id16、面向机器语言的特点是（ ABC  ）。A、程序的执行效率高 B、编制效率低 C、可读性差 D、可读性强17、编译程序使用（ AB ）区别标识符的作用域。A、说明标识符的过程 B、函数的静态层次C、函数的动态层

10、次 D、标识符的行号18、词法分析器的输出结果是（ AD ） A、单词的种别编码 B、单词在符号表中的位置 C、单词的长度 D、单词自身值19、优化可生成（ AD ）的目标代码。 A、运行时间较短 B、占用存储空间较大 C、运行时间短且占用内存空间大  D、占用存储空间小22、编译程序各阶段的工作都涉及到（ BC ） A、语法分析 B、表格管理 C、出错处理 D、语义分析 F、词法分析3、 填空题1编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代

11、码 生成,代码优化等几个基本阶段,同时还会伴有_表格处理_和 _出错处理_。  2若源程序是用高级语言编写的,_目标程序_是机器语言程序或汇编程序, 则其翻译程序称为 _编译程序_ 。  3编译方式与解释方式的根本区别在于_是否生成目标代码_。  4对编译程序而言,输入数据是_源程序_, 输出结果是_目标程序_。 5产生式是用于定义_语法成分_的一种书写规则。  6语法分析最常用的两类方法是_自上而下_和_自下而上_分析法 7设

12、0;G 是一个给定的文法，S 是文法的开始符号，如果 S->x( 其中 xVT*), 则称 x 是文 法的一个_句子_。 8递归下降法不允许任一非终极符是直接_左_递归的。  9.常用的参数传递方式有_传地址_，传值和传名。  10在使用高级语言编程时,首先可通过编译程序发现源程序的全部_语法_错误和语义的部分错误。 11一个句型中的最左简单短语称为该句型的_句柄_。   12一个典型的编译程序中，不仅包括_词

13、法分析_、_语法分析_、_中间代码生成_、 代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。 13 从功能上说，程序语言的语句大体可分为_执行性_语句和_说明性_语句两大类。   14语法分析是依据语言的_语法_规则进行的，中间代码产生是依据语言的_语义_规 进行的。  15产生式是用于定义_语法成分_的一种书写规则。 16计算机执行用高级语言编写的程序主要有两种途径：_解释_和_编译_。 17局部优化是在_基本块_范围内进行的一种优化。 18词法分析基于_正则

14、_文法进行，即识别的单词是该类文法的句子。  19语法分析基于_上下文无关_文法进行，即识别的是该类文法的句子。语法分析的有效 工具是_语法树_。  20一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有_递归 _定义的规则。 四、名词解释（1）2型文法（上下文无关文法）若文法G=（VN，VT，P，S）中的每一条规则的形式为A，其中AVN，(VNVT)*，则称G是2型文法。（2） 二义性文法如果一个文法存在某个句子对应两课不同的语法树，则称这个文法是二义性文法。（3） 有穷自动机是具有离散输入与输出系统的

15、一种抽象数学模型。（4） 算符文法设有文法G，若G中没有形如UVW的规则，其中V和W为非终结符，则称G为算符文法。（5） 素短语素短语是指这样一种短语，它至少包含一个终结符，并且除自身之外，不再包含其他任何更小的素短语。（6） 语法制导翻译法在语法分析过程中，根据相应文法的每一规则所对应的语义子程序进行翻译的方法。（7） 基本块指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。（8） 句柄一个句型的最左直接短语称为该句型的句柄。（9） 待用信息如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，

16、则称j是四元式i的变量A的待用信息。（10） 局部优化局限于基本块范围的优化称。5、 应用题1. 编译过程的5个阶段是什么？第1阶段：词法分析第2阶段：语法分析第3阶段: 词义分析与中间代码产生第4阶段：代码优化第5阶段：目标代码生成2. 请给出编译程序的结构框图。3. 设有文法GA:A>a|b|e|Aa|Ae|A0|A1（1）试问VT 和VN是由哪些符号组成的？VN=AVT=a,b,e,0,1（2）下列符号串a,ab0,a0e01,0a,11,eee是否为该文法的句子？a,a0e01,eee是该文法句子。4. 证明下面的文法是二义性的。S>iSeS|iS|i5.目标代码有哪几种形

17、式？生成目标代码时通常应考虑哪几个问题？ 目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。  应着重考虑的问题： (1)如何使生成的目标代码较短； (2)如何充分利用寄存器，以减少访问内存次数；  (3)如何充分利用指令系统的特点。6.基本的优化方法有哪几种？ 删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。7.构造下列正规式相应的DFA（用状态转换图表示）（1）1（0|1）*1（2）0*10*10*10*1（3）letter(letter|digit)*8.给出下述文法所对应的正规式。S>aAA>bA|aB|bB&g