编译原理试题.docx
《编译原理试题.docx》由会员分享，可在线阅读，更多相关《编译原理试题.docx（11页珍藏版）》请在冰点文库上搜索。
编译原理试题
编译原理题库
一、选择题：
1.编译原理是对（C）。
A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行
2.编译程序是将高级语言程序翻译成D。
A、汇编语言程序B、机器语言程序C、高级语言程序D、汇编语言或机器语言程序
3.文法：
G：
S→xSx|y所识别的语言是（D）。
A、xnyxmB、（xyx）*C、x*yx*D、xnyxm（n≥0）
4.设有文法G[I]：
I→I0|I1|Ia|Ic|a|b|c
下列符号串中是该文法的句子的有B。
①ab0②a0c01③aaa④bc10
可选项有A、①B、②③④C、③④D、①②③④
5.词法分析器的输出结果是（C）。
A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值
6.为了使编译程序能够对程序设计语言进行正确的翻译，必须采用_C_方法定义程序设计语言。
A、非形式化B、自然语言描述问题C、形式化D、自然语言和符号体系相结合
7.若文法G定义的语言是无限集，则文法必然是（C）A.前后文无关文法B.正规文法C.二义性文法D.递归文法
8、描述一个语言的文法是B。
A、唯一的B、不唯一的C、个数有限的
9、表达式（a+b）*c的逆波兰表示为_C_A、ab+c*B、abc+*C、a*c+b*c
10、递归下降分析法和预测分析法要求描述语言的文法是_C_A、正规文法B、ＬＲ（１）文法Ｃ、LL
（1）文法D、右线性文法
11编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过_A_这几步①编辑②编译③连接④运行
A、①②③④B、①②③C、①③D、①④
12、符号表的查找一般可以使用_B_：
①顺序查找②折半查找③杂凑查找④排序查找
可选项有：
A、①②③④B、①②C、③④D、①②③
13、语法分析的常用方法是B：
①自顶向下②自底向上③自左向右④自右向左可选项有：
A、①②③④B、①②C、③④D、①②③
14、LR语法分析栈中存放的状态是识别文法规范句型_A_的DFA状态。
A、前缀B、活前缀C、项目D、句柄
15、一个确定的有穷自动机DFA是一个A_A、五元组（K，∑，f,Ｓ，Ｚ）Ｂ、四元组（VN，VT，P，S）
Ｃ、四元组（Ｋ，f,S，Z）D、三元组（VN，VT，P）
16、设有文法G[E]:
E→E+T∣T
T→T*F∣F
F→（E）∣a
句型T+T*F+a的素短语是_A_
A、aB、E+TC、TD、T+T*F
17递归下降分析方法属于_B_A,自左至右B,自顶向下C,自底向上D,自右向左
18、文法的二义性和语言的二义性是两个_A_概念。
A、不同B、相同C、无法判断
19、编译过程中，词法分析阶段的任务是_B_A、识别表达式B、识别语言单词C、识别语句D、识别程序
20、无符号常数的识别和评数工作，通常都在B_阶段完成。
A、词法分析B、语法分析C、语义分析D、目标代码生成
21、编译程序中安排优化的目的是为了得到_C_的目标代码A、结构清晰B、较短C、高效率D、使用存储空间最小
22、代码优化的主要目标是_B_。
①如何提高目标程序的运行速度
②如何减少目标程序运行所需的空间。
③如何协调①和②
④如何使生成的目标代码尽可能简短
可选项有：
A、②④B、①②③C、③④①D、②③④
23、后缀式iii-/↑的中缀表达式是_A_A、i↑（i/（i-i））B、（i-i）/i↑iC、i↑（i-i）/ID、（i-i）↑i/i
24字母表中的元素可以是_D_A、字母B、字母和数字C、数字D、字母、数字和其他符号
25、编译过程中，比较常见的中间语言有_D_。
①波兰表示
②逆波兰表示
③三元式
④四元式
⑤树形表示
可选项有：
A、①③④B、②③④C、③④①⑤D、②③④⑤
26、正规式（a∣b）（a∣b∣0∣1）*对应的文法为_C_
A、S→aA∣bAB、S→aA∣bA
A→aA∣1A∣
A→aA∣bA∣0A∣1A
C、S→aA∣bAD、S→aA∣bA
A→aA∣bA∣0A∣1A∣
A→A∣bA∣0A∣1A∣
27、在规则产生式中，符号“∣”表示_B_A、与B、或C、非D、引导开关参数
28、循环优化是对_A_中的代码进行优化。
A、循环B、函数C、基本块D、整个程序
29、设有文法G[I]：
I→I0|I1|Ia|Ic|a|b
下列符号串中是该文法的句子的有_B_。
①ab0②a0c01③aaa④cb10
可选项有A、①B、②③C、③④D、①②③④
30、为了使编译程序能够对程序设计语言进行正确的翻译，必须采用_C_方法定义程序设计语言。
A、非形式化B、自然语言描述问题C、形式化D、自然语言和符号体系相结合
31、无符号常数的识别和评数工作，通常都在_B_阶段完成。
A、词法分析B、语法分析C、语义分析D、目标代码生成
32、递归下降分析法和预测分析法要求描述语言的文法是_C_
A、正规文法B、ＬＲ（１）文法 Ｃ、LL
（1）文法D、右线性文法
33、表达式a*（-b+c）的逆波兰表示为__A_______
A、ab＠c+*B、abc＠+*C、ab＠*+ac
34、文法的二义性和语言的二义性是两个_A_概念。
A、不同B、相同C、无法判断
35、设有文法G[E]:
E→E+T∣T
T→T*F∣F
F→（E）∣a
句型T+T*F+a的素短语是_A_
A、T*FB、E+TC、TD、T+T*F
36字母表中的元素可以是_D_A、字母B、字母和数字C、数字D、字母、数字和其他符号
37、编译过程中，比较常见的中间语言有_D_。
①波兰表示
②逆波兰表示
③三元式
④四元式
⑤树形表示
可选项有：
A、①③④B、②③④C、③④①⑤D、②③④⑤
38、正规式（a∣b）（a∣b∣0∣1）*对应的文法为__C
A、S→aA∣bAB、S→aA∣bA
A→aA∣1A∣
A→aA∣bA∣0A∣1A
C、S→aA∣bAD、S→aA∣bA
A→aA∣bA∣0A∣1A∣
A→A∣bA∣0A∣1A∣
39、在规则产生式中，符号“→”表示_D_A、恒等于B、等于C、取决于D、定义为
40、关于短语与句柄，正确的论述是：
B
A、短语就是句柄
B、直接短语才可能是句柄
C、左短语一定是句柄
D、最右短语一定是句柄
二、判断题（对下列叙述中正确的说法，在题后括号内打“√”，错误的打“×”，）
1、编译程序是一种常用的应用软件。
（× ）
2、名字就是标识符，标识符就是名字。
（ × ）
3、编译程序与具体的语言无关。
（√ ）
4、C语言的编译程序可以用C语言来编写。
（√ ）
5、一个语言的文法是唯一的。
（×）
2、数组元素的地址计算与数组的存储方式有关。
（√）
6、无左递归的文法是ＬＬ（１）文法。
（ × ）
7、含有优化部分的编译程序的执行效率高。
（×）
8、若两个正规式所表示的正规集相同，则认为二者是等价的。
（√）
9、算符优先关系表不一定存在对应的优先函数。
（×）
10、仅考虑一个基本块，不能确定一个赋值是否真是无用的。
（×）
11、每个文法都能改写为LL
（1）文法。
（×）
二、填空题
1、编译程序的工作过程一般主要可以划分为词法分析语法分析语义分析中间代码生成中间代码优化目标代码生成。
_等几个基本阶段。
2、语法分析的任务是：
依据语言的__语法规则_，逐一地分析词法分析时得到的__单词符号_，以确定它们是怎样组成说明和语句的，以及说明和语句是怎样组成__语法___________的。
如无语法错误，则给出正确的__语法单位___________。
3、代码优化是_对程序进行等价变换_，提高目标程序的质量。
即：
使目标代码运行时所需的时间尽可能___短__________，所占用的存储空间尽可能____少_________。
4、Chomsky定义的四种形式语言文法分别为：
___0型___文法（又称为__短语___________文法）、____1型_________文法（又称为__上下文有关___________文法）、_____2型________文法（又称为_上下文无关文法）、____3型_________文法（又称为__正规（或正则）___________文法）。
5、在代码优化阶段，优化的主要方法有：
局部优化、循环优化、全局优化_。
6、扫描器的任务是从_源程序_中识别出一个个_单词符号_。
7、所谓最右推导是指：
_任何一步α⇒β都是对α中最右非终结符进行替换的_。
8、语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。
9、一个上下文无关文法所含四个组成部分是一组终结符、一组非终结符、一个开始符号、一组产生式_。
10、所谓语法制导翻译方法是__为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序__。
11、符号表中的信息栏中登记了每个名字的有关的性质，如_类型、种属、所占单元大小、地址_等等。
12、一个过程相应的DISPLAY表的内容为现行的活动记录的地址和所有外出最新活动的记录地址。
13、常用的两种动态存贮分配办法是栈式动态分配和堆式动态分配。
14、产生式是用于定义_语法范畴_的一种书写规则。
15、一般程序语言的语法单位有：
表达式 、 语句 、 分程序 、和函数、过程、程序等等。
16、语法分析器的任务是 在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则 。
17、若源语言用高级语言编写的，目标程序是_等价的机器语言程序或汇编程序，则其翻译程序称为编译程序。
18、高级语言经过编译生成的目标程序一般是_机器语言程序或__汇编语言程序_
19、一个高级语言的源程序在编写形成后到正式运行前，一般要经过编辑、编译、连接这三个阶段
20、假设G是一个文法，S是文法的开始符号，如果S⇒*X，则称X是句型
三、名词解释：
（每题5分，共20分）
1、非终结符—出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。
2、终结符——出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。
3、语法制导翻译——语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。
4．编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序
5．扫描遍——指编译程序对源程序或中间代码程序从头到尾扫描一次。
6．自上而下分析法就是指从文法的开始符号出发，根据文法规则正向推导出给定句子的一种方法。
7．句柄——给定句型中的最左简单短语就是句柄
8．上下文无关文法——若文法G=（VN，VT，P，S）中的每一条规则的形式为A→
，其中A∈VN，
∈（VN∪VT），则称其为上下文无关文法
9．活前缀——规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
或给定文法规范句型的可归前缀的任意首部。
4、简答
1、何谓二义性文法？
试举例说明。
答：
若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。
产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。
例子：
给定文法G[]:
→*||a|b
考察句子ab*，它有两棵不同的推导树，如下所示：
2、设G=（VN,VT,P,）是上下文无关文法，产生式集合P中任意一个产生式应具有一个什么样的形式？
若G是正规文法呢？
答：
一般形式为→α,∈VN,α∈（VN∪VT）*若G是正则文法，则一般形式为→α,或→α,,∈VN,a∈VT（或→a,→a）
3,编译过程的5个阶段是什么？
答：
编译过程的5个阶段：
词法分析，语法分析，语义分析及中间代码生成，代码优化，目标代码生成。
4，常见的存储分配策略有几种？
它们都适合于什么性质的语言？
答：
有三种分配存储空间的方式：
（1）静态分配，若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。
适合静态管理的语言应具备条件：
数组上下界是常数过程调用不允许递归，不允许动态建立数据实体。
（2）栈式分配：
适用于允许递归调用的程序设计语言。
（3）堆式分配：
对于允许程序在运行时为变量，动态申请和释放存储空间的语言，采用堆式分配，是最有效的解决方案。
5，设有文法G[E]:
E→E+T▏E-T▏T
T→T*F▏T▏F▏F
F→（E）▏I试证明E+T*F是它的一个句型，指出这个句型的所有短语，直接短语和句柄。
答：
因为E→E+T→E+T*F,所以E+T*F是文法G[E]的句型。
短语：
E+T*F,T*F,其中T*F是直接短语，也是句柄。
6，在一个基本块内通常可以实现哪些优化？
答：
（1）合并已知量
（2）删除公共表达式（3）删除无用代码（4）复写传播（5）循环优化
7，设有文法G[A]
A→BCc▏gDB
B→bCDE▏ε
C→DaB▏ca
D→dD▏ε
E→gAf▏c
计算该文法的每一个非终结符的FIRST集和FOLLOW集。
答：
文法的每一个非终结符的FIRST集和FOLLOW集如下：
FIRST（A）=FIRST（BCc）∪FIRST（gDB）
=FIRST（B）∪FIRST（C）∪{c}∪{g}
={b}∪FIRST（D）∪{a}∪{c,g}
={a,b,c,d,g}
FIRST（B）=FIRST（bCDE）∪{ε}
={b,ε}
FIRST（C）=FIRST（DaB）∪FIRST（ca）
=FIRST（D）∪{a}∪{c}
={a,c,d}
FIRST（D）=FIRST（dD）∪{ε}
={d,ε}
FIRST（E）=FIRST（gAf）∪{c}
={g,c}
FOLLOW（A）={f,＄}
FOLLOW（B）={a,c,d,f,g,＄}
FOLLOW（C）={c,d,g}
FOLLOW（D）={a,b,c,g,f,＄}
FOLLOW（E）={a,c,d,f,g,＄}
8,什么是活动记录？
它主要由哪些内容构成？
答：
一个过程的一次执行所需信息的管理是通过称为活动记录的连续存储块来实现的，活动记录的主要内容有：
（1）临时变量域存放目标程序临时变量的值。
（2）局部数据域存放过程本次执行时的局部数据，简单变量及数组内情向量等。
（3）机器状态域保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等。
（4）存取链为访问其他活动记录中所有存放的非局部数据所提供的链地址。
（5）控制链指向主调过程的活动记录。
（6）实参存放主调过程为被调用过程所提供的实参信息。
（7）返回值为主调过程存放被调过程的返回值。
升级会员 