编译原理-期末复习.doc

编译原理
一、单选题
1、将编译程序分为若干个“遍”是为了（）。B
A. 提高程序的执行效率
B. 使程序的结构更加清晰
C. 利用有限的机器内存并提高机器的执行效率
D. 利用有限的机器内存但降低了机器的执行效率

2、构造编译程序应掌握（）。D
A. 源程序 B.目标语言
C.编译方法 D.以上三项都是

3、变量应当（）。C
A. 持有左值
B. 持有右值
C. 既持有左值又持有右值
D. 既不持有左值也不持有右值

4、编译程序绝大多数时间花在（）上。D
A. 出错处理 B.词法分析
C.目标代码生成 D.管理表格

5、（）不可能是目标代码。D
A. 汇编指令代码 B.可重定位指令代码
C.绝对指令代码 D.中间代码

6、 编译程序是对（）。D
A. 汇编程序的翻译 B.高级语言程序的解释执行
C.机器语言的执行 D.高级语言的翻译

7、 正规式M1和M2等价是指（）。C
A. M1和M2的状态数相等 B.M1和M2的有象弧条数相等
C.M1和M2所识别的语言集相等 D.M1和M2状态数和有象弧条数相等

8、 如果文法G是无二义的，则它的任何句子（）。A
A. 最左推导和最右推导对应的语法树必定相同。
B. 最左推导和最右推导对应的语法树可能相同。
C. 最左推导和最右推导必定相同。
D. 可能存在两个不同的最左推导，但它们对应的语法树相同。

9、 文法G：S→S+T|T
T→T*P|P
P→(S)|i
句型P+T+i的短语有（）B
A. i，P+T B. P，P+T，i，P+T +i
B.P+T + i D. P，P+T，i

10、 产生正规语言的文法为（）。D
A.0型 B.1型 C.2型 D.3型

11、 文法G：S→b|˄|(T)
T→T˅S|S
则FIRSTVT(T)=() C
A. {b，˄，(} B.{b，˄，)}
C.{b，˄，(，˅} D.{b，˄，)，˅}

12、 给定文法：A→bA | cc，下面的符号串中，为该文法句子的是（）。 A
cc ‚bcbc ƒbcbcc ④bccbcc ⑤bbbcc
可选项有：
A.  B.ƒ④⑤ C.④ D.④⑤

13、 采用自上而下分析，必须（）。C
A. 消除左递归 B.消除右递归
C.消除回溯 D.提取公共左因子

14、 由文法的开始符经0步或多步推导产生的文法符号序列是（）。C
A. 短语 B.句柄 C.句型 D.句子

15、 后缀式ab+cd+/可用表达式（）来表示。 B
A. a+b/c+d B.(a+b)/(c+d)
C.a+b/(c+d) D.a+b+c/d

16、 语法分析器则可以发现源程序中的（）。D
A. 语义错误 B.语法和语义错误
C.错误并矫正 D.语法错误

17、 在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是（）。B
A. 非终极符集 B.终极符集
D.字母表 D.状态集
18、四种形式语言文法中，1型文法又称为（）。C
A. 短语结构文法 B.前后文无关文法
C.前后文有关文法 D.正规文法

19、 优化可生成（）的目标代码。D
A. 运行时间较短 B.占用存储空间较小
C.运行时间短但占用内存空间大 D.运行时间短且占用内存空间小

20、四元式之间的联系是通过（）实现的。B
A. 指示器 B.临时变量
C.符号表 D.程序变量
二、 多选题
1、如果在文法G中存在一个句子，当其满足下列条件（ BCD ）之一时，则称该文法是二义文法。
A.其最左推导和最右推导相同  
B.该句子有两个不同的最左推导
C.该句子有两个不同的最右推导 
D.该句子有两棵不同的语法树
E.该句子对应的语法树唯一
2、下面（BCD）语法制导翻译中，采用拉链—回填技术。
A、赋值语句    B、布尔表达式的计算 
C、条件语句   D、循环语句
3、一般程序设计语言的定义都涉及到（ ABC ）3个方面。
A、 语法 B、语义 C、语用 D、程序基本符号的确定
4、程序语言一般分为（ A ）和（ B ）。
A高级语言 B低级语言 C专用程序语言 D通用程序语言
5、编译程序工作时，通常有（ABCD ）阶段。
A、词法分析 B、语法分析 C、中间代码生成 D、语义检查 E、目标代码生成
6、编译过程中，语法分析的任务是（ BCD ）。
A、分析单词是怎样构成的   B、分析单词是如何构成语句和说明的
C、分析语句和说明是如何构成程序的 D、分析程序的结构
7、语法分析的常用方法有 （ AB ）。
A、自顶向下 B、自底向上 C、自左向右 D、自右向左   
8、程序设计语言常见的数据类型有：（ABCD） 
A、数值型数据 B、逻辑数据 C、字符数据 D、指针类型
9、构造编译程序应掌握（ABC）。
A、源程序 B、目标语言   C、编译方法 D、以上都不是
10、编译程序前三个阶段完成的工作是（ABC）
A、词法分析 B、语法分析
C、语义分析和中间代码生成 D、代码优化
11、一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，以及（BC）。
A、一组字符串 B、一组产生式 C、一个开始符号 D一个文法
12、描述一个语言的文法是（C、D）。
 A、唯一的 B、不唯一的  C、可能唯一 D、也可能不唯一
13、设有文法G[I]：I→I1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（BCD）。
A、ab0   B、a0c01   C、aaa     D、bc10 
14、运行阶段的存储组织与管理的目的是（CD）。
A、提高编译程序的运行速度 B、节省编译程序的存储空间
C、提高目标程序的运行速度 D、为运行阶段的存储分配做准备

