2013编译原理复习题及答案

H→M|ε 答：

文法的 FIRST集和FOLLOW集

非终结符 S D T M H FIRST集 {a}..... {a ，ε} {b}..... {b}..... {b ，ε} FOLLOW集 {# ，b} {# ，b} {e}.... {e}.... {e}.... 由于predict（D→STe）∩predict（D→ε）={a}∩{# ，b}= predict（H→M）∩predict（H→ε）={ b }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表：

S D T M H

7． 某语言的拓广文法G′为： (0) S′→S (1) S → Db|B (2) D → d|ε (3) B → Ba|ε

证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。 答：

a →aD. →STe e →ε b →ε →bM →bH →M. # →ε 拓广文法G'，增加产生式S'→S 在项目集I0中： 有移进项目D →·d 归约项目D →·和B →·

存在移进-归约和归约-归约冲突，所以G不是LR(0)文法。

若产生式排序为： (0) S'→S (1) S → Db (2) S → B (3) D → d (4) D →ε (5) B → Ba (6) B →ε

G′的LR(0)项目集族及识别活前缀的DFA如下图：

由产生式知 Follow(S)={#} Follow(D)= {b}

Follow(B)= {a ,#} 在I0中:

Follow(D) ∩{d}={ b} ∩{d}= Follow(B) ∩{d}= { a ,#} ∩{d}= Follow(D) ∩ Follow(B)= {b}∩{a ,#} = 在I3中:

Follow(S) ∩{a}={#}∩{a}=

所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法, 构造的SLR(1)分析表如下表：

ACTION 状态 b 0 1 2 3 4 5 6

8． 给出与正规式R＝（ab）*（a|b*）ba等价的NFA。 答：

与正规式R等价的NFA如下图

r4 S5 r3 d S4 a r6 S6 r5 # r6 acc r2 r1 r5 S 1 D 2 B 3 GOTO

9． 给出与正规式R＝（(ab)*|b）*（a|(ba)*）a 等价的NFA。 答：

与正规式R等价的NFA如下图

10． 给出与正规式 R＝（aba）*（(ba)*|b）b等价的NFA。 答：

与正规式R等价的NFA如下图

11． 将下图的NFA确定化为DFA。

答：

用子集法确定化如下表

I {X,1,2} {1,2}.. {1,2,3} {1,2,Y} 确定化后如下图：

Ia {1,2}.. {1,2}.. {1,2,Y} {1,2}.. Ib {1,2,3} {1,2,3} {1,2,3} {1,2,3} 状态 X 1 2 3