编译原理期末试题
编译原理期末试题(2003年---2004年第二学期) (A卷)
一、选择题（本大题共20小题，每小题1分，共20分）
1、汇编程序是将__c____翻译成___b___；编译程序是将__c_____翻译成___d_______。
a、汇编语言程序
b、机器语言程序
c、高级语言程序d汇编语言或机器语言程序
2、描述一个语言的文法是_____b______。
a、唯一的
b、不唯一的
c、个数有限的
3、生成非0开头的正偶数集的文法是_____d_________。
a、Z::=ABC c、Z::=ABC|2|4|6|8
C::=0|2|4|6|8 C::=0|2|4|6|8
B::=BA|B0|εB::=BA|B0|0
A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9
b、Z::=ABC d、Z::=ABC|2|4|6|8
C::=0|2|4|6|8 C::=0|2|4|6|8
B::=BA|B0|0 B::=BA|B0|ε
A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9
4、设有文法G[I]：
I→I0|I1|I a|Ic|a|b|c
下列符号串中是该文法的句子的有___________________。
①ab0 ②a0c01 ③aaa ④bc10
可选项有
a、①
b、②③④
c、③④
d、①②③④
5、现有前缀表示的表达式文法G1：
E::=-EE E::=-E E::=a|b|c
则文法的句子—a-bc的所有可能语法树有______棵。
a、1
b、2
c、3
d、4
6、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、
一组______。
a、字符串
b、字母数字串
c、产生式
d、结束符号
e、开始符号
f、文法
g、非终结符号h、终结符号
7、语法分析的常用方法是_________：
①自顶向下②自底向上③自左向右④自右向左
可选项有：
a、①②③④
b、①②
c、③④
d、①②③
8、下列文法__________二义文法
E::=EiT|T T::=T+F|iF|F F::=E*|(
可选项有：a、是b、不是c、无法判断。
9、素短语是指_______的短语。
①至少包含一个符号
②至少包含一个非终结符号
③至少包含一个终结符号
④除自身外不再包含其它终结符号
⑤除自身外不再包含其它非终结符号
⑥除自身外不再包含其它短语
⑦除自身外不再包含其它素短语
可选项有：
a、①④
b、①⑤
c、①⑥
d、②④
e、③⑤
f、③⑦
g、②⑦
10、LR（K）文法是_________。
a、从左到右分析，共经过K步的一种编译方法。
b、从左到右分析，每次向前预测K步的一种编译方法。
c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。
d、从左到右分析，每次走K步的一种编译方法。
11、在编译中产生语法树是为了____________。
a、语法分析
b、语义分析
c、词法分析
d、产生目标代码
12、文法的二义性和语言的二义性是两个____________概念。
a、不同
b、相同
c、无法判断
13、下述正规表达式中________与(a*+b)*(c+d)等价。
①a*（c+d）+b（c+d）
②a*（c+d）*+b（c+d）*
③a*（c+d）+b*（c+d）
④（a+b）*c+（a+b）*d
⑤（a*+b）*c+（a*+b）*d
可选项有:a、①b、②c、③d、④ e、⑤ f、④⑤ g、③④⑤
14、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：
a、存在
b、不存在
c、无法判定是否存在
15、LL（K）文法________二义性的。
a、都是
b、都不是
c、不一定都是
16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x
可选项有：a、LR（1）文法b、LALR（1）文法c、都不是d、a和b
17、编译过程中，比较常见的中间语言有___________。
①波兰表示
②逆波兰表示
③三元式
④四元式
⑤树形表示
可选项有：a、①③④b、②③④c、③④①⑤d、②③④⑤
18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。
a、abc*cd-b-a*+/--
b、a-bc*cd-b-a*+/-
c、a-bc*cd-/b-a*+-
d、a-bc*/cd-b-a*+-
19、在编译程序中安排中间代码生成的目的是_______________。
①便于进行存储空间的组织
②利于目标代码优化
③利于编译程序的移植
④利于目标代码的移植
⑤利于提高目标代码的质量
可选项有：
a、②④
b、①②③
c、③④①
d、②③④⑤
20、代码优化的主要目标是_____________。
①如何提高目标程序的运行速度
②如何减少目标程序运行所需的空间。
③如何协调①和②
④如何使生成的目标代码尽可能简短
可选项有：
a 、②④
b 、①②③
c 、③④①
d 、②③④
二、简答题：（每小题5分，共35分）
1、 证明下面文法是二义性的。S::=ibtSeS|ibtS|a
2、 现有文法S::=SaA|A A::=AbB|B B::=cSd|e
请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。
3、 求出下列文法所产生语言对应的正规式。
S::=bS|aA A::=aA|bB B::=aA|bC|b C::=bS|aA
4、 将表达式((a*d+c)/d+e)*f+g 分别表示三元式、四元式、逆波兰式序列
5、 消除下列文法的左递归。
S::=SaP|Sf|P P::=QbP|Q Q::=cSd|e
6、 给出与下图的NFA 等价的正规文法。
a
b
ε ε
7、 试对基本块应用DAG 进行优化，写出优化后的四元式序列。
三、问答题：
1、 已知文法G A::=aABe|a B::=Bb|d
（1） 给出与上述文法等价的LL （1）文法G ’。
（2） 构造预测分析表并给出输入串aade#分析过程。（10分）
2、 设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=P ↑F F::=P P::=(E)
P::=i
构造此文法的算符优先矩阵。（10分）
3、 有正规式b*abb*(abb*)*
（1） 构造该正规式所对应的NFA （画出状态转换图）。
（2） 将所求的NFA 确定化。（画出确定化的状态转换图）。
（3） 将所求的NFA 最小化。（画出最小化后的状态转换图）。（10分）
4、 若有文法G （S ）的产生式如下：S::=L=R S::=R L::=*R L::=i R::=L,构造
识别所有项目集规范族的DFA 。（15分）
（1） 判断该文法是否是LR （0）文法，说明理由。
（2） 判断该文法是否是SLR （1）文法，说明理由。
（3） 判断该文法是否是LR （1）文法，说明理由。
（4） 判断该文法是否是LALR （1）文法，说明理由。
S0 S2 S1 S3