Question

证明下列文法是LL(1)文法但不是SLR(1)文法

Answer 1

(1)首先该文法无左递归存在,没有公共左因子.

其次:对于S→AaAb|BbBa FIRST(AaAb)={a} FIRST(BbBa)={b}

FIRST(AaAb)∩FIRST(BbBa)=Φ

所以该文法是LL(1)文法.

(2)证明该文法不是SLR的.

文法的LR(0)项目集规范族为:

I0={S’→.S S→.AaAb S→.BbBa A→. B→.}

I1={ S’→ S. }

I2={ S→A.aAb }

I3={ S→B.bBa }

I4={ S→Aa.Ab A→. }

I5={ S→Bb.Ba B→. }

I6={ S→AaA.b }

I7={ S→BbB.a }

I8={ S→AaAb. }

I9={ S→BbBa. }

考察I0:

FOLLOW(A)={a,b} FOLLOW(B)={a,b} FOLLOW(A)∩FOLLOW(B)= {a,b}

产生规约-规约冲突.

所以该文法不是SLR(1)文法.