发布时间 : 星期二 文章编译原理10套试卷及答案更新完毕开始阅读
编译原理期末试题(2003年---2004年第二学期) (A卷)
一、选择题（本大题共20小题，每小题1分，共20分）
1、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。 a、汇编语言程序 b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序
2、描述一个语言的文法是___________。
a、唯一的 b、不唯一的 c、个数有限的
3、生成非0开头的正偶数集的文法是______________。 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等价的正规文法。
ε S2 S3 ε a S1 b S0
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）文法，说明理由。
装 订 线
华中科技大学武昌分校
《编译原理》试卷A
专业班级：_________学号：_________姓名：__________总分
一、单项选择题(共10小题，每小题2分) （题分 20分）
1．语言是
A．句子的集合 B．产生式的集合 C．符号串的集合 D．句型的集合 2．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析
C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化
3．一个句型中称为句柄的是该句型的最左
A．非终结符号 B．短语 C．句子 D．直接短语 4．下推自动机识别的语言是
A．0型语言 B．1型语言
得分 C．2型语言 D．3型语言
5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即
A． 字符 B．单词 C．句子 D．句型 6．对应Chomsky四种文法的四种语言之间的关系是 A．L0?L1?L2?L3 B．L3?L2?L1?L0 C．L3=L2?L1?L0 D．L0?L1?L2=L3 7．词法分析的任务是
A．识别单词 B．分析句子的含义 C．识别句子 D．生成目标代码 8．常用的中间代码形式不含
A．三元式 B．四元式 C．逆波兰式 D．语法树
9． 代码优化的目的是
A．节省时间 B．节省空间
C．节省时间和空间 D．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A．把高级语言翻译成汇编语言 B．把高级语言翻译成机器语言
C．把中间代码变换成依赖具体机器的目标代码 D．把汇编语言翻译成机器语言