德州学院编译原理期末复习题

编译原理一、单选题1.LL(1)分析法的名字中，第一个“L”的含义是（）A.从左向右分析输入串B.使用最左推导C.分析表是二维的D.每次向前看1个符号答案：A2.有限自动机可以识别（）A.上下文无关语言B.上下文有关语言C.正则语言D.0型语言答案：C3.目标代码生成阶段的任务是（）A.生成抽象语法树B.生成中间代码C.生成可在目标机器上运行的代码D.生成符号表答案：C4.将表达式x=y*0优化为x=0，属于（）A.常数折叠B.删除公共子表达式C.删除无用代码D.强度削弱答案：A5.在目标代码生成中，指令选择的目的是（）A.为三地址语句序列选择合适的目标机器指令B.为变量分配寄存器C.决定指令的执行顺序D.优化指令序列答案：A6.L-属性定义是一种受限制的语法制导定义，它要求每个继承属性只依赖于其（）的文法符号的属性。A.左边或上方B.右边或下方C.左边和右边D.产生式内部答案：A7.一个确定的有限自动机（DFA）中，从任一状态出发，对任一输入符号，最多有（）个转移。A.0B.1C.2D.任意多答案：B8.LR(0)项目中的圆点“·”表示（）A.分析的当前位置B.产生式的结束C.输入串的结束D.规约的位置答案：A9.在编译的各阶段中，生成中间代码的阶段是（）A.词法分析B.语法分析C.语义分析D.目标代码生成答案：C10.在递归下降分析程序中，一个非终结符对应一个（）A.全局变量B.递归函数C.分析表项D.文法符号答案：B11.通常一个编译程序中，不仅包含词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成等部分，还应包括（）A.解释器B.模拟器C.表格管理和出错处理D.预处理器答案：C12.在语法分析中，FOLLOW集用于（）A.自顶向下分析中，确定何时使用ε产生式B.自底向上分析中，确定句柄C.语义分析中，确定属性值D.代码生成中，确定寄存器分配答案：A13.在目标代码生成中，一个基本而重要的问题是（）A.如何生成高效的代码B.如何分配寄存器C.如何管理符号表D.如何优化中间代码答案：B14.LR(0)项目集规范族的构造过程，本质上是识别文法所有活前缀的（）的过程。A.NFAB.DFAC.正则表达式D.语法树答案：B15.三地址代码中，每个指令最多有（）个操作符。A.1B.2C.3D.4答案：C16.一个文法，如果存在某个句子有不止一棵语法树对应，则称这个文法是（）A.二义的B.多义的C.递归的D.无二义的答案：A17.在SLR(1)分析中，解决“移进-规约”冲突的方法是：若对于项目集I中的项目A->α·和B->β·aγ，且a∈FOLLOW(A)，则（）A.遇到a时移进B.遇到a时规约C.报错D.由具体文法决定答案：B18.符号表的主要作用是（）A.记录标识符的属性信息，供各阶段查询和更新B.生成中间代码C.优化代码D.分配存储空间答案：A19.在语法分析中，如果既可以使用自顶向下也可以使用自底向上方法，通常优先选择（）A.自顶向下，因为它更简单B.自底向上，因为它更强大C.取决于语言和文法D.没有优先选择答案：C20.LR分析器在识别句柄时，是（）A.自左向右B.自右向左C.自顶向下D.随机选择答案：A21.下面哪种优化属于局部优化？（）A.常数传播B.删除公共子表达式C.删除无用赋值D.循环优化答案：A22.规范规约是关于（）的一个逆过程。A.最左推导B.最右推导C.直接推导D.任意推导答案：B23.正则表达式(a|b)*表示的语言是（）A.空串B.由a和b组成的任意串，包括空串C.以a开头，以b结尾的串D.由a和b组成的任意串，但不包括空串答案：B24.基本块内的优化是（）A.全局优化B.局部优化C.循环优化D.过程间优化答案：B25.在语法制导翻译中，文法符号的属性分为（）和（）。A.数值属性，字符串属性B.继承属性，综合属性C.左属性，右属性D.静态属性，动态属性答案：B26.一个LR分析器由（）、分析栈和（）三个部分组成。A.输入缓冲区，分析表B.语法树，符号表C.状态机，输出缓冲区D.词法分析器，语义分析器答案：A27.在自顶向下的语法分析中，如果文法含有（），则不能采用确定的分析方法。A.右递归B.左递归C.公共左因子D.空产生式答案：B28.语法分析最常用的两类方法是（）。A.自顶向下和自底向上B.向前搜索和向后搜索C.递归和迭代D.确定的和不确定的答案：A29.算符优先分析法通过比较相邻（）的优先关系来确定句柄。A.终结符B.非终结符C.文法符号D.单词符号答案：A30.提取公共左因子是为了解决（）的问题。A.左递归B.FIRST集相交C.回溯D.规约-规约冲突答案：C31.预测分析表是一个二维表，其行对应（），列对应（）。A.非终结符，终结符（包括$）B.终结符，非终结符C.状态，输入符号D.产生式，句型答案：A32.预测分析程序（LL(1)分析器）由（）、分析栈和（）组成。A.输入缓冲区，分析表B.语法树，符号表C.状态机，输出缓冲区D.词法分析器，语义分析器答案：A33.在符号表中，通常需要存放名字的（）和（）等信息。A.类型，长度B.种属（如变量、数组、过程），大小C.类型，种属D.存储位置，作用域答案：C34.自顶向下的语法分析从（）开始推导。A.开始符号B.句柄C.输入串的第一个符号D.任意非终结符答案：A35.LALR(1)分析法在分析能力上介于（）和（）之间。A.LR(0),SLR(1)B.SLR(1),LR(1)C.LL(1),LR(0)D.算符优先，LR(1)答案：B36.LR分析表中的“动作（action）”部分指明：在某个状态下，面对某个输入符号应该采取的动作，动作不包括（）A.移进（shift）B.规约（reduce）C.接受（accept）D.报错（error）E.转向（goto）（注：转向通常在GOTO表部分）答案：E37.在自底向上的语法分析中，用来表示分析过程中历史和展望信息的数据结构是（）A.队列B.栈C.数组D.链表答案：B38.词法分析器的输入是（）A.源程序字符串B.单词符号串C.语法单位D.目标代码答案：A39.正则表达式R1和R2等价，意味着（）A.R1和R2描述的语言相同B.R1和R2的结构相同C.R1和R2的长度相同D.R1和R2的运算符相同答案：A40.如果一个文法存在某个句子，它有两个不同的最左（最右）推导，则该文法是（）A.二义的B.歧义的C.确定的D.无二义的答案：A41.表达式a*(b+c)的后缀式是（）A.abc+*B.abc*+C.ab+c*D.a*bc+答案：A42.状态转换图（或有限自动机）是描述（）的有效工具。A.语法规则B.词法规则C.语义规则D.优化规则答案：B43.正则表达式a(b|c)*表示的语言是（）A.以a开头，后跟任意多个b或c的串B.任意多个a、b、c组成的串C.以a开头，后跟一个b或c的串D.由a、b、c组成的任意串答案：A44.在自顶向下的语法分析中，左递归文法会导致（）A.分析过程提前终止B.分析器陷入无限循环C.产生错误的语法树D.无法处理某些输入符号答案：B45.在循环优化中，将循环中与循环控制变量无关但每次迭代都重复计算的表达式移到循环体外，这种优化称为（）A.代码外提B.强度削弱C.删除归纳变量D.循环展开答案：A46.对嵌套过程语言，符号表的组织通常采用（）结构。A.线性表B.二叉树C.散列表D.栈式答案：D47.LR分析器的核心是（）A.语法树B.LR分析表C.符号表D.状态转换图答案：B48.在LR分析法中，“L”表示（），“R”表示（）。A.最左推导，最右规约B.从左向右扫描输入串，构造最右推导的逆过程C.最右推导，最左规约D.从右向左扫描输入串，构造最左推导的逆过程答案：B49.将程序中的控制流信息（如条件跳转、循环等）加入到中间代码中的过程，是（）的主要任务之一。A.词法分析B.语法分析C.语义分析与中间代码生成D.代码优化答案：C50.在规范规约中，任何可规约串的出现都在（）A.栈顶B.栈底C.输入串的末尾D.输入串的开头答案：A51.词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，（）A.词法分析器应作为独立的一遍B.词法分析器作为子程序较好C.词法分析器分解为多个过程，由语法分析器调用D.词法分析器并不作为一个独立的阶段答案：B52.将程序中的一个基本块复制多份，以利用指令级并行，这种优化称为（）A.循环展开B.代码外提C.强度削弱D.复写传播答案：A53.FOLLOW(A)的定义是：对于非终结符A，FOLLOW(A)是所有句型中（）的集合。A.紧跟在A后面的终结符B.紧跟在A后面的符号C.可以出现在A后面的终结符D.可以出现在A后面的符号答案：C54.语法制导定义（SDD）是上下文无关文法和（）的结合。A.词法规则B.属性及语义规则C.语法树D.中间代码答案：B55.算符优先分析法是一种（）的语法分析方法。A.自顶向下B.自底向上C.递归下降D.不确定答案：B56.在递归下降分析方法中，对应每个非终结符有一个（）A.分析表B.状态转换图C.递归子程序D.栈答案：C57.当一个过程（或块）的代码执行完毕时，需要（）A.创建新的符号表B.删除该过程对应的符号表项C.查找符号表中的所有项D.将符号表指针指向外层作用域答案：B58.FIRST集的定义是：对于文法符号串α，FIRST(α)是（）A.α可能推导出的所有终结符号串的集合B.α可能推导出的所有终结符号串的第一个符号的集合C.α可能推导出的所有句型的集合D.α本身包含的终结符号集合答案：B59.在词法分析中，能识别出（）A.基本字B.短语C.句子D.句柄答案：A60.词法分析器的输出是（）A.语法树B.单词符号串C.中间代码D.目标代码答案：B61.SLR(1)分析法使用（）来解决LR(0)项目集中的冲突。A.更多的展望信息B.FOLLOW集信息C.FIRST集信息D.语义信息答案：B62.词法分析器通常被实现为一个（）A.独立的过程，由语法分析器调用B.独立的一遍扫描C.与语法分析器合并的过程D.解释器答案：A63.在自底向上的分析中，分析栈中存放的是（）A.句型B.句柄C.活前缀D.输入符号答案：C64.代码优化可以分为（）优化和（）优化。A.局部，全局B.语句级，程序级C.语法级，语义级D.编译时，运行时答案：A65.最小化DFA的目的是（）A.提高识别的准确性B.减少状态数，提高效率C.使其成为NFAD.使其能识别更多字符串答案：B66.递归下降分析法的优点是（）A.分析速度快B.程序结构清晰，易于手工实现C.能处理所有文法D.不需要消除左递归答案：B67.S-属性定义是只含有（）属性的语法制导定义。A.继承B.综合C.内在D.传递答案：B68.一个LL(1)文法（）是二义的。A.一定B.不一定C.一定不D.可能答案：C69.中间代码的常见形式不包括（）A.三元式B.四元式C.逆波兰表示D.汇编代码答案：D70.对于允许嵌套作用域的语言，符号表的查询通常采用（）策略。A.顺序查找B.二分查找C.先查当前表，未找到再查外层表D.只查最外层表答案：C71.LL(1)分析表中，如果某个表项包含多个产生式，则说明该文法（）A.是LL(1)文法B.不是LL(1)文法C.可能是LL(1)文法D.无法判断答案：B72.LR(1)分析法的能力比SLR(1)分析法（）A.强B.弱C.相同D.无法比较答案：A73.词法分析器的任务是从（）中识别出一个个（）。A.源程序，语句B.字符串，单词C.句子，短语D.语法单位，符号答案：B74.LR(1)项目比LR(0)项目多了一个（）A.产生式B.状态C.展望符D.规约符号答案：C75.抽象语法树（AST）是（）的图形表示。A.词法结构B.语法结构C.语句的抽象语法结构D.程序的控制流答案：C76.逆波兰表示法（后缀式）的特点是（）A.运算符在操作数之前B.运算符在操作数之后C.运算符在操作数中间D.不需要括号答案：B77.将循环中的乘法运算（如i*4）替换为加法运算（如t=t+4），这种优化称为（）A.代码外提B.强度削弱C.删除归纳变量D.循环合并答案：B78.在算符优先分析中，关系a<·b表示（）A.a的优先级低于bB.a的优先级高于bC.a和b优先级相等D.a和b没有关系答案：A79.有限自动机有（）和（）两种类型。A.确定的，不确定的B.线性的，非线性的C.递归的，非递归的D.二义的，无二义的答案：A80.文法的二义性通常（）在理论上判定，（）在实际上消除。A.可以，可以B.不可以，不可以C.可以，不可以D.不可以，可以答案：A81.常用的寄存器分配策略是（）A.随机分配B.图着色分配C.顺序分配D.固定分配答案：B82.将正则表达式转换为NFA的算法是（）A.子集构造法B.Thompson构造法C.递归下降法D.LR分析法答案：B83.在自顶向下的语法分析方法中，分析的关键是（）A.寻找句柄B.寻找可规约串C.消除左递归D.选择使用哪个产生式进行推导答案：D84.一个简单的代码生成器通常基于（）模型。A.栈式B.寄存器C.累加器D.树匹配答案：B85.寄存器分配是代码生成中的一个（）问题。A.简单B.NP完全C.无解D.线性答案：B86.四元式的组成是（）A.(运算符，运算对象1，运算对象2，结果)B.(结果，运算符，运算对象1，运算对象2)C.(运算对象1，运算符，运算对象2，结果)D.(运算符，结果，运算对象1，运算对象2)答案：A87.“状态最小化”是针对（）进行的优化。A.NFAB.DFAC.正则表达式D.文法答案：B88.词法分析器所遵循的是语言的（）A.语法规则B.构词规则（词法规则）C.语义规则D.等价变换规则答案：B89.LALR(1)分析法通过合并LR(1)项目集中（）的项目集来减少状态数。A.核心相同B.展望符集相同C.核心相同且展望符集相同D.产生式相同答案：A90.如果一个文法存在句子对应两棵不同的语法树，则称该文法是（）A.二义性的B.不确定的C.递归的D.复杂的答案：A91.自底向上的语法分析方法中，分析的关键是（）A.寻找句柄B.寻找开始符号C.消除左递归D.选择使用哪个产生式进行推导答案：A92.一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（）A.句子B.句型C.单词D.产生式答案：D93.给定文法G[S]:S->aS|b，该文法描述的语言是（）A.{a^nb|n≥0}B.{a^nb|n≥1}C.{ab^n|n≥0}D.{ab^n|n≥1}答案：A94.在产生式A->XYZ的语义规则中，如果某条规则定义了A的属性，则该属性通常是（）A.继承属性B.综合属性C.既可以是继承也可以是综合D.无法判断答案：B95.代码生成阶段依赖于目标机器的（）A.操作系统B.指令系统C.内存大小D.外设配置答案：B96.语法制导翻译既可以用来产生（），也可以用来产生（）。A.目标代码，语法树B.中间代码，目标代码C.单词符号，语法单位D.符号表，错误信息答案：B97.将NFA转换为等价的DFA的算法是（）A.子集构造法B.Thompson构造法C.递归下降法D.最小化算法答案：A98.算符优先文法要求文法的任何产生式的右部都不含两个（）的非终结符。A.相连B.相邻C.相同D.不同答案：B99.编译程序的各个阶段在工作过程中都会涉及（）A.词法分析B.表格管理C.语法分析D.代码生成答案：B100.综合属性用于自（）向（）传递语义信息。A.上，下B.下，上C.左，右D.右，左答案：B二、多选题101.乔姆斯基文法分类中，2型文法指：A.上下文无关文法B.产生式左部是单个非终结符C.产生式右部可以是εD.产生式右部长度有限制答案：ABC102.一遍扫描的编译器：A.将多个阶段组合在一起B.通常语法分析与语义分析交织C.不产生显式的中间代码D.适合解释型语言答案：ABC103.文法G是二义的，当且仅当：A.G中存在某个句子对应两棵不同的语法树B.G中存在某个句子有两个不同的最左推导C.G中存在某个句子有两个不同的最右推导D.G不是LL(1)文法答案：ABC104.乔姆斯基文法分类中，3型文法指：A.正规文法B.右线性文法或左线性文法C.产生式右部最多有一个非终结符D.描述的语言可由有限自动机识别答案：ABCD105.编译原理中常用的数学工具有：A.集合论B.图论C.自动机理论D.数理逻辑答案：ABC106.简单的代码生成算法需要考虑：A.寄存器的描述和分配B.目标代码的生成顺序C.数据依赖关系D.窥孔优化答案：ABC107.编译前端通常包括：A.词法分析B.语法分析C.语义分析与中间代码生成D.代码优化答案：ABC108.图着色法寄存器分配的基本步骤包括：A.构建冲突图B.简化图C.选择寄存器D.溢出处理答案：ABCD109.编译后端通常包括：A.中间代码优化B.目标代码生成C.目标代码优化D.符号表管理答案：ABC110.循环的查找通常基于：A.控制流图B.深度优先搜索树C.回边D.必经结点集答案：ABCD111.DAG图可以用于：A.表示基本块内的计算过程B.发现公共子表达式C.确定计算顺序D.进行循环优化答案：ABC112.语言是上下文无关的，当且仅当：A.它可以由一个上下文无关文法产生B.它可以由一个下推自动机识别C.它可以由一个正规式描述D.它可以由一个有限自动机识别答案：AB113.优化进行的基本原则包括：A.等价变换B.提高速度或节省空间C.遵守依赖关系D.可能导致程序行为改变答案：ABC114.学习编译原理的意义在于：A.理解高级语言程序如何被计算机执行B.掌握设计和实现编程语言的能力C.提高程序调试和优化能力D.为学习操作系统等课程打下基础答案：ABCD115.从DAG生成代码时，需要：A.对DAG结点进行排序B.为结点选择寄存器或内存位置C.生成对应的目标指令D.构建控制流图答案：ABC116.编译器可能产生哪些类型的错误信息：A.词法错误B.语法错误C.语义错误D.运行时错误答案：ABC117.目标机的主要特征会影响代码生成，包括：A.指令集B.寄存器个数和功能C.寻址方式D.操作系统答案：ABC118.到达-定值分析中，一个定值d到达点p，意味着：A.有一条从d到p的路径B.该路径上d没有被“杀死”C.变量在p点被使用D.p点之前没有其他定值答案：AB119.多遍扫描的编译器的优点有：A.结构清晰，易于实现和维护B.可以进行复杂的全局优化C.各阶段独立，便于重用D.编译速度快答案：ABC三、判断题120.预测分析法（LL(1)）是一种无回溯的自顶向下分析方法。答案：正确121.静态存储分配在编译时确定所有数据对象的存储地址。答案：正确122.代码优化可以完全消除程序中所有不必要的计算。答案：错误123.自顶向下语法分析在遇到选择时，可能需要回溯。答案：正确124.后缀式非常适合基于栈的求值。答案：正确125.循环展开属于循环优化，通过增加循环体代码来减少循环控制开销。答案：正确126.最小化DFA可以使其状态数达到最少。答案：正确127.词法分析阶段发现的错误通常是非法字符或不符合词法规则的字符序列。答案：正确128.栈式动态存储分配支持过程的递归调用。答案：正确129.目标代码生成中，必须为每一个变量分配一个固定的存储单元。答案：错误130.数据流分析是进行全局优化的重要基础。答案：正确131.语法错误恢复是编译程序应该具备的功能之一。答案：正确132.LR分析法在分析过程中，需要不断地查看输入串的下一个符号（展望符）。答案：正确133.正规式(a|b)*和(a*b*)*描述的语言是相同的。答案：正确134.编译程序必须为用户程序分配运行时的存储空间。答案：正确135.两个有限自动机等价，当且仅当它们识别的语言相同。答案：正确136.图着色法是一种经典的寄存器分配算法。答案：正确137.词法分析器返回的单词符号通常是一个二元组（种别编码，属性值）。答案：正确138.符号表的查询效率对整个编译器的性能影响不大。答案：错误139.堆式动态存储分配用于管理生命周期不确定的数据。答案：正确四、简答题140.什么是“一遍扫描”的编译程序？其优缺点是什么？解析：“一遍扫描”编译程序是指将编译的多个阶段组合起来，在对源程序的一次完整扫描过程中完成从分析到代码生成的各项工作（可能不显式生成完整的中间代码）。优点：节省时间和空间开销，适合内存受限的环境。缺点：各阶段交织，程序结构不清晰；难以进行复杂的、需要全局信息的优化；错误处理和调试支持较弱。141.简述在基于DAG（有向无环图）的局部优化中，如何利用DAG进行优化。解析：为基本块构造DAG，其结点代表运算或变量初值，边表示依赖关系。利用DAG可进行以下优化：1.删除公共子表达式：相同运算对应同一个DAG结点，可消除重复计算。2.删除无用代码：如果没有父结点引用某个变量的赋值结点，则该赋值可能无用（除非该变量在块外被引用，需谨慎）。3.代数恒等变换：利用代数性质（如`x+0=x`）简化DAG。优化后，从DAG出发可生成更高效的三地址代码序列。142.什么是“内联展开”（Inlining）？它有哪些优点和潜在缺点？解析：内联展开是一种优化，将函数调用点用被调用函数的函数体代码替换。优点：1.消除调用开销（参数传递、控制转移、活动记录管理）；2.为编译器带来更多的上下文信息，便于进行后续优化（如常量传播、死代码删除）。潜在缺点：1.增加代码大小，可能影响指令缓存命中率；2.过度内联可能导致编译时间增长；3.对于递归函数需谨慎处理。通常由编译器启发式决定或由程序员指导进行。143.简述寄存器分配中图着色法的基本原理和关键步骤。解析：基本原理：将寄存器分配问题抽象为图着色问题。以变量（或临时值）为图的结点，如果两个变量在同一时刻都需要寄存器（即它们“冲突”，生命期重叠），则在它们之间连一条边。试图用K种颜色（K为可用寄存器数目）为图着色，相邻结点颜色不同。着色成功意味着为每个变量分配了一个寄存器（颜色），且冲突变量不同寄存器。关键步骤：1.建立冲突图；2.尝试着色，若失败则需“溢出”某些变量到内存；3.生成加载/存储代码。144.简述编译器前端与后端的划分及其意义。解析：划分：前端包括词法分析、语法分析、语义分析及中间代码生成，主要依赖于源语言。后端包括代码优化和目标代码生成，主要依赖于目标机器。意义：1.模块化与可移植性：为一种新语言开发编译器时，只需重写前端，可复用后端；为一种新机器开发编译器时，只需重写后端，可复用前端。2.便于团队分工协作。这是现代编译器设计的经典结构。145.简述控制流图