编译原理复习资料

1、编译原理复习资料一、填空题.1. 编译程序是一种程序，能够将某一种高级语言编写的源程序改造成另一种低级语言编写的目标程序，它们在逻辑上等价，完成相同的工作。2. 如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是_二义性的_。3. 词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号，并以_单词符号或单词符号表示的源程序_的形式输出。4. 编译程序一般划分为词法分析、语法分析、语义分析、中间代码生成、和代码优化目标代码生成六个阶段； 除此以外,还有两个重要的基本工作,它们是表格管理和出错处理_。5. 目前，语法分析方法有两大类，分别为自上向下的分析方法和

2、_自下而上_分析方法。自上而下的分析方法是从_文法的开始符号_出发，根据文法规则正向推导出给定句子的方法。6. 属性文法是编译技术中用来说明程序设计语言的_语义_的工具。7. 若源程序是用高级语言编写的,_目标程序 _是机器语言程序或汇编程序,则其翻译程序称为_编译程序_。8. 扫描器（程序）的任务是从_字符串_中识别出一个个_单词符号_。9. 一个lr分析器包括三部分：总控程序、_分析表_和分析栈。10. 自顶向下的语法分析方法的基本思想是：从文法的_开始符号_出发，根据给定的输入串并按照文法的产生式一步一步的向下进行_正向推导_，试图推导出文法的_给力句子_，使之与给定的输入串匹配。11.

3、 按chomsky分类法，文法被分成_4（03型文法）_类。12. 局部优化是在_基本块_范围内进行的一种优化。13. 编译程序是一种翻译程序，它将某一种高级语言编写的源程序改造成另一种低级语言编写的目标程序，源程序和目标程序在逻辑上等价，完成相同的工作。14. 编译程序与解释程序的根本区别为_解释程序在执行中不产生目标程序_。15. 语法分析的任务是识别给定的终结符号串是否为给定文法的_句子_。16. 编译程序一般划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段； 除此以外,还有两个重要的基本工作,它们是表格管理和出错处理。17. 局部优化是局限于一个_基本块

4、_范围内的一种优化。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的字母表中所有符号组成的符

5、号串 b、文法g的字母表中的*中的所有符号串c、由文法的开始符号推出的所有符号串 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*d b、(a+b)*(c+d) c、(a+b)*c+d d、a+b*c+d （ d ）8. 程序基本

6、块是指 。a、一个子程序 b、一个仅有一个入口和一个出口的语句 c、一个没有嵌套的程序段 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. 已知一文法gs：sxsx½

7、;y 则其识别的语言是。a、xyx b、(xyx)* c、xnyxn(n³0) d、x*yx*（ a ）12. 在常用的语法分析方法中，递归下降分析法属于分析方法。a、自顶向下 b、自左向右 c、自底向上 d、自右向左 （ b ）13. 逆波兰表达式ab+cd+*所代表的中缀形式的表达式是。a、a+b+c*d b、(a+b)*(c+d) c、(a+b)*c+d d、a+b*c+d （ b ）14. 正规式中，符号|读作。a、并且 b、或者 c、连接 d、闭包（ c ）15. 算符优先分析法每次都是对进行归约。a、最左短语 b、直接短语 c、最左素短语 d、素短语（ d ）16. lr

8、(k)方法是。a、从左到右分析，每次走k步的一种编译方法 b、从左到右分析，共走k步的一种编译方法c、从左到右分析，每次向前预测k步的一种编译方法 d、从左到右分析，每次向貌似句柄的符号串后看k个输入符号的一种编译方法（ d ）17. 代码优化后可生成_的目标代码。a、运行时间较短         b、占用存储空间较小 c、运行时间短但占用内存空间大 d、运行时间短且占用存储空间小（ a ）18. 若文法 g 定义的语言是无穷集，则文法必然是_。  a、递归的   b、前后文无关的 

9、c、二义性的 d、无二义性的（ b ）19. 一个文法所描述的语言是_。a、不唯一的 b、唯一的    c、可能唯一，也可能不唯一   d、都不对（ b ）20. 若a为终结符，则a->.a为_项目。a、归约   b、移进     c、接受      d、待约（ c ）21. 词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号，并将单词或单词序列以_的形式输出。a、单词 b、单词序列 c、二元组即种别码和自身值 d、语

10、法树（ a ）22. 编译程序是将高级语言程序翻译成_。a、汇编语言程序或机器语言程序 b、机器语言程序c、汇编语言程序或高级语言程序 d、机器语言程序或高级语言程序（ c ）23. 属性文法是编译技术中用来说明程序设计语言的_的工具。a、词法 b、语法 c、语义 d、代码优化（ d ）24. 文法g所描述的语言是的集合。a、文法g的字母表中所有符号组成的符号串 b、文法g的字母表中的*中的所有符号串c、由文法的开始符号推出的所有符号串 d、由文法的开始符号推出的所有终结符号串（ a ）25. 乔姆斯基(chomsky)把文法分为四种类型，即0型、1型、2型和3型。其中3型文法是。a、正规文法

