内容发布更新时间 : 2024/11/16 21:46:23星期一 下面是文章的全部内容请认真阅读。

由产生式知 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 r4 S5 d S4 a r6 S6 # r6 acc r2 S 1 D 2 B 3 GOTO 4 5 6 r3 r5 r1 r5 8． 给出与正规式R＝（ab）*（a|b*）ba等价的NFA。 答：

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

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

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

答：

用子集法确定化如下表

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

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

13． 某语言的拓广文法G′为：

(0) S′→T (1) T →aBd|ε (2) B →Tb|ε

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

拓广文法G'，增加产生式S'→T 在项目集I0中：

有移进项目T →·aBd和归约项目T →· 存在移进-归约冲突，所以G不是LR(0)文法。 若产生式排序为： (0) S'→T (1) T →aBd (2) T →ε (3) B →Tb (4) B →ε

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

识别G′活前缀的DFA

由产生式知： Follow(T)={#,b} Follow(B)= {d} 在I0中：

Follow(T) ∩{a}={# ，b} ∩{a}= 在I2中：

Follow(B) ∩{a}= {d} ∩{a}= Follow(T) ∩{a}={# ，b} ∩{a}= Follow(B) ∩ Follow(T) = {d}∩{# ，b}=

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

SLR(1)分析表 ACTION name a 0 1 2 3 4 S2 S2 b r2 r2 S6 d r4 S5 # r2 acc r2 T 1 4 B 3 GOTO