编译原理复习

编译原理复习

一、选择

1、构造编译程序应掌握()

A.源程序B.目标文件C.编译方法D.以上三项2、编译程序绝大多数时间

花在()上

A.出错处理B.词法分析C.目标代码生成D.表格管理3、编译程序是对

()

A.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级

语言的翻译4、词法分析器的输出结果是()

A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值

D,单词自身值5、正规式Ml和M2等价是指()A.M1和M2的状态数相等B.M1

和M22的有向变条数相等C,M1和M2所识别的语言集相等D.M1和M2状态数和

有向边条数6、DFAM接受的字集为()A.以0开头的二进制数组成的集合B.以

0结尾的二进制数组成的集合C.含奇数个0的二进制数组成的集合D.含偶数个

0的二进制数组成的集合7、文法G[S]:S-某S某|y所识别的语言是()

A.某y某B.(某y某)某C.某ny某n(n20)D.某ny某n8、如果文法

G[S]是无二义的，则它的任何句子a()A.最左推导和最右推导对应的语法树

必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导

必定相同

D.可能存在两个不同的最左推导，但它们对应的语法树相同9、采用自顶

向下分析，必须()

A.消除左递归B.消除右递归C.消除回溯D.提取公共左因子10、设a、

b、c是文法的终结符，且满足有限关系a=b和b=c,则()A.必有a=cB.必

