7、给文法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 BZ B Q DZ D a A A Q Q Q A A b Q BZ D D DZ B B 将S、A、BZ、B、Q、DZ、D重新命名，分别用0、1、2、3、4、5、6表示。因为2、5中含有Z，所以它们为终态。因此有： 0 1 2 3 4 5 a 1 1 4 4 4 1 b 4 2 6 6 5 3 6 1 3 初始分划得：终态组｛2,5｝，非终态组｛0,1,3,46｝ Π0：｛2,5｝,｛0,1,3,4,6｝

对｛0,1,3,4,6｝进行审查： {1,4}输入b到达｛2,5｝，而{0,3,6}输入b到达｛3,4,6｝，故得到新分划｛1,4｝,｛0,3,6｝ Π1：｛2,5｝,｛1,4｝,｛0,3,6｝

对｛0,3,6｝进行审查： {0}经过b到达｛2｝，{3,6}经过b到达｛3,6｝，故得到新分划｛0｝，｛3,6｝ Π3：得到最后划分{0}，{1,4}，{2,5}，{3,6}

重新命名，以A，B，C，D分别代替{0}，{1,4}，{2,5}，{3,6},其中A为始态，C为终态，可得到最小DFA如下：

2、自顶向下方法 (一) 设文法G(E)：

E→ E + T | T T→ T * F | F F→ i | ( E )

(1) 判断是否为LL(1)文法. (2) 构造文法的预测分析表. 解：详见P93-96例题。

(1) 由于文法中含有左递归，所以必须先消除左递归，使文法变为：

E→TE`

E`→+TE`|ε T→FT`

T`→*FT`|ε F→ i | ( E ) FIRST集合如下：

FIRST（E）={(,i} FIRST（E`）={+,ε} FIRST（T）={(,i} FIRST（T`）={*,ε} FIRST（F）={(,i} FOLLOW集合如下：

FOLLOW（E）={),#} FOLLOW（E`）={),#} FOLLOW（T）={+,),#} FOLLOW（T`）={+,),#} FOLLOW（F）={+,*,),#}

各产生式的SELECT集合如下： SELECT（E→TE`）={(,i} SELECT（E`→+TE`）={+} SELECT（E`→|ε）={),#} SELECT（T→FT`）={(,i} SELECT（T`→*FT`）={*} SELECT（T`→|ε）={+,),#} SELECT（F→ i）={i } SELECT（F→ ( E )）={(}

由上可知有相同左部产生式的SELECT集合的交集为空，故文法是LL(1)文法。 （2）构造文法的预测分析表如下：

E E` T T` F i →TE` →FT` → i + →+TE` →ε * →*FT` ( →TE` →FT` → ( E ) ) →ε →ε # →ε →ε (二) P101 6.(4) 改写下面文法为LL(1)文法，井对每个LL(1)文法构造相应的预测分析表。

解：

3、自底向上方法 已知文法G(E):

[0] S'→ E [1] E→ E + T

[2] E→ T

[3] T→ T * F [4] T→ F [5] F→ ( E ) [6] F→ i (1) 证明该文法是SLR(1)文法.

(2) 若已给出下面的SLR(1)分析表，试分析句子(i + ( * i ))#输入串出错的位置。

状态 0 1 2 3 4 5 6 7 8 9 10 11 ACTION i S5 S5 S5 S5 + S6 r2 r4 r6 S6 r1 r3 r5 * S7 r4 r6 S7 r3 r5 ( S4 S4 S4 S4 ) r2 r4 r6 S11 r1 r3 r5 # acc r2 r4 r6 r1 r3 r5 E 1 8 GOTO T 2 2 9 F 3 3 3 10 3、解：（1）：

先分析LR（0）项目：