15、已知文法G[E]：E→TE’ E’→+TE’∣ε  T→FT’  T’→*FT’∣ε  F→（E）∣id 求：FOLLOW（F）=（ D ），FIRST（T’）=（ B ）
A、｛*，+｝ B、｛*，ε｝ C、｛+,#，）｝
D、｛*，+，#，）｝ E、｛#，）｝ F、｛*，+，#，id｝
16、面向机器语言的特点是（ ABC  ）。
A、程序的执行效率高 B、编制效率低
C、可读性差 D、可读性强
17、编译程序使用（ AB ）区别标识符的作用域。
A、说明标识符的过程 B、函数的静态层次

C、函数的动态层次 D、标识符的行号
18、词法分析器的输出结果是（ AD ）
 A、单词的种别编码
 B、单词在符号表中的位置
 C、单词的长度
 D、单词自身值
19、优化可生成（ AD ）的目标代码。
 A、运行时间较短 B、占用存储空间较大
 C、运行时间短且占用内存空间大  D、占用存储空间小
22、编译程序各阶段的工作都涉及到（ BC ）
 A、语法分析 B、表格管理 C、出错处理 D、语义分析 F、词法分析
三、 填空题
1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码 生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和 ___出错处理__。  
2．若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序, 则其翻译程序称为 ___编译程序__ 。  

3．编译方式与解释方式的根本区别在于__是否生成目标代码___。  

4．对编译程序而言,输入数据是___源程序__, 输出结果是__目标程序___。 

5．产生式是用于定义___语法成分__的一种书写规则。  

6．语法分析最常用的两类方法是___自上而下__和___自下而上__分析法 

7．设 G 是一个给定的文法，S 是文法的开始符号，如果 S->x( 其中 x∈VT*), 则称 x 是文 法的一个__句子___。 

8．递归下降法不允许任一非终极符是直接__左___递归的。 

9.常用的参数传递方式有___传地址__，传值和传名。  

10．在使用高级语言编程时,首先可通过编译程序发现源程序的全部__语法___错误和语义的部分错误。

 11．一个句型中的最左简单短语称为该句型的___句柄_。  

12．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、 代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。 

13． 从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。   

14．语法分析是依据语言的__语法___规则进行的，中间代码产生是依据语言的__语义___规 进行的。 
 15．产生式是用于定义___语法成分__的一种书写规则。

16．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。 

17．局部优化是在__基本块___范围内进行的一种优化。 

18．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。  

19．语法分析基于__上下文无关___文法进行，即识别的是该类文法的句子。语法分析的有效 工具是__语法树___。  

20．一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有___递归 __定义的规则。 
四、名词解释
（1）2型文法（上下文无关文法）
若文法G=（VN，VT，P，S）中的每一条规则的形式为A→β，其中A∈VN，β∈(VN∪VT)*，则称G是2型文法。

（2） 二义性文法
如果一个文法存在某个句子对应两课不同的语法树，则称这个文法是二义性文法。
（3） 有穷自动机
是具有离散输入与输出系统的一种抽象数学模型。
（4） 算符文法
设有文法G，若G中没有形如U→…VW…的规则，其中V和W为非终结符，则称G为算符文法。

（5） 素短语
素短语是指这样一种短语，它至少包含一个终结符，并且除自身之外，不再包含其他任何更小的素短语。
（6） 语法制导翻译法
在语法分析过程中，根据相应文法的每一规则所对应的语义子程序进行翻译的方法。
（7） 基本块
指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。

（8） 句柄
一个句型的最左直接短语称为该句型的句柄。
（9） 待用信息
如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。
（10） 局部优化
局限于基本块范围的优化称。
五、 应用题
1. 编译过程的5个阶段是什么？
第1阶段：词法分析
第2阶段：语法分析
第3阶段: 词义分析与中间代码产生
第4阶段：代码优化
第5阶段：目标代码生成

2. 请给出编译程序的结构框图。

3. 设有文法G[A]:
A—>a|b|e|Aa|Ae|A0|A1
（1）试问VT 和VN是由哪些符号组成的？
VN={A}
VT={a,b,e,0,1}
（2）下列符号串a,ab0,a0e01,0a,11,eee是否为该文法的句子？
a,a0e01,eee是该文法句子。
4. 证明下面的文法是二义性的。
S—>iSeS|iS|i

5.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？
目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。 
应着重考虑的问题： 
(1)如何使生成的目标代码较短； (2)如何充分利用寄存器，以减少访问内存次数；  (3)如何充分利用指令系统的特点。
6.基本的优化方法有哪几种？
删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。
7.构造下列正规式相应的DFA（用状态转换图表示）
（1）1（0|1）*1
（2）0*10*10*10*1
（3）letter(letter|digit)*

8.给出下述文法所对应的正规式。
S—>aA
A—>bA|aB|b
B—>aA
对应的正规式为：R=a(b|aa)*b
解析：

9.给出文法G[S],构造相应最小的DFA
S—>aS|bA|b
A—>aS

10.给出下述文法所对应的正规式：
S—>0A|1B
A—>1S|1
B—>0S|0
根据正规文法转换成正规式的方法，首先给出该正规文法对应的正规式方程组：
S=0A+1B （1）
A=1S+1 （2）
B=0S+0 （3）
将（2）（3）式代入（1）式得
S=01S+01+10S+10 （4）
对（4）式使用求解规则得
S=（01|10）（01|10）*
即正规文法所生成语言的正规式是（01|10）（01|10）*。