有©=@(1必有b=aD.a、c都不一定成立11、在规范规约中，用()开刻画可归

约串A.直接短语B.句柄C.最左素短语D.素短语12、若a为终结符，则

A-Q-a3为()项目A.规约B.移近C.接受D.待约

13^若项目集合Ik含有A—Q・，则在状态k时，仅当面临的输入符号

a£FOLLOW(A)时，才采取“Afa・”动作的一定是()

A.LALR文法B.LR(0)文法C.LR(1)文法D.SLR(l)文法14、同心集合并有

可能产生新的()冲突

A.指示器B.临时变量C.符号表D.程序变量16、间接三元式表示法的优点

为()

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

于优化处理，节省存储空间D.节省存储空间，不便于优化处理17、表达式

(-1AVB)A(CVD)的逆波兰表示为()

A.-|ABVACDVB.A-iBVCDVAC.ABVnCDVAD.A-|BVACDV18、过程的

DISPLAY表中记录了()

A.过程的连接数据B.过程的嵌套层次C.过程的返回地址D.过程的入口地

址19、过程P1调用P2是，连接数据不包含()

A.嵌套层次显示表B.老SP值C.返回地址D.全局DISPLAY表地址

20、堆式动态分配申请和释放存储空间遵守()原则

A.先请先放B.先请后放C.后请先放D.任意21、.栈式动态分配与管理在

过程返回时应做的工作有()

A.保护SPB.恢复SPC.保护TOPD.恢复TOP22、如果活动记录中没有

DISPLAY表,则说明()

A.程序中不允许有递归定义的过程B.程序中不允许有嵌套定义的过程

C.程序中不允许有嵌套定义的过程，也不允许有递归定义的过程D.程序

中允许有递归定义的过程，也允许有嵌套定义的过程23、优化可生成()的目

标代码

A.运行时间较短工占用存储空间较小

C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小24、下

列()优化方法不是针对循环优化进行的

A.强度削弱B.删除归纳变量C.删除多余运算D.代码外提25、基本块内的

优化为()

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

弱，代码外提D.循环展开，循环合并

26、在程序流图中，我们称具有下述性质()的节点序列为一个循环A.

它们是非连通的且只有一个入口结点B.它们是强连通的但有多个入口结点C.它

们是非连通的但有多个入口结点D.它们是强联通的且只有一个入口结点27、关

于必经结点的二元关系，下列叙述中不正确的是()

A.满足自反性B.满足传递性C.满足反对称性D.满足对称性28、有一语法

制导翻译如下：

S—bAb{print“1”}A—(B{print“2”}A-a{print"3”}BfAa){print

“4”}

若输入序列为b(((aa)a)a)b,且采用自底向上的分析方法，则输出序列为

()A.32224441B.34242421C.12424243D.344422：229、错误的局部化是()

A.把错误理解成局部的错误B.对错误在局部范围内进行纠结

C.当发现错误时，跳过错误所在的语法单位继续分析下去D.当发现错

误时立即停止编译，待用户改正错误后再继续编译二、填空

1、编译程序划分的类型2、编译程序是对—高级语言的翻译一

3、若文法是无二义的，则规范推导与规范归纳的关系4、词法分析程序

输出的单词符号通常表示成二元式的形式5、语言的目标是，是一个特殊的非

终结符6、描述语言L={ab|n2mNl}的文法为

7、程序语言的生成系统是，而识别系统贝!是8、语法分析器的功能是输

入输出9、两个自动机等价是指DFA和NFA

10、文法四元组G[S]:{VTVTS&}11、词法分析器的输出结果是12、语

法分析的方法种类13、文法符号的属性种类14、文法G所描述的语言是的集

合

15、为使编译程序能正确翻译，对程序设计语言必须使用的定义方法

16、LR语法分析法是指扫描输入串和进行规范归纳17、首节点是指从

它开始到控制流程图中任何一个结点都有一条通路的结点。18、生成中间代码

时所依据的是19、划分基本块的关键问题是准确定义入口和出口语句

20、错误的局部化是指当发现错误时，跳过错误所在的语法单位继续分析

下去21、基本块是指

22、基本块的优化方法，循环优化的方法23、优化可生成的目标代码

24、优化对象所涉及的范围，优化的分类

25、一个好的编译程序应具有较强的或能力。26、代码优化所遵循的原

则是程序的等价变换原则。

27、动态语义检查需要生成相应的目标代码，它是在运行时进行的。28、

编译生成的目标代码不可能是。

29、语法制导翻译。30、编译程序是将源程序成目标程序后再执行c

31、中间代码。32、编译模型的最后一个阶段是代码生成。

33、在编译程序的全过程中，都需对进行频繁地访问，耗费的时间占很

大比例三、简答

1.四类文法的关系与区别

答：由四类文法的定义可知，从0型文法到3型文法逐渐增加限制。03

型文法都属于0型文法，2、3型文法不一定属于1型文法（如果存在形如

A-§的产生式，则不属于1型文法），3型文法属于2型文法。

四类文法的区别如下：（1）1型文法中不允许有形如“A-§”的产生式

存在，而2、3型文法则允许形如“A-§”的产生式存在。（2）0、1型文法

的产生式左部

存在含有终结符号的符号串或两个以上的非终结符，而2型和3型文法的

产生式左部只允许是单个的非终结符号。2.中间弋码的优化原则答：等价原

则：

有效原则：合算原则：

源程序表格管理目标程序语义分析与中间代码生成器出词法分析器语法分

析器错处优化目标代码生成器理3.编译程序的结构（图）

4.解释程序与编译程序的区别

答：编译程序是将源程序翻译成目标程序后再执行该目标程序；而解释程

序则逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产

生目标程序。典型的解释型高级语言是BASIC语言。5.构造编译程序应掌握的

内容。

答：构造一个编译程序必须掌握下述三方面的内容：

⑴对被编译的源语言（如C、PASCAL等），要深刻理解其结构（语法）和

含义。

（2）必须对目标机器的硬件和指令系统有深刻的了解。

⑶必须熟练掌握编译方法，编译方法掌握的如何将直接影响到编译程序的

成败，一个好的编译方法可能得到事半功倍的效果。6.编译程序的工作过程。

答：编译程序的工作过程是指从输入源程序开始到输出目标程序为止的整

个过程。此过程是非常复杂的。一般来说，整个编译过程可以划分成五个阶

段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、优化阶段

和目标代码生成阶段。

7.堆式存储分配中需解决的问题。

答：对于堆式存储分配来说，需要解决两个问题：一是堆空间的分配，即

当运行程序需要一块空间时应分配哪一块给它；另一个问题是分配空间的回

收，由于返回堆的不同空间是按任意次序进行的，所以需要研究专门的回收分

配策略。

8.NFA和DFA的区别。

答：NFA和DFA的区别主要有两点：其一是NFA可以有若干个初始状态，

而DFA仅有一个初始状态；其二是NFA的状态转爽函数f不是单值函数，而是

一个多值函数，即f(i,a)=｛某些状态的集合｝(iES),它表示不能由当前状

态和当前输入字符唯一地确定下一个要转换的状态，也即允许同一个状态走同

一个输入字符可以有不同的输出边。四、计算

1.文件G[S]：S-aS|bS|a

构造LR(0)项目集规范族；给出识别活前缀的DFA；构造SLR(1)分析

表,判断是否为SLR(1)文法。

2.表达式(人+8某((>口))+E(C-D)不翻译成：逆波兰式、四元式、三元

式、间

接三元式。

3.程序：I=400J=200Ll：J=J+lreadI

ifI<5000gotoL2writeJhaltL2:1=1某1

gotoLl

画控制流程图：求各个结点的必经结点集；求回边：求循环。

4.文件G[S]：

S->(L)|aS|aLfL,S|S(l)(S,(a))最右推导,画语法树。

(