编译原理期末考试选择题汇总.docx
《编译原理期末考试选择题汇总.docx》由会员分享，可在线阅读，更多相关《编译原理期末考试选择题汇总.docx（34页珍藏版）》请在冰点文库上搜索。
编译原理期末考试选择题汇总
一、单项选择题
1、将编译程序分成若干个“遍”是为了（B）
A．提高程序的执行效率
B.使程序的结构更加清晰
C．利用有限的机器内存并提高机器的执行效率
D．利用有限的机器内存但降低了机器的执行效率
2、不可能是目标代码的是（D）
A．汇编指令代码B．可重定位指令代码
C．绝对指令代码D．中间代码
3、词法分析器的输入是（B）
A．单词符号串B．源程序
C．语法单位D．目标程序
4、编译程序中的语法分析器接受以c为单位的输入，并产生有关信息供以后各阶段使用。
可选项有：
a、表达式b、产生式c、单词d、语句
5、高级语言编译程序常用的语法分析方法中，递归下降分析法属于b分析方法。
可选项有：
a、自左至右b、自顶向下c、自底向上d、自右向左
6、已知文法G[E]：
E→TE’E’→+TE’∣εT→FT’
T’→*FT’∣εF→（E）∣id
求：
FOLLOW（F）=
（1）d，FIRST（T’）=
（2）b
可选项有：
a、｛*，+｝b、｛*，ε｝c、｛+,#，）｝
d、｛*，+，#，）｝e、｛#，）｝f、｛*，+，#，id｝
7、中间代码生成时所遵循的是（C）
A．语法规则B．词法规则
C．语义规则D．等价变换规则
8、编译程序是对（D）
A．汇编程序的翻译B．高级语言程序的解释执行
C．机器语言的执行D．高级语言的翻译
9、词法分析应遵循（C）
A．语义规则B．语法规则
C．构词规则D．等价变换规则
10、词法分析器的输出结果是（C）
A．单词的种别编码B．单词在符号表中的位置
C．单词的种别编码和属性值D．单词属性值
11、正规式M1和M2等价是指（C）
A．M1和M2的状态数相等B．M1和M2的有向弧条数相等
C．M1和M2所识别的语言集相等D．M1和M2状态数和有向弧条数相等
12、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，（A）
A．词法分析器应作为独立的一遍
B．词法分析器作为子程序较好
C．词法分析器分解为多个过程，由语法分析器选择使用．
D．词法分析器并不作为一个独立的阶段
13、如果L（M1）=L（M2），则M1与M2（A）
A．等价B．都是二义的
C．都是无二义的D．它们的状态数相等
14、文法G：
S→xSx|y所识别的语言是（C）
A．xyxB．（xyx）*c．xnyxn（n≥0）d．x*yx*
15、文法G描述的语言L（G）是指（A）
A．
B．
C．
D．
16、有限状态自动机能识别（C）
A．上下文无关文法B．上下文有关文法
C．正规文法D．短语文法
17、编译过程中扫描器的任务包括d。
①组织源程序的输入②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出③删除注解④删除空格及无用字符⑤行计数、列计数⑥发现并定位词法错误⑦建立符号表
可选项有：
a、②③④⑦b、②③④⑥⑦c、①②③④⑥⑦d、①②③④⑤⑥⑦
18、正则式的“∣”读作
（1）b，“·”读作
（2）c，“*”读作（3）d。
可选项有：
a、并且b、或者c、连接d、闭包
19、b这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。
可选项有：
a、存在b、不存在c、无法判定是否存在
20、编译过程中，语法分析的任务是c。
①分析单词是怎样构成的②分析单词是如何构成语句和说明的
③分析语句和说明是如何构成程序的④分析程序的结构
可选项有：
a、②和③b、④c、②③④d、①②③④
21、语法分析的常用方法有b。
①自顶向下②自底向上③自左向右④自右向左
可选项有：
a、①②③④b、①②c、③④d、①②③
22、如果文法G是无二义的，则它的任何句子（A）
A．最左推导和最右推导对应的语法树必定相同
B．最左推导和最右推导对应的语法树可能不同
C．最左推导和最右推导必定相同
D．可能存在两个不同的最左推导，但它们对应的语法树相同
23、由文法的开始符经0步或多步推导产生的文法符号序列是（C）
A．短语B．句柄C．句型D．句子
24、文法G：
E→E+T|T
T→T*P|P
P→（E）|i
则句型P+T+i的句柄为（B）
A．P+TB．PC．P+T+iD．i
25、文法G：
S→b|∧|（T）
T→T∨S|S
则FIRSTVT（T）=（C）
A．{b，∧，（}B．{b，∧，）}
C．{b，∧，（，∨}D．{b，∧，），∨}
26、产生正规语言的文法为（D）
A．0型B．1型C．2型D．3型
27、任何算符优先文法（D）优先函数。
A．有一个B．没有C．有若干个D．可能有若干个
28、采用自上而下分析，必须（C）
A．消除左递归B．消除右递归
C．消除回溯D．提取公共左因子
29、素短语是指D的短语。
①至少包含一个符号②至少包含一个终结符号③至少包含一个非终结符号④除自身外不再包含其他终结符号⑤除自身外不再包含其他非终结符号⑥除自身外不再包含其他短语⑦除自身外不再包含其他素短语
可选项有：
A、①④B、①⑤C、②④D、②⑦
30、给定文法A→bA∣cc，下面的符号串中，为该文法句子的是A。
①cc②bcbc③bcbcc④bccbcc⑤bbbcc
可选项有：
A、①B、①③④⑤C、①④D、①④⑤
31、已知文法G[S]：
S→eT∣RTT→DR∣εR→dR∣εD→a∣bd
则FOLLOW（T）=D。
可选项有：
A、｛d｝B、｛a,b｝C、｛a,b,#｝D、｛#｝E、｛d,#｝
32、正则式中的“*”读作D。
可选项有：
A、并且B、或者C、连接D、闭包
33、在规X归约中，用（B）来刻画可归约串。
A．直接短语B．句柄C．最左素短语D．素短语
34、有文法G：
E→E*T|T
T→T+i|i
句子1+2*8+6按该文法G归约，其值为（B）
A．23B．42C．30D．17
35、如果文法是无二义的，那么规X归约是指（B）
A．最左推导的逆过程B．最右推导的逆过程
C．规X推导D．最左归约的逆过程
36、文法G:
S→S+T|T
T→T*P|P
P→（S）|i
句型P+T+i的短语有（B）
A．i,P+TB．P,P+T,i,P+T+iC．P+T+iD．P，P+T，i
37、高级语言编译程序常用的语法分析方法中，递归下降分析法属于b分析方法。
可选项有：
A、自左至右B、自顶向下C、自底向上D、自右向左
38、一般程序设计语言的定义都涉及A三个方面。
①语法②语义③语用④程序基本符号的确定
可选项有：
A、①②③B、①②④C、①③④D、②③④
39、编译过程中，语法分析器的任务是B。
①分析单词是怎样构成的②分析单词串是如何构成语句和说明的
③分析语句和说明是如何构成程序的④分析程序的结构
可选项有：
A、②③B、②③④C、①②③D、①②③④
40、编译程序生成的目标程序B是机器语言的程序。
可选项有：
A、一定B、不一定C、无法判断D、一定不
一、单项选择题（将正确答案的字母填入括号，每题1.5分，共30分）
1、一般程序设计语言的定义都涉及到（1.2.3）3个方面。
（1）语法
（2）语义（3）语用（4）程序基本符号的确定
2、程序语言一般分为
（1）和
（2）。
（1）高级语言；
（2）低级语言；（3）专用程序语言；（4）通用程序语言
3、面向机器语言指的是（B）。
A．用于解决机器硬件设计问题的语言B．特定计算机系统所固有的语言
C．各种计算机系统都通用的语言D．只能在一台计算机上使用的语言
4．面向机器语言的特点是（D）。
A．程序的执行效率低，编制效率低，可读性差
B．程序的执行效率高，编制效率高，可读性强
C．程序的执行效率低，编制效率高，可读性强
D．程序的执行效率高，编制效率低，可读性差
5、程序设计语言常见的数据类型有：
1.2.3.4
（1）数值型数据
（2）逻辑数据（3）字符数据（4）指针类型
6、下列程序设计语言中是应用式语言的是：
B
A、PASCALB、LISPC、VBD、PROLOG
7、任何语法结构都可以用（C）来表示。
A、语法树B、树C、抽象语法树D、二义文法树
8、字母表是符号的有穷集合，由（C）组成词和句子。
A、字符串B、字符C、符号D、语言
9、下列符号是终结符的是（A）。
A、cB、AC、SD、β
10、语法树用（C）关系说明了句子中以操作符为核心的操作顺序，同时也说明了每一个操作符的操作对象。
A、上下B、先后C、层次D、关联
11、循环语句的语法树为（D）
A、
B、
C、
D、
12、表达式中间代码的生成可采用（B）。
A、三地址代码B、四元式C、三元式D、间接三元式
13、下列文法中，赋值语句的文法是（C）。
A、B、
C、D、E→EopE
14、词法分析的任务是（A）
A、识别单词B、分析句子的含义C、识别句子D、生成目标代码
15、常用的中间代码形式中不含（D）
A、三元式B、四元式C、逆波兰式D、语法树
16、代码优化的目的是（C）
A、节省时间B、节省空间C、节省时间和空间D、把编译程序进行等价转换
17、代码生成阶段的主要任务是（C）
A、把高级语言翻译成汇编语言B、把高级语言翻译成机器语言
C、把中间代码变换成依赖具体机器的目标代码D、把汇编语言翻译成机器语言
18、词法分析器的输入是（B）
A、单词符号串B、源程序C、语法单位D、目标程序
19、中间代码的生成所遵循的是（C）
A、语法规则B、词法规则C、语义规则D、等价变换规则
20、编译程序是对（D）
A、汇编程序的翻译B、高级语言程序的解释并执行C、机器语言的执行D、高级语言的翻译
21、语法分析应遵循（C）
A、语义规则B、语法规则C、构词规则D、等价变换规则
22、编译程序各阶段的工作都涉及到（B）
A、语法分析B、表格管理、出错处理C、语义分析D、词法分析
23、编译程序工作时，通常有（1.2.3.4）阶段。
（1）词法分析
（2）语法分析（3）中间代码生成（4）语义检查（5）目标代码生成
24、由文法的开始符经0步或多步推导产生的文法符号序列是C。
A、短语B、句柄C、句型D、句子
25、产生正规语言的文法为D。
A、0型B、1型C、2型D、3型
26、对无二义性文法来说，一棵语法树往往代表了D。
（1）多种推导过程
（2）多种最左推导过程（3）一种最左推导过程
（4）仅一种推导过程（5）一种最左推导过程
A、B、
（1）（3）（5）C、D
27、如果文法G存在一个句子，满足下列条件之一时，则称该文法是二义文法。
BCD
a.该句子的最左推导与最右推导相同b.该句子有两个不同的最左推导
c.该句子有两棵不同的最右推导d.该句子有两棵不同的语法树
e.该句子的语法树只有一个
28、优化可生成（D）的目标代码。
A、运行时间较短B、占用存储空间较小C、运行时间短且占用内存空间大D、运行时间短且存储空间小
29、构造编译程序应掌握（D）
A、源程序B、目标程序C、编译方法D、以上三项都是
30、赋值语句x=a+b*c-d的逆波兰式为（B）
A、xab+c*d-=B、xabc*+d-=C、xabcd*+-=D、x=abc*+d-
31、词法分析器的输出结果是（C）
A、单词的种别编码B、单词在符号表中的位置
C、单词的种别编码和自身值D、单词自身值
《编译原理》期末试题
（一）
一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）
1．编译程序是对高级语言程序的解释执行。
（×）
2．一个有限状态自动机中，有且仅有一个唯一的终态。
（×）
3．一个算符优先文法可能不存在算符优先函数与之对应。
（√）
4．语法分析时必须先消除文法中的左递归。
（×）
5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
（√）
6．逆波兰表示法表示表达式时无须使用括号。
（√）
7．静态数组的存储空间可以在编译时确定。
（×）
8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
（×）
9．两个正规集相等的必要条件是他们对应的正规式等价。
（×）
10．一个语义子程序描述了一个文法所对应的翻译工作。
（×）
二、选择题（请在前括号内选择最确切的一项作为答案划一个勾，多划按错论）（每个4分，共40分）
1．词法分析器的输出结果是_____。
A．（）单词的种别编码 B．（）单词在符号表中的位置
C．（）单词的种别编码和自身值 D．（）单词自身值
2．正规式M1和M2等价是指_____。
A．（）M1和M2的状态数相等 B．（）M1和M2的有向边条数相等
C．（）M1和M2所识别的语言集相等 D．（）M1和M2状态数和有向边条数相等
3．文法G：
S→xSx|y所识别的语言是_____。
A．（）xyx B．（）（xyx）*C．（）xnyxn（n≥0） D．（）x*yx*
4．如果文法G是无二义的，则它的任何句子α_____。
A．（）最左推导和最右推导对应的语法树必定相同
B．（）最左推导和最右推导对应的语法树可能不同
C．（）最左推导和最右推导必定相同
D．（）可能存在两个不同的最左推导，但它们对应的语法树相同
5．构造编译程序应掌握______。
A．（）源程序 B．（）目标语言
C．（）编译方法 D．（）以上三项都是
6．四元式之间的联系是通过_____实现的。
A．（）指示器 B．（）临时变量
C．（）符号表 D．（）程序变量
7．表达式（┐A∨B）∧（C∨D）的逆波兰表示为_____。
A.（）┐AB∨∧CD∨B．（）A┐B∨CD∨∧
C．（）AB∨┐CD∨∧ D．（）A┐B∨∧CD∨
8.优化可生成_____的目标代码。
A．（）运行时间较短 B．（）占用存储空间较小
C．（）运行时间短但占用内存空间大 D．（）运行时间短且占用存储空间小
9．下列______优化方法不是针对循环优化进行的。
A.（）强度削弱 B．（）删除归纳变量
C．（）删除多余运算 D．（）代码外提
10．编译程序使用_____区别标识符的作用域。
A.（）说明标识符的过程或函数名
B．（）说明标识符的过程或函数的静态层次
C．（）说明标识符的过程或函数的动态层次
D.（）标识符的行号
《编译原理》期末试题
（二）
1、描述由正规式b*（abb*）*（a|）定义的语言，并画出接受该语言的最简DFA。
2、证明文法EE+id|id是SLR
（1）文法。
5、下面C语言程序经非优化编译后，若运行时输入2，则结果是
area=12.566360,addr=-1073743076
经优化编译后，若运行时输入2，则结果是
area=12.566360,addr=-1073743068
请解释为什么输出结果有区别。
main（）
{
floats,pi,r;
pi=3.14159;
scanf（"%f",&r）;
printf（"area=%f,addr=%d\n",s=pi*r*r,&r）;
}
6、描述由正规式ba（bba）b定义的语言，并画出接受该语言的最简DFA。
7、下面的文法产生代表正二进制数的0和1的串集：
BB0|B1|1
下面的翻译方案计算这种正二进制数的十进制值：
BB10{B.val:
=B1.val2}
|B11{B.val:
=B1.val2+1}
|1{B.val:
=1}
请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。
8、在C语言中，如果变量i和j都是long类型，请写出表达式&i和表达式&i&j的类型表达式。
为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。
main（）{
longi,j;
printf（“%d\n”,&i&j）;
}
9、一个C语言的函数如下：
func（i）longi;{
longj;
j=i–1;
func（j）;
}
下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。
左边的代码在调用func之前将参数压栈，调用结束后将参数退栈。
右边代码对参数传递的处理方式没有实质区别。
请叙述右边代码对参数传递的处理方式并推测它带来的优点。
func:
|func:
pushl%ebp|pushl%ebp
movl%esp,%ebp|movl%esp,%ebp
subl$4,%esp|subl$8,%esp
movl8（%ebp）,%edx|movl8（%ebp）,%eax
decl%edx|decl%eax
movl%edx,-4（%ebp）|movl%eax,-4（%ebp）
movl-4（%ebp）,%eax|movl-4（%ebp）,%eax
pushl%eax|movl%eax,（%esp）
callfunc|callfunc
addl$4,%esp|leave
leave|ret
ret|
编译原理试卷八答案
1、由正规式b*（abb*）*（a|）定义的语言是字母表{a,b}上不含子串aa的所有串的集合。
最简DFA如下：
2、先给出接受该文法活前缀的DFA如下：
I0和I3都只有移进项目，肯定不会引起冲突；I2和I4都无移进项目并仅含一个归约项目，也肯定不会引起冲突；在I1中，E的后继符号只有$，同第2个项目的展望符号“+”不一样，因此I1也肯定不会引起冲突。
由此可以断定该文法是SLR
（1）的。
3、语法制导定义如下。
Sid:
=E{S.type:
=if（id.type=boolandE.type=bool）or（id.type=intandE.type=int）thentype_okelsetype_error}
EE1andE2{E.type:
=ifE1.type=boolandE2.type=boolthenboolelsetype_error}
EE1+E2{E.type:
=ifE1.type=intandE2.type=intthenintelsetype_error}
EE1=E2{E.type:
=ifE1.type=intandE2.type=intthenboolelsetype_error}
Eid{E.type:
=lookup（id.entry）}
4、对于函数f1，局部变量x声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。
由于这是一个合法的C语言函数，因此编译器给出警告错误。
对于函数f2，由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。
5、使用非优化编译时，变量s,pi,r在局部数据区都分配4个字节的空间。
使用优化编译时，由于复写传播，pi*r*r变成3.14159*r*r，pi=3.14159成为无用赋值而删去，函数中不再有pi的引用，因此不必为pi分配空间。
类似地，s=3.14159*r*r也是一个无用赋值（表达式要计算，但赋值是无用的），也不必为s分配空间。
这样，和非优化情况相比，局部数据区少了8个字节，因此r的地址向高地址方向移动了8个字节。
6、正规式ba（bba）b体现的特点是，每个a的左边都有若干b，除非a是第一个字母。
该正规式定义的语言是：
至少含一个a，但不含子串aa的所有a和b的串集。
最简DFA如下：
7、消除左递归后的文法：
B1B
B0B|1B|
相应的翻译方案如下：
B1{B.i:
=1}B{B.val:
=B.val}
B0{B1.i:
=B.i2}B1{B.val:
=B1.val}
|1{B1.i:
=B.i2+1}B1{B.val:
=B1.val}
|{B.val:
=B.i}
8、表达式&i的类型表达式是pointer（long），表达式&i&j的类型表达式是long。
按照C语言的规定，指向同一个类型的两个指针可以相加减，它们值的差是它们之间的元素个数。
9、左边的编译器版本：
一般只为局部变量分配空间。
调用函数前，用若干次pushl指令将参数压栈，返回后用addl$n,%esp一次将所有参数退栈（常数n根据调用前做了多少次pushl来决定）。
右边的编译器版本：
除了为局部变量分配空间外，同时还为本函数中出现的函数调用的参数分配空间，并且参数所用空间靠近栈顶。
调用函数前，用movl指令将参数移入栈顶，调用结束后无需参数退栈指令。
优点是每次函数调用结束后不需要执行addl$n,%esp指令，另外增加优化的可能性。
《编译原理》期末试题（三）
1、从优化的X围的角度，优化可以分哪两类？
对循环的优化可以有哪三种？
答：
从优化的X围的角度，优化可以分为局部优化和全局优化两类；
对循环的优化有三种：
循环不变表达式外提、归纳变量删除与计算强度削减。
2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。
答：
逆波兰式：
abc*bd*+:
=
升级会员 