编译原理习题

编译原理复习资料一、填空题.1.编译程序是一种程序，能够将某一种高级语言编写的源程序改造成另一种低级语言编写的目标程序，它们在逻辑上＿等价＿＿，完成＿相同＿＿的工作。2.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是___二义性的____。3.词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号，并以___单词符号或单词符号表示的源程序_____的形式输出。4.编译程序一般划分为词法分析、语法分析、语义分析、中间代码生成、和＿代码优化＿目标代码生成六个阶段；除此以外,还有两个重要的基本工作,它们是＿表格管理＿和＿出错处理_。5.目前，语法分析方法有两大类，分别为自上向下的分析方法和__自下而上__分析方法。自上而下的分析方法是从____文法的开始符号_____出发，根据文法规则正向推导出给定句子的方法。6.属性文法是编译技术中用来说明程序设计语言的__语义___的工具。7.若源程序是用高级语言编写的,_____目标程序____是机器语言程序或汇编程序,则其翻译程序称为__编译程序____。8.扫描器（程序）的任务是从____字符串____中识别出一个个___单词符号___。9.一个LR分析器包括三部分：总控程序、_分析表___和分析栈。10.自顶向下的语法分析方法的基本思想是：从文法的___开始符号_____出发，根据给定的输入串并按照文法的产生式一步一步的向下进行____正向推导___，试图推导出文法的__给力句子__，使之与给定的输入串匹配。11.按Chomsky分类法，文法被分成__4（0~3型文法）_类。12.局部优化是在__基本块__范围内进行的一种优化。13.编译程序是一种＿翻译＿程序，它将某一种高级语言编写的源程序改造成另一种低级语言编写的目标程序，源程序和目标程序在逻辑上等价，完成相同的工作。14.编译程序与解释程序的根本区别为___解释程序在执行中不产生目标程序___。15.语法分析的任务是识别给定的终结符号串是否为给定文法的___句子___。16.编译程序一般划分为＿词法＿分析、语法分析、＿语义＿分析、中间代码生成、＿代码优化＿和目标代码生成六个阶段；除此以外,还有两个重要的基本工作,它们是＿＿表格管理＿和＿出错处理＿。17.局部优化是局限于一个___基本块__范围内的一种优化。18.一个上下文无关文法G包括四个组成部分，他们是：一组非终结符号，一组终结符号，一个开始符号，以及一组___文法规则__。二、单选题.（A）1.一般程序设计语言的定义都涉及到_______三个方面。（1）语法（2）语义（3）语用（4）程序基本符号的确定A、（1）（2）（3）B、（1）（2）（4）C、（1）（3）（4）D、（2）（3）（4）（B）2.编译程序是将高级语言程序翻译成_______。A、机器语言程序B、汇编语言程序或机器语言程序C、汇编语言程序或高级语言程序D、机器语言程序或高级语言程序（D）3.文法G所描述的语言是＿＿＿的集合。A、文法G的字母表Σ中所有符号组成的符号串B、文法G的字母表Σ中的Σ*中的所有符号串D、由文法的开始符号推出的所有终结符号串（B）4.一个句型中的最左＿＿＿称为该句型的句柄。A、短语B、直接短语C、素短语D、终结符号（C）5.正规式中，符号＂＊＂读作＿＿＿。A、并且B、或者C、闭包D、连接（B）6.LL(1)文法、OPG文法和LR(K)文法＿＿＿二义性的。A、都是B、都不是C、不一定都是D、不能确定（B）7.逆波兰表达式ab+cd+*所代表的中缀形式的表达式是。A、a+b+c*dB、(a+b)*(c+d)C、(a+b)*c+dD、a+b*c+d（D）8.程序基本块是指。A、一个子程序B、一个仅有一个入口和一个出口的语句D、一组顺序执行的程序段，仅有一个入口和一个出口（D）9.在编译程序采用的优化方法中，是在循环语句范围内进行的。（1）合并已知常量（2）删除多余运算（3）删除归纳变量（4）强度削弱（5）代码外提A、（1）（4）B、（1）（5）C、（1）（4）（5）D、（3）（4）（5）（B）10.采用自上而下语法分析法分析文法时，必须先_____。　A、消除回溯　B、消除左递归C、消除右递归　　D、提取公共左因子（C）11.已知一文法G[S]：S→xSxy则其识别的语言是＿＿＿＿＿。A、xyxB、(xyx)*C、xnyxn(n0)D、x*yx*（A）12.在常用的语法分析方法中，递归下降分析法属于＿＿分析方法。A、自顶向下B、自左向右C、自底向上D、自右向左（B）13.逆波兰表达式ab+cd+*所代表的中缀形式的表达式是＿＿＿＿＿。A、a+b+c*dB、(a+b)*(c+d)C、(a+b)*c+dD、a+b*c+d（B）14.正规式中，符号＂|＂读作＿＿＿。A、并且B、或者C、连接D、闭包（C）15.算符优先分析法每次都是对＿＿＿进行归约。A、最左短语B、直接短语C、最左素短语D、素短语（D）16.LR(k)方法是＿＿＿。A、从左到右分析，每次走k步的一种编译方法B、从左到右分析，共走k步的一种编译方法C、从左到右分析，每次向前预测k步的一种编译方法D、从左到右分析，每次向貌似句柄的符号串后看k个输入符号的一种编译方法（D）17.代码优化后可生成_____的目标代码。A、运行时间较短B、占用存储空间较小　C、运行时间短但占用内存空间大　　D、运行时间短且占用存储空间小（A）18.若文法G定义的语言是无穷集，则文法必然是_____。A、递归的　　B、前后文无关的　C、二义性的　　D、无二义性的（B）19.一个文法所描述的语言是_____。A、不唯一的　B、唯一的C、可能唯一，也可能不唯一D、都不对（B）20.若a为终结符，则A-α.aβ为_____项目。A、归约　　B、移进　C、接受　　D、待约（C）21.词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号，并将单词或单词序列以_______的形式输出。A、单词B、单词序列C、二元组即种别码和自身值D、语法树（A）22.编译程序是将高级语言程序翻译成_______。A、汇编语言程序或机器语言程序B、机器语言程序C、汇编语言程序或高级语言程序D、机器语言程序或高级语言程序（C）23.属性文法是编译技术中用来说明程序设计语言的_____________的工具。A、词法B、语法C、语义D、代码优化（D）24.文法G所描述的语言是＿＿＿的集合。A、文法G的字母表Σ中所有符号组成的符号串B、文法G的字母表Σ中的Σ*中的所有符号串D、由文法的开始符号推出的所有终结符号串（A）25.乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型和3型。其中3型文法是＿＿＿。A、正规文法B、短语文法C、上下文无关文法D、上下文有关文法（C）26.用l代表字母，用d代表数字，∑={l，d}，则定义标识符单词的正规式为＿.A、ld*B、ll*C、l(l|d)*D、ll*|d*（B）27.LL(1)文法、OPG文法和LR(K)文法＿＿＿二义性的。A、都是B、都不是C、不一定都是D、不能确定（A）28.中缀表达式-b+c*(-d+a)所代表的逆波兰形式的表达式是。A、b@cd@a+*+B、d@a+b@c*+C、b@cd@a*++D、b@cd@a++*（D）29.设一个文法G，若G中没有形如A→…BC…的规则，其中A、B、C为非终结符，则称文法G为＿＿。A、算符优先文法B、LL(1)文法C、LR（0）文法D、算符文法（B）30.LR语法分析栈中存放的状态是识别文法规范句型_____的DFA状态。　A、前缀　B、活前缀C、项目　　D、句柄得分三、判断改错题（对打√，错打×并改正之）（×）1.编译程序是一种常用的应用软件。（×）2.设符号串x为10，则x0=1。（√）3.在形式语言中，最右推导的逆过程称为规范归约。（×）4.一张状态转换图中只包含有限个状态，其中有一个唯一的初态，最多只有一个终态。（×）5.算符优先分析法是一种规范归约分析法，每次归约的可归约串是句柄。（√）6.在编译程序中安排中间代码生成的目的是利于目标代码优化和便于编译程序的移植。（×）7.转移语句是基本块的入口语句。（√）8.若某符号串是一个文法的句子，则该符号串一定是该文法的句型。（×）9.一个语言所对应的文法是唯一的。（√）10.正规文法和正规式是描述程序语言单词符号的两种不同的形式化形式。（×）11.若OPG文法存在一张算符优先关系表，则一定存在对应的优先函数。（√）12.LL(1)文法一定是无左递归和无二义性的文法。（×）13.所谓语法制导翻译法是指在语法分析过程中，随着分析的逐步进行，根据相应文法的每一个产生式所对应的词法子程序进行翻译。（√）14.自顶向下的语法分析方法的关键是如何选择候选式的问题。（×）15.一个句型中的最左短语称为该句型的句柄。（√）16.递归下降语法分析方法不允许任一非终结符是直接左递归的。（√）17.LR语法分析法是一种规范归约分析法，每次归约的可归约串是句柄。（×）18.一张状态转换图中只包含有限个状态，其中有一个唯一的初态，最多只有一个终态。四、综合题.本题中各小题均需要有详细求解计算过程，否则不得分。1.已知文法G[Z]:Z→0U|1VU→1Z|1V→0Z|0（1）请写出此文法描述的只含有４个符号的全部句子。（2）G[Z]产生的语言是什么？（3）该文法在Chomsky文法分类中属于几型文法？2.已知文法G[S]:S→TB请求出G[S]每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。T→Ba|B→Db|eT|D→d|　解答：　　计算文法的FIRST和FOLLOW集合：(4分)　　FIRST(M)={a，b，e，d，}FIRST(T)={a，b，e，d，}　　FIRST(B)={b，e，d，}FIRST(D)={d，}　　FOLLOW(M)={#}FOLLOW(T)={a，b，e，d，#}　　FOLLOW(B)={a，#}FOLLOW(D)={b}3.已知文法G(E)：　E→T|E＋T|E-T　　T→F|T*F|T/F　　F→(E)|i求符号串T*i+(F-i)的短语、素短语、直接短语和句柄。句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;简单短语为i、T*F、第一个T;句柄为第一个T。4.考虑简单赋值语句的文法G[S]：Sid:=EEE+EEE*EEid(1)试构造识别该文法所有规范句型活前缀的有穷自动机。(2)判断该文法是否为LR(0)文法（必须说明理由）。解:(1)I0:S’.SS.id=EI1:S’S.I2:Sid.=EI3:Sid=.EE.E+EE.E*EE.idI4:Sid=E.EE.+EEE.*EI5:Eid.I6:EE+.E（2）由于I4、I8、I9均有移进—归约冲突，E.E+EE.E*E故该文法不是LR(0)文法。E.idI7:EE*EE.E+EE.E*EE.idI8:EE+EEE.+EEE.*EI9:EE*E.EE.+EEE.*E5.构造正规式ba(b︱a)*bab相应的DFA。6.已知文法G[E]:E→Tc|aFT→abF→bc证明该文法是二义性文法。7.写一个文法，使其语言是偶数的集合，且每个偶数不以0开头。8.已知文法G[S]:S→1A请求出G[S]所对应的正规式。A→0A|1B|1B→1A9.已知文法G[S]：S（L|aLS,L|)（1）构造文法G[S]的预测分析表。（2）若输入串为“（ａ，）”，请给出语法分析过程。10.已知文法G[Z]:Z→HZ|aH→ZH|b判断该文法是否为LR(0)、SLR(1)、LR(1)、LALR(1)文法？并说明理由。11.给出表达式-a+b*(-c+d)的三元式和四元式两种中间代码表示形式。12.已知文法G[S]:S→1S0|10求该文法G[S]所描述的语言L。13.已知文法G[E]:E→Tc|aFT→abF→bc证明该文法是二义性文法。14.已知表达式为-a+