2013编译原理复习题及答案

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 5 6

14． 某语言的文法G为： E → aTd|ε T → Eb|a

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

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

S2 S2 b r2 r2 S6 r1 d r4 S5 r3 # r2 acc r2 r1 T 1 4 B 3 GOTO 在项目集I0中： 有移进项目E →·aTd 和归约项目E→·

存在移进-归约冲突，所以G不是LR(0)文法。 若产生式排序为： (0) S′→E (1) E → aTd (2) E →ε (3) T → Eb (4) T → a

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

.

由产生式知： Follow(E)={# ，b} Follow(T)= {d} 在I0 ，I2中:

Follow(E) ∩{a}={# ，b} ∩{a}= 在I5 中: