编译原理期末复习资料.doc

资源描述

编译原理期末复习资料.doc

《编译原理期末复习资料.doc》由会员分享，可在线阅读，更多相关《编译原理期末复习资料.doc（16页珍藏版）》请在冰点文库上搜索。

编译原理期末复习资料.doc

一、选择题

1．词法分析器的输出结果是__C___。

　A．单词的种别编码　　　　　　B．单词在符号表中的位置

　C．单词的种别编码和自身值　　D．单词自身值

2．正规式M1和M2等价是指__C___。

　A．M1和M2的状态数相等　　 B．M1和M2的有向边条数相等

　C．M1和M2所识别的语言集相等　　D．M1和M2状态数和有向边条数相等

3．文法G：

S→xSx|y所识别的语言是__C___。

　A．xyx 　B．（xyx）* C．xnyxn（n≥0） D．x*yx*

4．如果文法G是无二义的，则它的任何句子α__A___。

　A．最左推导和最右推导对应的语法树必定相同　　

　B．最左推导和最右推导对应的语法树可能不同　　

　C．最左推导和最右推导必定相同　　

　D．可能存在两个不同的最左推导，但它们对应的语法树相同

5．构造编译程序应掌握__D____。

　A．源程序　　　B．目标语言

C．编译方法 D．以上三项都是

6．四元式之间的联系是通过__B___实现的。

　A．指示器　　B．临时变量

　C．符号表 D．程序变量

7．表达式（┐A∨B）∧（C∨D）的逆波兰表示为___B__。

　A.┐AB∨∧CD∨　　　　B．A┐B∨CD∨∧

C．AB∨┐CD∨∧ D．A┐B∨∧CD∨

8.优化可生成__D___的目标代码。

　A．运行时间较短　　　 B．占用存储空间较小

　C．运行时间短但占用内存空间大　　　D．运行时间短且占用存储空间小

9．下列__C____优化方法不是针对循环优化进行的。

　A.强度削弱　　　B．删除归纳变量

　C．删除多余运算　　D．代码外提

10．编译程序使用__B___区别标识符的作用域。

　A.说明标识符的过程或函数名

　B．说明标识符的过程或函数的静态层次

　C．说明标识符的过程或函数的动态层次

　D.标识符的行号

1．语言是A

A．句子的集合B．产生式的集合

C．符号串的集合D．句型的集合

2．编译程序前三个阶段完成的工作是C

A．词法分析、语法分析和代码优化

B．代码生成、代码优化和词法分析

C．词法分析、语法分析、语义分析和中间代码生成

D．词法分析、语法分析和代码优化

3．一个句型中称为句柄的是该句型的最左D

A．非终结符号B．短语C．句子D．直接短语

4．下推自动机识别的语言是C

A．0型语言B．1型语言

C．2型语言D．3型语言

5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即B

A．字符B．单词C．句子D．句型

6．对应Chomsky四种文法的四种语言之间的关系是B

A．L0L1L2L3B．L3L2L1L0

C．L3=L2L1L0D．L0L1L2=L3

7．词法分析的任务是A

A．识别单词B．分析句子的含义

C．识别句子D．生成目标代码

8．常用的中间代码形式不含D

A．三元式B．四元式C．逆波兰式D．语法树

9．代码优化的目的是C

A．节省时间B．节省空间

C．节省时间和空间D．把编译程序进行等价交换

10．代码生成阶段的主要任务是C

A．把高级语言翻译成汇编语言

B．把高级语言翻译成机器语言

C．把中间代码变换成依赖具体机器的目标代码

D．把汇编语言翻译成机器语言

【D】1．____型文法也称为正规文法。

　　　[A]0[B]1[C]2[D]3

【D】2．____文法不是LL

（1）的。

　　[A]递归[B]右递归[C]2型[D]含有公共左因子的

【B】3．文法E→E+E|E*E|i的句子i*i+i*i的不同语法分析树的总数为______。

　　　[A]1[B]3[C]5[D]7

【A】4．四元式之间的联系是通过实现。

[A]临时变量[B]指示器[C]符号表[D]程序变量

【C】5．同心集合并可能会产生的新冲突为。

[A]二义[B]移进/移进[C]移进/归约[D]归约/归约

【C】6．代码优化时所依据的是。

[A]语法规则[B]词法规则[C]等价变换规则[D]语义规则

【B】7．表达式a-（-b）*c的逆波兰表示为。

