第1页共6页 《编译原理》期末试题（一）
一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）
1．编译程序是对高级语言程序的解释执行。(× )
2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)
3．一个算符优先文法可能不存在算符优先函数与之对应。 (√ )
4．语法分析时必须先消除文法中的左递归 。 (×)
5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (√)
6．逆波兰表示法表示表达式时无须使用括号。 (√ )
7．静态数组的存储空间可以在编译时确定。 (×)
8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (×)
9．两个正规集相等的必要条件是他们对应的正规式等价。 (× )
10．一个语义子程序描述了一个文法所对应的翻译工作。 (×)
二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)
1．词法分析器的输出结果是_____。
A．( ) 单词的种别编码 B．( ) 单词在符号表中的位置
C．( ) 单词的种别编码和自身值 D．( ) 单词自身值
2． 正规式 M 1 和 M 2 等价是指_____。
A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等
C．( ) M1和M2所识别的语言集相等 D．( ) M1和M2状态数和有向边条数相等
3． 文法G：S→xSx|y所识别的语言是_____。 第2页共6页 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*
4．如果文法G是无二义的，则它的任何句子α_____。
A．( )最左推导和最右推导对应的语法树必定相同
B．( ) 最左推导和最右推导对应的语法树可能不同
编译原理复习题一、填空题：
1、编译方式与解释方式的根本区别在于（ 是否生成目标代码 ）。
2、对编译程序而言，输入数据是（ 源程序 ），输出结果是（ 目标程序 ）。
3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段 ）和（ 运行阶段 ）。
4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（ 编译阶段）、（汇编阶段）和（运行阶段）。
5、自顶向下语法分析方法会遇到的主要问题有（ 回溯 ）和（ （左递归带来的）无限循环 ）。
6、LL(k)分析法中，第一个L的含义是（ 从左到右进行分析 ），第二个L的含义是（ 每次进行最左推导 ），“k”的含义是（向输入串中查看K个输入符号 ）。
7、LL(1)分析法中，第一个L的含义是（从左到右进行分析 ），第二个L的含义是（每次进行最左推导 ），“1”的含义是（向输入串中查看1个输入符号 ）。
8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（ 直接推导 ），试图构造一个推导序列，最终由它推导出与输入符号相同的（ 符号串 ）。
9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（ 识别符号|开始符号 ）。
10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（ 采用最右推导的逆过程---最左归约 ），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。
11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。
12、SLR(1)分析法的名字中，“S”的含义是（简单的 ），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。
中间语言与语法制导翻译
重点与难点
重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。
三地址码，各种语句的目标代码结构、属性文法与翻译模式。
难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。
基本要求
掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现
掌握中间语言与语义分析的基本概念；熟练掌握语法（结构）树、三地址代码、赋值与控制语句的翻译、说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。
例题解析
例1 给定文法 E --> T { R.i := T.p }
R { E.p := R.s }
R --> addop
T { R1.i := mknode( addop.val, R.i, T.p ) }
R { R.s := R1.s }
R --> { R.s := R1.s }
T --> ( E ) { T.p := E.p }
T --> id { T.p := mkleaf( id, id.entry ) }
T --> num { T.p := mkleaf( num, num.val ) }
(1) 指出文法中的各非终结符具有哪些综合属性和哪些继承属性
⑵ 画出按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树
【解】
(1)E的综合属性 p，R的继承属性i，综合属性s；T的综合属性p
(2) 处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树如下
编译原理
第一章：
1．编译程序是现代计算机系统的基本组成部分之一
2．一个计算机系统中通常配置多个高级语言的编译程序
3．在一个计算机系统中可为某些高级语言配置多个不同性能的编译程序
4．编译程序是一种语言翻译程序，其功能是把一种语言编写的程序翻译成另一种语言的等价程序
5．被编译的程序称为源程序，编译后的等价程序称为目标程序
6．编译程序的任务就是将源语言程序翻译成等价的目标语言程序
7．通常将编译过程分为六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。
8．词法分析的主要任务是从左至右扫描字符序列，并按照此法规则识别出一个个的单词
9．单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。
10．计算机语言中，单词的种类通常有保留字、标识符、数、算符、界符等
11．语法分析的主要任务是：按照语言的语法规则，把词法分析所得的单词序列分解成各类语法成分。
12．词法分析和语法分析都是对源程序进行结构分析，但二者是有区别的。
13．语义分析的主要功能是审查源程序有无语义错误，伪代码生成阶段收集类型信息。
14．中间代码生成阶段的主要任务是，把源程序转换成一种中间代码
15．中间代码是一种结构简单、含义明确的记号系统
16．中间代码可以设计成多种形式，其设计原则有两点：一是容易生成，二是容易转换成目标代码
17．代码优化的主要任务是对中间代码进行改造，使生成的目标代码更为高效
18．目标代码生成阶段的任务是把中间代码转换成特定机器上的绝对指令代码或者可重定位的指令代码或者汇编指令代码
19．在编译过程的每个阶段中都含有出错处理和表格管理的工作
20．编译程序的结构可以按功能分为八个模块，即词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序，此外还有与上述每个阶段都有关系的出错处理程序和表格管理程序。
