期末考试编译原理试题
20、代码优化的主要目标是_____________。 ①如何提高目标程序的运行速度
②如何减少目标程序运行所需的空间。 ③如何协调①和②
④如何使生成的目标代码尽可能简短 可选项有：
a 、②④
b 、①②③
c 、③④①
d 、②③④ 二、简答题：（每小题5分，共30分）
1、写一个文法使其语言为L(G)={ a n b m a m b n | m,n ≥1}。
2、对于文法G(E): E →T|E+T T →F|T*F F →(E)|i
（1） 写出句型(T*F+i)的最右推导并画出语法树。
（2） 写出上述句型的短语，直接短语、句柄和素短语。 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
5、 给出与下图的NFA 等价的正规文法。
三、问答题：（共计50分）
5、 已知文法G A::=aABe|a B::=Bb|d
（1） 给出与上述文法等价的LL （1）文法G ’。 （2） 构造预测分析表并给出输入串aade#分析过程。（10分） 6、 设∑={0，1}上的正规集S 由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，
并构造一个识别该正规集的DFA 。(15分)
3、设文法G(S)：(10分)
(
|*)B B |B A A A
|SiA S A →+→→
构造算符优先关系表和优先函数。
4、构造文法G(S)：
(1) S → BB (2) B → aB (3) B → b
的LR 分析表。假定输入串为abab ，请给出LR 分析过程(即按照步骤给出状态，符号，输入串的变化过程)（15分）。
德州学院期末考试试题
（ 8 至 学年第 学期）
课程名称： 考试对象： 试卷类型： （1） 考试时间： 分钟
一、 选择题（本大题共20小题，每小题1分，共20分） 1、素短语是指_______的短语。 ①至少包含一个符号
②至少包含一个非终结符号 ③至少包含一个终结符号
④除自身外不再包含其它终结符号 ⑤除自身外不再包含其它非终结符号 ⑥除自身外不再包含其它短语 ⑦除自身外不再包含其它素短语 可选项有：
A 、①④
B 、①⑤
C 、①⑥
D 、②④
E 、③⑤
F 、③⑦
G 、②⑦ 2、表达式ab+cd+*的逆波兰式表达式所表示的中缀形式的表达式是 A 、 a+b+c*d B 、 (a+b)*(c+d) C 、 (a+b)*c+d D 、a+b*c+d
3、Chomsky 的3型语言是这样一种语言，其产生式限制为（α、π、β为字符串）。 A 、 A →β B 、 A →a A →aB C 、α→β D 、αA β→απβ
4、设有文法G[S]=（{b},{S,B},S,{S →b|bB, B →bS}）,该文法描述的语言是 。 A 、b i | i ≥0 B 、b 2i | i ≥0 C 、b 2i+1 | i ≥0 D 、b 2i+1 | i ≥1
5、设有文法G[S]：
S →S*S|S+S|（S ）|a 该文法 二义性文法
A 、是
B 、不是
C 、无法判断
6、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。
A 、汇编语言程序
B 、机器语言程序
C 、高级语言程序
D 、汇编语言或机器语言程序 7、给定文法A →bA|cc, 下面符号串中，为该文法句子的是 。 ① cc ② bcbc ③ bcbcc ④ bccbcc ⑤bbbcc
A 、①
B 、①③④⑤
C 、①⑤
D 、①④⑤
E 、①②③④⑤ 8、递归下降分析语法分析的属于 分析方法。
A 、自顶向下
B 、自底向上
C 、 自左向右
D 、自右向左
9、已知语言L={a n bb n |n ≥1}，则下述文法中， 可以产生语言L