期末考试编译原理试题
①如何提高目标程序的运行速度
②如何减少目标程序运行所需的空间。
③如何协调①和②
④如何使生成的目标代码尽可能简短
可选项有：
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等价的正规文法。
7、对基本块P画出DAG图
B:=3
D:=A+C
E::=A*C
F:=E+D
G:=B*F
H:=A+C
I:=A*C
J:=H+I
K:=B*5
L:=K+J
M:=L
假定只有L在基本块出口之后活跃，写出优化后的四元式序列。
四、问答题：（共计45分）
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）文法，说明理由
德州学院期末考试试题
（ 3 至学年第学期）
课程名称：考试对象：试卷类型：（1）考试时间：分钟
一、单项选择题（20分，每小题1分）
1、文法G1：P→aPQR| abR，RQ→QR，BQ→bb，bR→bc，cR→cc，它是chomsky哪一型文法？
A、0型
B、1型
C、2型
D、3型
2、编译程序必须完成的工作有
①词法分析②语法分析③语义分析④代码生成⑤中间代码生成⑥代码优化
①②③④B、①②③④⑤C、①②③④⑥D、①②③④⑤⑥
3、LR（K）文法________二义性的。
A、都是
B、都不是
C、不一定都是
4、语法分析的常用方法是________。
①自顶向下②自底向上③自左向右④自右向左
A、①②③④
B、①②
C、③④
D、①②③
5、用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行，这种说法
A、不正确
B、正确
6、生成非0开头的正偶数集的文法是______________。
A、Z::=ABC
B、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
C、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
7、文法G所描述的语言是的集合
A、文法G的字汇表V中所有符号组成的符号串
B、文法G的字汇表V的闭包V*中的所有符号串
C、由文法的开始符号推出的所有符号串
D、由文法的开始符号推出的所有终结符号串。
8、给定文法G[I]:I→I1|I0|Ia|Ic|a|b|c, 下面符号串中，为该文法句子的是。
①ab0 ②a0c01 ③aaa ④bc10
A、①
B、②③④
C、③④
D、①②③④