[A]a-b@c*[B]ab@c*-[C]ab@-[D]ab@c-*（注：

@为单目减运算符）

【B】8．过程的DISPLAY表记录了。

[A]过程的连接数据[B]过程的嵌套层次

[C]过程的返回地址[D]过程的入口地址

1.一个上下文无关文法G包括四个组成部分：

一组终结符，一组非终结符，一个（C），以及一组（B）。

A．字符串B．产生式C．开始符号D．文法

2.程序的基本块是指（D）。

A．一个子程序B．一个仅有一个入口和一个出口的语句

C．一个没有嵌套的程序段D．一组顺序执行的程序段，仅有一个入口和一个出口

3.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（B）分析方法。

A．自左向右B．自顶向下C．自底向上D．自右向左

4．在通常的语法分析方法中，（A）特别适用于表达式的分析。

A．算符优先分析法B．LR分析法

C．递归下降分析法D．LL

（1）分析法

5．经过编译所得到的目标程序是（D）。

A．四元式序列B．间接三元式序列

C．二元式序列D．机器语言程序或汇编语言程序

6．一个文法所描述的语言是（A）；描述一个语言的文法是（C）。

A．唯一的B．不唯一的C．可能唯一，也可能不唯一

7．如果在文法G中存在一个句子，当其满足下列条件（BCD）之一时，则称该文法是二义文法。

A．其最左推导和最右推导相同B．该句子有两个不同的最左推导

C．该句子有两个不同的最右推导D．该句子有两棵不同的语法树

E．该句子对应的语法树唯一

8．下面（BCD）语法制导翻译中，采用拉链—回填技术。

A.赋值语句B.布尔表达式的计算C.条件语句D.循环语句

1.设有文法G[I]：

I→I1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（B）。

①ab0②a0c01③aaa④bc10

可选项有：

A．①B．②③④C．③④D．①②③④

5．运行阶段的存储组织与管理的目的是（C）。

①提高编译程序的运行速度②节省编译程序的存储空间

③提高目标程序的运行速度④为运行阶段的存储分配做准备

可选项有：

A.①②B.②③C.③④D.④②

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.词法分析器的输出结果是_c___。

a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值

6.中间代码生成时所依据的是—c。

a.语法规则b．词法规则c．语义规则d．等价变换规则

7.,后缀式ab+cd+/可用表达式__b_来表示。

a.a+b/c+d b．（a+b）/（c+d） c．a+b/（c+d） d．a+b+c/d

8.程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。

a.动态存储b.栈式存储c.静态存储d.堆式存储

9.堆式动态分配申请和释放存储空间遵守___d____＿原则。

a.先请先放b.先请后放c.后请先放d.任意

1．一个编译程序中，不仅包含词法分析，__A___，中间代码生成，代码优化，目标代码生成等五个部分。

A．语法分析B．文法分析C．语言分析D．解释分析

2．词法分析器用于识别__C___。

A．字符串B．语句C．单词D．标识符

3．语法分析器则可以发现源程序中的__D___。

A．语义错误B．语法和语义错误C．错误并校正D．语法错误

4．下面关于解释程序的描述正确的是__B___。

（1）解释程序的特点是处理程序时不产生目标代码

（2）解释程序适用于COBOL和FORTRAN语言（3）解释程序是为打开编译程序技术的僵局而开发的

A．

（1）

（2）B．

（1）C．

（1）

（2）（3）D．

（2）（3）

5．解释程序处理语言时,大多数采用的是__B___方法。

A．源程序命令被逐个直接解释执行B．先将源程序转化为中间代码,再解释执行

C．先将源程序解释转化为目标程序,再执行D．以上方法都可以

6．编译过程中,语法分析器的任务就是__B___。

（1）分析单词是怎样构成的

（2）分析单词串是如何构成语句和说明的（3）分析语句和说明是如何构成程序的（4）分析程序的结构

A．

（2）（3）B．

（2）（3）（4）C．

（1）

（2）（3）D．

（1）

（2）（3）（4）

7．编译程序是一种___C__。

A.汇编程序B．翻译程序C．解释程序D．目标程序

8．文法G所描述的语言是__C___的集合。

A.文法G的字母表V中所有符号组成的符号串

B．文法G的字母表V的闭包V*中的所有符号串

C．由文法的开始符号推出的所有终极符串

D.由文法的开始符号推出的所有符号串

