内容发布更新时间 : 2024/5/23 18:32:03星期一 下面是文章的全部内容请认真阅读。

T H {b，d，ε} {d，ε} {e} {e} 由于predict（D→STe）∩predict（D→ε）={a}∩{# ，b ，d ，e }= predict（T→bH）∩predict（T→H）={b}∩{e }= predict（H→d）∩predict（H→ε）={ d }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表： a e b d S →aD. D →STe →ε →ε →ε T →H. →bH →H. H →ε →d.

6． 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。 S→aD D→STe|ε T→bM M→bH H→M|ε 答：

文法的 FIRST集和FOLLOW集 非终结符 FIRST集 FOLLOW集 S {a}..... {# ，b} D {a ，ε} {# ，b} T {b}..... {e}.... M {b}..... {e}.... H {e}.... {b ，ε} 由于predict（D→STe）∩predict（D→ε）={a}∩{# ，b}=

predict（H→M）∩predict（H→ε）={ b }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表： a e b S →aD. D →STe →ε T →bM M →bH H →ε →M.

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

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

# →ε # →ε

拓广文法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 GOTO 状态 b d a # S D B 0 r4 S4 r6 r6 1 2 3

1 2 3 4 5 6 S5 r3 S6 r5 acc r2 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 GOTO name a b d # T B 0 S2 r2 r2 1 1 acc 2 S2 r2 r4 r2 4 3 3 S5 4 S6 5 r1 r1 6 r3 14． 某语言的文法G为： E → aTd|ε T → Eb|a

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

拓广文法G'，增加产生式S'→E