编译原理复习提纲.doc

一. 选择题：1. 词法分析的作用是（ ）A 识别出单词B 识别出保留字C 分析源程序的语法是否合法D 识别出标识符2. （ ）不是自下而上（自底向上）的分析方法A LR（0）分析法B SLR分析法C 算符优先分析法D LL（1）分析法3. 乔姆斯基的3型文法对应的自动机是（ ）A 图灵机B 线性界限自动机C 下推自动机D 有穷自动机4. 下面说法（ ）错误的A 句型是从识别（开始）符号推导出来的符号串B 由终结符号组成的句型是句子C 句子是句型的特例D 句型中必须含有非终结符号5. （ ）描述的是语言abn|n0A ab* B a|bC a*|b* D （a*b*）* 6. （ ）描述的是语言ambn|m,n0E ab* B. a|bC. a|b* D. a*b*7. 下列四种方式中，（ ）能完成对高级语言源程序的翻译A 汇编B 反汇编 C 编译 D 预处理8. 下面关于符号表的说法正确的是（ ）A 一个编译程序只能使用一个符号表B 有序表的建表速度相对较快C 编译程序可以没有符号表D 符号表的主重要作用之一就是收集单词的属性9. 对于下面文法（ ）是LL（1）文法A G1：EE+ E | E* E |(E) | iB G2：ScSc| aSa |bC G3：Sa |(T) TT,S | SD G4：NND | D D0 | 1 | 1010. 对于下面文法（ ）是LL（1）文法E G1：EE+ E | iF G2：SaSa |bG G3：SSb | aH G4：AaA |ab11. 代码优化的主要目的是( )A 提高目标程序运行时的时间和空间效率B 提高目标程序的易读性C 提高目标程序的重用性D 获得最短的目标代码12. ( ) 所需的空间是采用静态存储分配的A 局部变量B 用户申请的临时单元C 函数或过程的形式参数D 全局变量13. 不属于编译的阶段是（ ）A. 中间语言B. 语义分析C. 语法分析D. 中间代码优化14. 属于编译的工作阶段是（ ）E 语法分析F 语言工具的选择G 中间语言设计H 目标机指令系统分析15. （ ）是自顶向下的分析方法A.LR(1)分析法B.SLR(1)分析法C.LALR(1)分析法D.递归子程序分析法16. 大部分与语法分析有关文法属于、（ ）A.0型文法B.1型文法C.2型文法D.3型文法17. 与词法分析有关文法近似于（ ）A.0型文法B.1型文法C.2型文法D.3型文法18. 下面关于语言和文法的描述（ ）是错误的A.文法是有限的但描述的语言可以是无限的D.若语言是无限（穷）的，则文法的规则必须是无限（穷）的C.若两文法描述的语言相同则这两文法等价D.语言是句子的集合19. 设有文法GS:SaSb|d 下列（ ）是该文法句子A. ababd C. adbbB. adb D. aadb20. 下列四种程序中（ ）是翻译程序A. C#语言程序B.编译程序 C.目标程序 D.源程序21. 设计符号表时，最后考虑的因素是（ ）A.登记项的格式B.符号表的查找算法C.编写符号表的语言D.符号表的组织22. 下面关于符号表的说法正确的是（ ）A.一个编译程序只能使用一个符号表B.无序表的查找速度相对较快C.编译程序可以没有符号表D.符号表的主重要作用之一就是收集单词的属性23. 符号表的主要作用之一是（ ）E 统计单词个数F 统计源源程序长度G 收集有关单词属性H 统计出错次数24. 下面对于LL（1）分析法不正确的描述是（ ）A.LL（1）分析法最多只需超前扫描1个符号B.LL（1）分析法是基于归约的分析法C.LL（1）分析法是自顶向下的的分析法D.LL（1）分析法又叫预测分析法25. 代码优化主要对 ( )进行的A.源代码B.目标代码C.中间代码D.二进制代码26. 下面说法不正确的是（ ）A 句子是句型的特例B 文法的二义性与语言的二义性是同一个概念C 一个语言所包含的句子是有穷的则称该语言为有穷语言D 存在递归规则的文法称为递归文法二. 填空： 1. 源程序翻译采用编译方式与解释方式的主要区别是 。2. 在编译程序中把与源语言无关只依赖于目标机器部分称为 3. 编译程序从研制角度可分为 、 两部分。4. 在编译程序中把与源语言有关而不依赖于目标机器部分称为 5. 编译程序典型的工作过程可分成 、 、 、 、 五个阶段。6. 一个文法定义为四元组(Vn,Vt,P,S),其中P为 。7. 一个文法定义为四元组(Vn,Vt,P,S),其中S为 8. 文法GS:SaSb|c的语言是 。9. 文法GS:SAa AAb |a 的语言是 .10. 文法GS:SaSb|c的语言是 11. 语言anban|n0的二型文法是 。12. 语言ambn|m,n1的二型文法是 13. 文法中引入递归文法的好处是 。14. 简化了的文法是去除了 规则和 规则后得到的文法。15. 执行（运行）时的内存分配方式分为 、 。16. 优化从对程序的作用范围和规模上可分为 、 。17. 对于形如Aa的LR（0）项目,其中、V*,aVt，则该项目称为 。18. LALR(1)分析法是通过对LR(1)项目集规范族进行 来缩小分析表的。19. 动态存储分配分为 、 20. 规范推导就是 推导。21. 有害规则是指形如 的规则。22. 有穷自动机可用四元组(函数),表格（矩阵）和 这三种形式来定义。三. 概念1.常用的符号表的结构2.简述内存分配分哪几种？简述内存分配完成的主要任务？3. 辨析下列编译原理所涉及的概念（1） 编译程序和解释程序（2） 编译、连接和调试4.一个形式文法可由四元式表表示，根据乔姆斯基的文法分类，请给出二型文法和三型文法的条件，并说明它们在程序语言分析中的作用。5.符号表的有效组织和管理是编译程序的重要任务，请解释无序符号表、有序符号表和散列表三种结构的符号表的概念，并比较它们对编译程序效率的影响四. 综合题1. 证明文法GS：SAB AAb|b BBb|b是二义性的。2. 试证明文法GN：NND|D D0|1|2|3|4|5|6|7|8|9|10 是二义性的。3. 已知：GS：SaAB AAa|Ba|a Bbd 试指出句子abdaabd的短语、简单短语、和句柄。4. 已知：GS：SAc AaAb|B Bbd 试指出句子aabdbbc的短语、简单短语、和句柄。5. 设有文法GS：SAB B bAB|a A（S）|b 试画出该文法的LL(1)分析表。6. 设GS： S 0LT TaL|0 L0L|1 L|a试构造相应的预测LL（1）分析表。7. 写出 anbmcn|n,m1对应的文法8. 将下图对应的DFA最小化 。9. 设有造拓广文法GS: (0) SS (1) SaL (2) LL,i (3) Li 试构造其SLR分析表10. 设GS： S bBT TaB|b BbB|c B|a试构造相应的预测分析表。 a b c # S B T11. 设有文法GS: Sa(L) LL ba La试构造其SLR分析表12. 语言和文法写出下列文法G: SabSba S1A A0A A1所定义的语言1