9．文法分为四种类型，即0型、1型、2型、3型。

其中3型文法是__B___。

A.短语文法B．正则文法C．上下文有关文法D．上下文无关文法

1．文法G产生的__D___的全体是该文法描述的语言。

A．句型B．终结符集C．非终结符集D．句子

2．若文法G定义的语言是无限集，则文法必然是_A____。

A．递归的B．前后文无关的C．二义性的D．无二义性的

3．四种形式语言文法中，1型文法又称为___C__文法。

A．短语结构文法B．前后文无关文法C．前后文有关文法D．正规文法

5．__B___和代码优化部分不是每个编译程序都必需的。

A．语法分析B．中间代码生成C．词法分析D．目标代码生成

6．__B___是两类程序语言处理程序。

A．高级语言程序和低级语言程序 B．解释程序和编译程序

C．编译程序和操作系统 D．系统程序和应用程序

7．数组的内情向量中肯定不含有数组的__A___的信息。

A.维数B．类型C．维上下界D．各维的界差

9．文法分为四种类型，即0型、1型、2型、3型。

其中2型文法是__D___。

A.短语文法B．正则文法C．上下文有关文法D．上下文无关文法

4．__A___是一种典型的解释型语言。

A．BASIC B．C C．FORTRAN D．PASCAL

5．与编译系统相比，解释系统__D___。

A．比较简单,可移植性好,执行速度快B．比较复杂,可移植性好,执行速度快

C．比较简单,可移植性差,执行速度慢D．比较简单,可移植性好,执行速度慢

6．用高级语言编写的程序经编译后产生的程序叫__B___。

A．源程序B．目标程序C．连接程序D．解释程序

8．编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过__B___这几步:

（1）编辑

（2）编译（3）连接（4）运行

（1）

（2）（3）（4） B．

（1）

（2）（3） C．

（1）（3） D．

（1）（4）

9．把汇编语言程序翻译成机器可执行的目标程序的工作是由__B___完成的。

A．编译器B．汇编器C．解释器D．预处理器

2．编译程序是对_D____。

A．汇编程序的翻译 B．高级语言程序的解释执行

C．机器语言的执行 D．高级语言的翻译

3．采用自上而下分析，必须__C___。

A．消除左递归B．消除右递归C．消除回溯D．提取公共左因子

4．在规范归约中，用__B___来刻画可归约串。

A．直接短语B．句柄C．最左素短语D．素短语

5．若a为终结符，则A->α·aβ为__B___项目。

A．归约B．移进C．接受D．待约

6．间接三元式表示法的优点为_A____。

A．采用间接码表，便于优化处理 B．节省存储空间，不便于表的修改

C．便于优化处理，节省存储空间 D．节省存储空间，不便于优化处理

7．基本块内的优化为__B___。

A.代码外提，删除归纳变量 B．删除多余运算，删除无用赋值

C．强度削弱，代码外提 D．循环展开，循环合并

8.在目标代码生成阶段，符号表用__D___。

A．目标代码生成B．语义检查C．语法检查D．地址分配

9．若项目集Ik含有A->α·，则在状态k时，仅当面临的输入符号a∈FOLLOW（A）时，才采取“A->α·”动作的一定是__D___。

A.LALR文法B．LR（0）文法C．LR

（1）文法D．SLR

（1）文法

10．堆式动态分配申请和释放存储空间遵守__D___原则。

A.先请先放B．先请后放C．后请先放D.任意

二、简答题

1、正规表达式定义P18

2、上下文无关文法定义P39

①VT是一个非空有限集合，其元素称为终结符。

②VN是一个非空有限集合，其元素称为非终结符，并有VT∩VN=非空

③S是一个非终结符，称为开始符号。

④P是产生式的有限集合。

3、分离词法分析器的理由P44

①语言的词法规则简单，不必用功能更强的上下文无关文法描述它；

②对于词法记号，正规式给出的描述比上下文无关文法给出的更简洁且易于理解；

③从正规式自动构造出的词法分析器比从上下文无关文法构造出的更有效；

④编译器的效率会改进；

⑤编译器的可移植性加强；

⑥把语言的语法结构分成词法和非词法两部分，为编译器前端的模块划分提供了方便的途径。

4、LR分析器富有吸引力的原因P71

①LR分析器能够被构造来识别所有能用上下文无关文法写出的编程语言构造。

②LR分析方法是已知的最一般的无回溯的移进－归约方法，它能和其他移进－归约方

