编译原理习题

编译原理复习资料

一、填空题.

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的字母表Σ中的Σ中

的所有符号串

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. 程序基本块是指 。

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. 已知一文法G[S]：S→xSx?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(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的字母表Σ中的Σ*

中的所有符号串

C、由文法的开始符号推出的所有符号串 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，则x= 1 。

（ √ ）3.在形式语言中，最右推导的逆过程称为规范归约。

（ × ）4.一张状态转换图中只包含有限个状态，其中有一个唯一的初态，最多只有一个

终态。

（ × ）5.算符优先分析法是一种规范归约分析法，每次归约的可归约串是句柄。

（ √ ）6. 在编译程序中安排中间代码生成的目的是利于目标代码优化和便于编译程序

的移植。

（ × ）7. 转移语句是基本块的入口语句。

（ √ ）8.若某符号串是一个文法的句子，则该符号串一定是该文法的句型。

（ × ）9.一个语言所对应的文法是唯一的。

（ √ ）10.正规文法和正规式是描述程序语言单词符号的两种不同的形式化形式。

（ × ）11.若OPG文法存在一张算符优先关系表，则一定存在对应的优先函数。

（ √ ）12.LL(1)文法一定是无左递归和无二义性的文法。

（ × ）13.所谓语法制导翻译法是指在语法分析过程中，随着分析的逐步进行，根据相

应文法的每一个产生式所对应的词法子程序进行翻译。

（ √ ）14.自顶向下的语法分析方法的关键是如何选择候选式的问题。

（ × ）15.一个句型中的最左短语称为该句型的句柄。

（ √ ）16.递归下降语法分析方法不允许任一非终结符是直接左递归的。

（ √ ）17.LR语法分析法是一种规范归约分析法，每次归约的可归约串是句柄。

（ × ）18.一张状态转换图中只包含有限个状态，其中有一个唯一的初态，最多只有一

个终态。

0

四、综合题.

本题中各小题均需要有详细求解计算过程，否则不得分。

1. 已知文法G[Z]: Z→0U|1V

U→1Z|1

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理习题在线全文阅读。