编译原理 有文法G（S）这道题怎么做？

Question

有文法G（S）:
　S->aS
S->bS
S->a
　　　1）构造识别文法活缀的DFA
　 2）写出该文法的SLR（1）分析表

Answer 1

首先扩展文法为：   

1)   S1->S

2)   S->aS

3)   S->bS

4)   S->a

则：

I0 = Closure({S1->.S})={S1->.S,S->.aS,S->.bS,S->.a}

go(I0,S) = Closure({S1->S.})={S1->S.} = I1

go(I0,a) = Closure({S->a.S,S->a.})={S->a.S,S->.aS,S->.bS,S->.a,S->a.} = I2

go(I0,b) = Closure({S->b.S})={S->b.S,S->.aS,S->.bS,S->.a}=I3

go(I2,S) = closure({S->aS.})={S->aS.}=I4

go(I2,a) = Closure({S->a.S,S->a.}) = I2

go(I2,b) = Closure({S->b.S}) =I3

go(I3,S) = Closure({S->bS.}) = {S->bS.} = I5

go(I3,a) = Closure({S->a.S,S->a.}) = I2

go(I3,b) = Closure({S->b.S}) = I3

由图所示，状态I2,既有归约项目(S->a.)又有移近项目(S->.aS,S->.bS,S->.a)，产生冲突。当用SRL分析法时，需向前看一步，即求出：

Follow(S) = Follow(S1) = {#}

则，Follow(S)∩{a,b} =∮

故而Action(I2,a) = s2

Action(I2,b) = s3

Action(I2,#) = r4

则构造出srl分析表如下所示：

    Action                                                            Goto

    a     b     # S

I0     s2  s3       1

I1 acc

I2                 s2  s3 r4 4

I3                 s2  s3 5

I4     r2  r2    r2

I5     r3  r3 r3