法一样有效地实现。

③LR方法能分析的文法类是预测分析法或者说LL方法能分析的文法类的直超集。

④在自左向右扫描输入的前提下，LR分析器尽可能快地发现语法错误。

5、语法制导定义的形式P107

综合属性：

如果b是A的属性，c1，c2，····，ck是产生式右部文法符号的属性或A的其他属性，那么b称为A的综合属性。

继承属性：

如果b是产生式右部某个文法符号X的属性，c1，c2，···，ck是A的属性或右部文法符号的属性，那么b称为X的继承属性。

S属性定义：

仅仅使用综合属性的语法制导定义称为S属性定义。

注释分析树：

每个结点的属性值都标注出来的分析树。

依赖图：

分析树结点的属性之间的互相依赖可以用依赖图的有向图来描绘。

6、翻译方案设计原则P117

①产生式右部符号的继承属性必须在先于这个符号的动作中计算。

②一个动作不能引用该动作右边符号的综合属性。

③左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算。

④只有综合属性的情况最简单。

7、活动记录结构P166

①临时数据；保存临时值。

②局部数据；保存过程的局部数据。

③保存的机器状态；保存刚好在过程调用前的机器状态信息，包括返回地址及调用过

程使用并且在返回时必须恢复的寄存器的内容。

④访问链；有些语言需要通过访问链来访问非局部数据。

⑤控制链；用来指向调用者的活动记录。

⑥参数；调用过程提供的实在参数，由被调用过程使用。

⑦返回值。

用于存放被调用过程返回给调用过程的值。

8、活动记录设计布局原则P171

①调用者和被调用者之间交流的数据一般放在被调用者活动纪录的开始处，并尽可能

靠近调用者的活动纪录。

②固定长度的项通常放在活动纪录的中间，一般包括控制链、访问链和机器状态链。

③在编译时不能及时知道大小的一些项放在活动纪录的末端。

9、参数传递的方法和特点P180

①值调用。

值调用是最简单的传递参数的方法。

调用者计算实参，并把它的值（右值）

传给被调用过程。

②引用调用。

调用者把实参存储单元的地址（即实参的左值）传给被调用者，被调用

者对形参的任何访问就是对对应实参的访问。

③换名调用。

P181

10、使用独立于机器的中间形式的好处P199

①再目标比较容易。

把针对新机器的后端加到现成的前端上，可以得到另一种机器的

编译器。

②独立于机器的代码优化器可用于这种中间表示。

三、应用题

状态转换图（有穷状态自动机）：

：

1、（a|b）*（aa|bb）（a|b）*画出状态转换图。

①1,2,3

2,3,4

2,3,5

②2,3,4

2,3,4,6,7,8

2,3,5

③2,3,5

2,3,4

2,,3,5,6,7,8

④2,3,4,6,7,8

2,3,4,6,7,8

2,3,5,7,8

⑤2,3,5,6,7,8

2,3,4,7,8

2,3,5,6,7,8

⑥2,3,5,7,8

2,3,4,7,8

2,3,5,6,7,8

⑦2,3,4,7,8

2,3,4,6,7,8

2,3,5,7,8

新的状态转换图如下：

（1）A={1,2,3}，B={4,5,6,7}Aa={2,4}×

（2）A={1,3}，B={2}，C={4,5,6,7}Aa={2}B，Ab={3,5}×

（3）A={1}，B={2}，C={3},D={4,5,6,7}（单元素可以不用看，必有，古先看D）

Da={4,7}D，Db={5,6}D，Aa={2}B，Ab={3}C，Ba={4}D，Bb={3}C，Ca={2}B，Cb={5}C，则有

2、（a*|b*）b（ba）*的状态转换图。

①1,2,3,4

2,4

3,4,5,6,8

②2,4

2,4

5,6,8

③3,4,5,6,8

---

3,4,5,6,7,8

④5,6,8

---

⑤3,4,5,6,7,8

6,8

3,4,5,6,7,8

⑥7

6,8

---

⑦6,8

---

新的状态转换图如下：

化简：

（用终结状态与非终结状态，然后输出状态一致分一类）。

（1）A={1,2,6}，B={3,4,5,7}Aa={2}×

（2）A={1,2}，B={6}，C={3,4,7}，D={5}Cb={5,6}×（只要有一个不属于任何一个集合，就不行）

（3）A

展开阅读全文