11、 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、bcda+*+ b、da+bc*+ c、bcda*+ d、bcda+* （ d ）29. 设一个文法g，若g中没有形如abc的规则，其中a、b、c为非终结符，则称文法g为。a、算符优先文法 b、l

12、l(1)文法 c、lr（0）文法 d、算符文法（ b ）30. lr语法分析栈中存放的状态是识别文法规范句型_的dfa状态。 a、前缀  b、活前缀   c、项目 d、句柄得分三、判断改错题（对打，错打×并改正之）（ × ）1.编译程序是一种常用的应用软件。（ × ）2.设符号串x为10，则x0 = 1 。（ ）3.在形式语言中，最右推导的逆过程称为规范归约。（ × ）4.一张状态转换图中只包含有限个状态，其中有一个唯一的初态，最多只有一个终态。（ × ）5.算符优先分析法是一种规范归约分析法，每次归约的

13、可归约串是句柄。（ ）6. 在编译程序中安排中间代码生成的目的是利于目标代码优化和便于编译程序的移植。（ × ）7. 转移语句是基本块的入口语句。（ ）8.若某符号串是一个文法的句子，则该符号串一定是该文法的句型。（ × ）9.一个语言所对应的文法是唯一的。（ ）10.正规文法和正规式是描述程序语言单词符号的两种不同的形式化形式。（ × ）11.若opg文法存在一张算符优先关系表，则一定存在对应的优先函数。（ ）12.ll(1)文法一定是无左递归和无二义性的文法。（ × ）13.所谓语法制导翻译法是指在语法分析过程中，随着分析的逐步进行，根据相应文法的每

14、一个产生式所对应的词法子程序进行翻译。（ ）14.自顶向下的语法分析方法的关键是如何选择候选式的问题。（ × ）15.一个句型中的最左短语称为该句型的句柄。（ ）16.递归下降语法分析方法不允许任一非终结符是直接左递归的。（ ）17.lr语法分析法是一种规范归约分析法，每次归约的可归约串是句柄。（ × ）18.一张状态转换图中只包含有限个状态，其中有一个唯一的初态，最多只有一个终态。四、综合题.本题中各小题均需要有详细求解计算过程，否则不得分。1. 已知文法gz: z0u|1vu1z|1v0z|0（1） 请写出此文法描述的只含有个符号的全部句子。（2） gz产生的语言是什么

15、？ （3） 该文法在chomsky文法分类中属于几型文法？请求出gs每个非终结符的first和follow集合，并判断该文法是否是ll(1)的，请说明理由。2. 已知文法gs: stbtba|ebdb|et|edd|e3. 已知文法g(e)： et|et|e-t tf|t *f|t/f f(e)|i 求符号串t*i+(f-i)的短语、素短语、直接短语和句柄。4. 考虑简单赋值语句的文法gs： s ® id:= e e ® e + ee ® e * ee ® id(1) 试构造识别该文法所有规范句型活前缀的有穷自动机。(2) 判断该文法是否为lr(0)文法

16、（必须说明理由）。5. 构造正规式 ba(ba)* bab相应的dfa。6. 写一个文法使其语言为l(g)= anbmambn | m,n1。7. 构造正规式(a|b)*(ab|ba)(a|b)*相应的最小化的dfa。8. 已知文法ge: etc|af tab fbc 证明该文法是二义性文法。9. 写一个文法，使其语言是偶数的集合，且每个偶数不以0开头。请求出gs所对应的正规式。10. 已知文法gs: s1aa0a|1b|1b1a11. 已知文法gs： s®（l|a l®s,l|)（1） 构造文法gs的预测分析表。（2） 若输入串为“（，）”，请给出语法分析过程。（3）12

17、. 已知文法gz: zhz|ahzh|b判断该文法是否为lr(0)、slr(1)、lr(1)、lalr(1)文法？并说明理由。13. 已知文法ge: etc|af tab fbc 证明该文法是二义性文法。14. 已知表达式为-a+b*(c+d/e)，求该表达式的逆波兰式、三元式、四元式和树形表示。请按要求完成以下内容。（1）改写文法以消除左递归；（2分）（2）并求改写后的文法g,a每个非终结符的first集和follow集；（4分）（3）判断g,a是否是ll(1)的。(4分)15. 已知文法ga: aaab|bbbbc|cced|dd(a)|i求该文法的lr(0)项目。(3分)16. 已知文法gs: saa|bbaca|dbcb|d请按要求完成以下内容。(1)求文法gs每个非终结符的firstvt集和lastvt集；（4分）(2)构造该文法的算符优先关系表。(6分)17