考虑文法:S∷=AS|bA∷=SA|a(1)构造该文法LR(0)的DFA;(2)判定其是否是LR(0)文法?是否是SLR(1)文法?若是,则构造SLR(1)分析表。(3)试分析符号串bab是否是该文法的句子。

解:

(1)在上述文法中引入新的开始符号S’,并将S’::=S作为第0个规则,从而得到所谓的拓广文法G’,则其LR(0)项目有:

(1) S’∷=·S (2) S’∷=S· (3) S∷=·b

(4) S∷=b· (5) S∷=·AS (6) S∷=A·S

(7) S∷=AS· (8) A∷=·SA (9) A∷=S·A

(10) A∷=SA· (11) A∷=·a (12) A∷=a·

(2)由上述文法DFA中的状态I1可以看出,项目集中既存在移进项目A::= S·A和A::= ·a又存在规约项目S’::= S·,这些项目是冲突项目,所以该文法不是LR(0)文法。因为该项目集中的移进与规约项目只根据一个输入符号就可唯一确定分析动作,因此是SLR(1)文法,构造SLR(1)分析表:

FOLLOW(A)={b} FOLLOW(S)={ #, b }

状态

ACTION

GOTO

a

b

#

S

A

S4

S2

1

3

1

S4

acc

5

2

r2

r2

3

S2

6

4

r4

5

r3

6

r1

r1

规则顺序:r1:S→AS r2:S→b r3:A→SA r4:A→a

(3)分析符号串bab是否为该文法的句子

步骤

状态栈

符号栈

输入串

分析动作

下一状态

1

#

bab#

S2

2

2

2

#b

ab#

r2

GOTO[, S]=1

3

1

#S

ab#

S4

4

4

14

#Sa

b#

r4

GOTO[1, A]=5

5

15

#SA

b#

r3

GOTO[, A]=3

6

3

#A

b#

S2

2

7

32

#Ab

#

r2

GOTO[3, S]=6

8

36

#AS

#

r1

GOTO[, S]=1

9

1

#S

#

acc

成功

标签：文法,是否是,LR