编译原理期末复习

编译原理一、单选题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、 编译程序是对（）。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 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.句柄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.运行时间短但占用内存空间大D.运行时间短且占用内存空间小20、四元式之间的联系是通过（）实现的。BA. 指示器B.临时变量C.符号表D.程序变量二、 多选题1、如果在文法G中存在一个句子，当其满足下列条件（ BCD ）之一时，则称该文法是二义文法。A.其最左推导和最右推导相同B.该句子有两个不同的最左推导C.该句子有两个不同的最右推导D.该句子有两棵不同的语法树E.该句子对应的语法树唯一2、下面（BCD）语法制导翻译中，采用拉链回填技术。A、赋值语句 B、布尔表达式的计算C、条件语句 D、循环语句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、语法分析的常用方法有（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 包括四个组成部分：一组终结符，一组非终结符，以及（BC）。A、一组字符串B、一组产生式C、一个开始符号D、一个文法12、描述一个语言的文法是（C、D）。A、唯一的 B、不唯一的C、可能唯一 D、也可能不唯一13、设有文法GI：II1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（BCD）。 A、ab0B、a0c01 C、aaaD、bc10 14、运行阶段的存储组织与管理的目的是（CD）。A、提高编译程序的运行速度 B、节省编译程序的存储空间 C、提高目标程序的运行速度 D、为运行阶段的存储分配做准备15、已知文法GE：ETEE+TE TFTT*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、函数的动态层次 D、标识符的行号18、词法分析器的输出结果是（AD）A、单词的种别编码B、单词在符号表中的位置C、单词的长度D、单词自身值19、优化可生成（AD）的目标代码。A、运行时间较短 B、占用存储空间较大C、运行时间短且占用内存空间大 D、占用存储空间小22、编译程序各阶段的工作都涉及到（BC ）A、语法分析 B、表格管理 C、出错处理 D、语义分析 F、词法分析三、 填空题1编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_表格处理_和_出错处理_。2若源程序是用高级语言编写的,_目标程序_是机器语言程序或汇编程序,则其翻译程序称为_编译程序_。3编译方式与解释方式的根本区别在于_是否生成目标代码_。4对编译程序而言,输入数据是_源程序_,输出结果是_目标程序_。5产生式是用于定义_语法成分_的一种书写规则。6语法分析最常用的两类方法是_自上而下_和_自下而上_分析法7设G是一个给定的文法，S是文法的开始符号，如果S-x(其中xVT*),则称x是文法的一个_句子_。8递归下降法不允许任一非终极符是直接_左_递归的。9.常用的参数传递方式有_传地址_，传值和传名。10在使用高级语言编程时,首先可通过编译程序发现源程序的全部_语法_错误和语义的部分错误。11一个句型中的最左简单短语称为该句型的_句柄_。12一个典型的编译程序中，不仅包括_词法分析_、_语法分析_、_中间代码生成_、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。13从功能上说，程序语言的语句大体可分为_执行性_语句和_说明性_语句两大类。14语法分析是依据语言的_语法_规则进行的，中间代码产生是依据语言的_语义_规进行的。15产生式是用于定义_语法成分_的一种书写规则。16计算机执行用高级语言编写的程序主要有两种途径：_解释_和_编译_。17局部优化是在_基本块_范围内进行的一种优化。18词法分析基于_正则_文法进行，即识别的单词是该类文法的句子。19语法分析基于_上下文无关_文法进行，即识别的是该类文法的句子。语法分析的有效工具是_语法树_。20一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有_递归_定义的规则。四、名词解释（1）2型文法（上下文无关文法）若文法G=（VN，VT，P，S）中的每一条规则的形式为A，其中AVN，(VNVT)*，则称G是2型文法。（2） 二义性文法如果一个文法存在某个句子对应两课不同的语法树，则称这个文法是二义性文法。（3） 有穷自动机是具有离散输入与输出系统的一种抽象数学模型。（4） 算符文法设有文法G，若G中没有形如UVW的规则，其中V和W为非终结符，则称G为算符文法。（5） 素短语素短语是指这样一种短语，它至少包含一个终结符，并且除自身之外，不再包含其他任何更小的素短语。（6） 语法制导翻译法在语法分析过程中，根据相应文法的每一规则所对应的语义子程序进行翻译的方法。（7） 基本块指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。（8） 句柄一个句型的最左直接短语称为该句型的句柄。（9） 待用信息如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。（10） 局部优化局限于基本块范围的优化称。五、 应用题1. 编译过程的5个阶段是什么？第1阶段：词法分析第2阶段：语法分析第3阶段: 词义分析与中间代码产生第4阶段：代码优化第5阶段：目标代码生成2. 请给出编译程序的结构框图。3. 设有文法GA:Aa|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. 证明下面的文法是二义性的。SiSeS|iS|i5.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？ 目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。 应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指令系统的特点。6.基本的优化方法有哪几种？ 删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。7.构造下列正规式相应的DFA（用状态转换图表示）（1）1（0|1）*1（2）0*10*10*10*1（3）letter(letter|digit)*8.给出下述文法所对应的正规式。SaAAbA|aB|bBaA对应的正规式为：R=a(b|aa)*b解析：9.给出文法GS,构造相应最小的DFASaS|bA|bAaS10.给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0根据正规文法转换成正规式的方法，首先给出该正规文法对应的正规式方程组：S=0A+1B （1）A=1S+1 （2）B=0S+0 （3）将（2）（3）式代入（1）式得S=01S+01+10S+10 （4）对（4）式使用求解规则得S=（01|10）（01|10）*即正规文法所生成语言的正规式是（01|10）（01|10）*。