编译原理试题及答案Word文件下载.docx
《编译原理试题及答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《编译原理试题及答案Word文件下载.docx（43页珍藏版）》请在冰点文库上搜索。
c.后请先放
d.任意
二（每小题10分，共80分）简答题
1.画出编译程序的总体结构图，简述各部分的主要功能。
2.
已知文法G[E]:
E→ET+|T
T→TF*|F
F→F^|a
试证：
FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.
3．为正规式（a|b）*a（a|b）构造一个确定的有限自动机。
4．
设文法G（S）：
S→（L）|aS|a
L→L，S|S
（1）消除左递归和回溯；
（2）计算每个非终结符的FIRST和FOLLOW；
（3）构造预测分析表。
5．
已知文法
A->
aAd|aAb|ε
判断该文法是否SLR
（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。
6．
构造算符文法G[H]的算符优先关系（含＃）。
G[H]：
H→H;
M|M
M→d|aHb
7．已构造出文法G（S）
（1）S
BB
（2）B
aB
（3）B
b
1）。
给出DFA图
2）.给出LR分析表
3）．假定输入串为abaab，请给出LR分析过程（即状态，符号，输入串的变化过程）。
8．
将下面的语句翻译成四元式序列：
whileA<
C∧B<
Ddo
ifA=1thenC:
=C+l
elsewhileA≤Ddo
A:
=A+2；
9．
对下面的流图，
（1）求出流图中各结点N的必经结点集D（n），
（2）求出流图中的回边，
（3）求出流图中的循环。
参考答案
一．单项选择题
1.
将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。
.构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。
3.
对编译而言，变量既持有左值又持有右值，故选c。
4.
编译程序打交道最多的就是各种表格，因此选d。
5.
词法分析器输出的结果是单词的种别编码和自身值，选C。
6.
正规式M1和M2所识别的语言集相等，故选C。
7.
选c。
8.
选b。
9.
选C
10.
堆式动态分配申请和释放存储空间不一定遵守先请后放和后请先放的原则，故选d
二．简答题
1．
【解答】
编译程序的总体结构图如图1.2所示。
词法分析器：
输入源程序，进行词法分析，输出单词符号。
语法分析器：
在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号串分
解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。
中间代码生成器：
按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定
形式的中间代码，比如说四元式。
优化：
对中间代码进行优化处理。
目标代码生成器：
把中间代码翻译成目标语言程序。
表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。
编
译程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编
译过程都在不断地和表格打交道。
出错处理程序对出现在源程序中的错误进行处理。
此外，编译的各阶段都可能出现错误，
出错处理程序对发现的错误都及时进行处理。
2．
【解答】
该句型对应的语法树如下：
该句型相对于E的短语有FF^^*；
相对于T的短语有FF^^*,F;
相对于F的短语有F^;
F^^;
简单短语有F;
F^;
句柄为F.
3．
最简DFA如图2.66所示。
【解答】
（1）
S→（L）|aS’
S’→S|ε
L→SL’
L’→SL’|ε
评分细则：
消除左递归2分，提公共因子2分。
（2）FIRST和FOLLOW
FIRST）S）＝{（，a} FOLLOW（S）＝{#，，，）}
FIRST（S’）＝{，a,ε} FOLLOW（S’）＝{#，，，）}
FIRST（L）＝{（，a} FOLLOW（L）＝{）}
FIRST（L’）＝{，，ε} FOLLOW（L’〕＝{）}
（1）拓广文法
（0）S->
A
（1）A->
aAd
（2）A->
aAb
（3）A->
ε
（2）构造识别活前缀的DFA
FOLLOW（A）={d,b,#}
对于状态I0：
FOLLOW（A）∩{a}=Ф
对于状态I1：
因为，在DFA中无冲突的现象，所以该文法是SLR
（1）文法。
（3）SLR
（1）分析表
状态
ACTION
GOTO
a
B
d
#
A
0
S2
r3
1
1
acc
2
3
3
S5
S4
4
r1
5
r2
（4）串ab#的分析过程
步骤
状态栈
符号栈
当前字符
剩余字符串
动作
0
b#
移进
02
#a
b
归约A->
023
#aA
0235
#aAb
aAb
01
#A
接受
由M→d和M→a…得：
FIRSTVT（M）=｛d,a｝；
由H-H;
…得：
FIRSTVT（H）=｛；
｝
由H→M得：
FIRSTVT（M）cFIRSTVT（H），即FIRSTVT（H）={;
d,a}
由M→d和M→…b得：
LASTVT（M）={d,b}；
由H---，；
m得：
LASTVT（H）=｛；
｝；
LASTVT（M）cLASTVT（H），即LASTVT（H）=｛;
d,b}
对文法开始符H,有#H#存在，即有＃=＃，#<
FIRSTVT（H），LASTVT（H）>
#,也即＃＜；
，#<
d.#<
a,；
＞＃，d>
#,b>
#。
对形如P→…ab…，或P→…aQb…，有a=b，由M→a|b得：
a=b；
对形如P→…aR…，而b∈FIRSTVT（R），有a<
b，对形如P→…Rb…，而a∈LASTVT（R）．
有a>
b。
由H→…；
M得：
；
FIRSTVT（M），即：
：
d，：
a
由M→aH…得：
a<
FIRSTVT（H），即：
a＜；
，a<
d，a＜a
由H→H；
’’•得：
LASTVT（H）>
;
，即：
＞；
，d>
，b＞；
由M→…Hb得：
b，即：
＞b，d>
b，b＞b
由此得到算符优先关系表，见表3.5。
7．
（1）LR分析表如下：
（2）分析表
状态
ACTION
GOTO
a
b
#
S
B
0
s3
s4
1
2
1
acc
2
S3
S4
5
3
6
4
r3
5
R1
r1
6
R2
（3）句子abaab的分析过程
表:
句子abaab的分析过程
步骤
状态
符号栈
输入串
所得产生式
#0
abaad#
#03
#a
baad#
#034
#ab
aab#
B→b
#036
#aB
B→aB
#02
#B
#023
#Ba
ab#
#0233
#Baa
b#
7
#02334
#Baab
8
#02336
#BaaB
9
#0236
#BaB
ad#
10
#025
#BB
11
#01
#S
d#
12
13
识别成功
【解答】
该语句的四元式序列如下（其中E1、E2和E3分别对应：
A<
D,A=1和A≤D并且关系运算符优先级高）：
100（j<
A,C,102）
101（j,_,_,113）
/*E1为F*/
102（j<
B,D,104）
/*El为T*/
103（j,_,_,113）
/*El为F*/
104（j=,A,1,106）
/*Ez为T*/
105（j,_,_,108）
/*EZ为F*/
106（＋,C,1,C）
/*C:
=C+1*/
107（j,_,_,112）
/*跳过else后的语句*/
108（j≤,A,D,110）
/*E3为T*/
109（j,_,_,112）
/*E3为F*/
110（＋,A,2,A）
/*A:
=A+2*/
111（j,_,_,108）
/*转回内层while语句开始处*/
112（j,_,_,100）
/*转回外层while语句开始处*/
113
（1）流图中各结点N的必经结点集D（n），
D（l）＝{1}，D
（2）＝{1,2}，D（3）＝{1,2,3}，D（4）={1,2,3,4}，D（5）＝{1,2,5}，
D（6）＝{1,2,5,6}
5->
2，4->
3
（3）求出流图中的循环:
回边5->
2对应的循环：
2、5、3、4；
回边4->
3对应的循环：
3、4
《编译原理》模拟试题一
一、是非题（请在括号内，正确的划√，错误的划×
）（每个2分，共20分）
1．计算机高级语言翻译成低级语言只有解释一种方式。
（×
）
2．在编译中进行语法检查的目的是为了发现程序中所有错误。
3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。
（√）
4．正则文法其产生式为A->
a，A->
Bb,
A,B∈VN，a、b∈VT。
（×
5．每个文法都能改写为LL
（1）文法。
（√）
6．递归下降法允许任一非终极符是直接左递归的。
7．算符优先关系表不一定存在对应的优先函数。
8．自底而上语法分析方法的主要问题是候选式的选择。
9．LR法是自顶向下语法分析方法。
10．简单优先文法允许任意两个产生式具有相同右部。
二、选择题（请在前括号内选择最确切的一项作为答案划一个勾，多划按错论）（每个4分，共40分）
1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。
A．（）语法分析 B．（）文法分析 C．（）语言分析 D．（）解释分析
2．词法分析器用于识别_____。
c
A．（）字符串B．（）语句C．（）单词 D．（）标识符
3．语法分析器则可以发现源程序中的_____。
d
A．（）语义错误
B．（）语法和语义错误
C．（）错误并校正
D．（）语法错误
4．下面关于解释程序的描述正确的是_____。
（1）解释程序的特点是处理程序时不产生目标代码
（2）解释程序适用于COBOL和FORTRAN语言
（3）解释程序是为打开编译程序技术的僵局而开发的
A．（）
（1）
（2） B．（）
（1） C．（）
（1）
（2）（3）
D．（）
（2）（3）
5．解释程序处理语言时,大多数采用的是_____方法。
A．（）源程序命令被逐个直接解释执行
B．（）先将源程序转化为中间代码,再解释执行
C．（）先将源程序解释转化为目标程序,再执行
D．（）以上方法都可以
6．编译过程中,语法分析器的任务就是_____。
（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所描述的语言是_____的集合。
A.（）文法G的字母表V中所有符号组成的符号串
B．（）文法G的字母表V的闭包V*中的所有符号串
C．（）由文法的开始符号推出的所有终极符串
D.（）由文法的开始符号推出的所有符号串
9．文法分为四种类型，即0型、1型、2型、3型。
其中3型文法是_____。
A.（）短语文法B．（）正则文法C．（）上下文有关文法 D．（）上下文无关文法
10．一个上下文无关文法G包括四个组成部分，它们是：
一组非终结符号，一组终结符号，一个开始符号，以及一组_____。
A．（）句子 B．（）句型C．（）单词 D．（）产生式
三、填空题（每空1分，共10分）
1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和___出错处理__。
2．若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序称为___编译程序__。
3．编译方式与解释方式的根本区别在于__是否生成目标代码___。
4．对编译程序而言,输入数据是___源程序__,输出结果是__目标程序___。
5．产生式是用于定义___语法成分__的一种书写规则。
6．语法分析最常用的两类方法是___自上而下__和___自下而上__分析法。
四、简答题（20分）
1.什么是句子？
什么是语言?
答：
（1）设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*）,则称x是文法的一个句子。
（2）设G[S]是给定文法，则由文法G所定义的语言L（G）可描述为：
L（G）＝{x│Sx,x∈VT*}。
参考答案：
（每个2分，共4分）
2.写一文法，使其语言是偶正整数的集合,要求：
（1）允许0打头；
（2）不允许0打头。
解：
（1）G[S]=（{S,P,D,N},{0,1,2,…,9},P,S）
P:
S->
PD|D
P->
NP|N
D->
0|2|4|6|8
N->
0|1|2|3|4|5|6|7|8|9
（2）G[S]=（{S,P,R,D,N,Q},{0,1,2,…,9},P,S）
PD|P0|D
NR|N
R->
QR|Q
2|4|6|8
1|2|3|4|5|6|7|8|9
Q->
3.已知文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→（E）|i
①该文法的开始符号（识别符号）是什么？
②请给出该文法的终结符号集合VT和非终结符号集合VN。
③找出句型T+T*F+i的所有短语、简单短语和句柄。
①该文法的开始符号（识别符号）是E。
②该文法的终结符号集合VT={+、-、*、/、（、）、i}。
非终结符号集合VN={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;
简单短语为i、T*F、第一个T;
句柄为第一个T。
4.构造正规式相应的NFA:
1（0|1）*101
解1（0|1）*101对应的NFA为
5.写出表达式（a＋b*c）/（a＋b）－d的逆波兰表示和三元式序列。
逆波兰表示：
abc*＋ab＋/d－
三元式序列：
①（*，b，c） ②（＋，a，①） ③（＋，a，b） ④（/，②，③） ⑤（－，④，d）
五.计算题（10分）
构造下述文法G[S]的自动机：
S->
A0A->
A0|S1|0
该自动机是确定的吗？
若不确定，则对它确定化。
由于该文法的产生式S->
A0，A->
A0|S1中没有字符集VT的输入，所以不是确定的自动机。
要将其他确定化，必须先用代入法得到它对应的正规式。
把S?
A0代入产生式A?
S1有：
A=A0|A01|0=A（0|01）|0=0（0|01）
升级会员 