《编译原理》期末试题（三）
1、 从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？ 答：从优化的范围的角度，优化可以分为局部优化和全局优化两类； 对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。 2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:= 四元式序列：
三元式序列: OP ARG1 ARG2
(1) (* b， c ) (2) (* b， d ) (3) (+ (1)， (2)) (4) (:= (3)， a)
(1) (*， b， c， t1) (2) (*， b， d， t2) (3) (+， t1， t2，t3) (4) (:=， t3， /， a)
3、对于文法G(S):
S ?bMbM ?(L|aL ?Ma）
答：1） S?bMb?b(Lb?b(Ma)b 2） 短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma)
b ( S M b T L M a ) 三、 设有字母表{a，b}上的正规式R=(ab|a)*。
解：（1）
2 - 0 ε a 1 a b ε + 3
（2）将（1）所得的非确定有限自动机确定化
ε a b -0 1 1 3 12 2 1 +3 第21页共6页
2 +
-+ a 0 b a 1 + a
（3）对（2）得到的DFA化简，合并状态0和2 为状态2：
2 -+ b a 1 +
（4）令状态1和2分别对应非终结符B和A
G: A→aB|a|ε； B→aB|bA|a|b|ε；可化简为：G: A→aB|ε；B→aB|bA|ε
a 四、 设将文法G改写成等价的LL(1)文法，并构造预测分析表。
G：S→S*aT|aT|*aT； T→+aT|+a
解：消除左递归后的文法G’: S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公因子得文法G’’: S→aTS’|*aTS’
S’→*aTS’|ε T→+aT’
T’→T|ε Select(S→aTS’)={a} Select(S→*aTS’)={*}
Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}
Select(S’→ε)=Follow(s’)={#}
Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}
Select(T’→T)=First(T) ={+}
Select(T’→ ε)=Follow(T’)={*,#}
Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表： * + a # S →*aTS’ →aTS’ 第22页共6页
S’ →*aTS’ T T’ → ε →ε → ε →+aT’ →T 6设文法G 为： S→A；A→BA|ε；B→aB|b
解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4)
B→aB (5) B→b ； FIRST(A) = {ε, a, b}；FIRST(B) = {a, b}
构造的DFA 如下:
项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。
（2） LR(1)分析表如下：
(3)输入串abab 的分析过程为：
第23页共6页
简答题 3、设有文法G[S]: S→S(S)S|ε，该文法是否为二义文法？说明理由。 答：是二义的，因为对于（）（）可以构造两棵不同的语法树。 S S
S ( S ) S S ( S ) S
ε ε S ( S ) S S ( S ) S ε ε
ε ε ε ε ε ε
五、 给定文法G[S]：
S→aA|bQ； A→aA|bB|b；B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；E→aB|bF
F→bD|aE|b
构造相应的最小的DFA 。
解：先构造其NFA： 用子集法将NFA确定化：
S A Q BZ DZ D B a A A Q Q A A Q b Q BZ DZ D B B D
第24页共6页
将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。
令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割：
P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b进行分割： P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 进行分割，仍不变。 再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。 最小化为右上图。
六、 对文法G(S)：S → a | ^ | (T)；T → T，S | S
答：(1)
FIRSTVT(S)?{a,^,(}FIRSTVT(T)?{,,a,^,(}
LASTVT(S)?{a,^,)}LASTVT(T)?{,,a,^,)} a ^ ) a ^ ( ) , # > > > > > > = > > > < (2) 是算符优先文法，因为任何两个
终结符之间至多只有一种优先关系。（2分）
(3) 给出输入串(a,a)#的算符优先
分析过程。 步骤 1 2 3 4 5 6 7 8 9 10 栈 # #( #(a #(N #(N, #(N,a #(N,N #(N #(N) #N ( < < < = < , < < < > > # < < 当前输入字符 剩余输入串 动作 ( a,a# #<( 移进 a ,a)# (, 归约 , a)# (<, 移进 a )# ,) 归约 ） # ,>) 归约 ) # (=) 移进 # )># 归约 # 接受 第25页共6页