《SLR分析表的构造》课件

图5.7p106识别文法活前缀的DFA从初态出发,经读出活前缀γ后,而到达的项目集称为活前缀γ的有效项目集I0:S'

•E

E•aA

E•bBI5:Bc•B

B•cB

B•dI3:Eb•B

B•cB

B•dI2:Ea•A

A•cA

A•dI1:S'E•I4:Ac•A

A•cA

A•dI8:AcA•I10:Ad

•I6:EaA

•I7:EbB•I11:Bd

•I9:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B有效项目如果存在规范推导则项目A

1·

2

对活前缀

1

是有效的。如果

2

，应该移进如果

2=

，应该用产生式A

1归约

*R

R

1

2

A

S'LR分析理论的一条基本定理:在任何时候，分析栈中的活前缀X1X2...Xm的有效项目集正是栈顶状态Sm所代表的那个集合。I0:S'

•EE•aA

E•bBI5:Bc•B

B•cB

B•dI3:Eb•B

B•cB

B•dI2:Ea•A

A•cA

A•dI1:S'E•I4:Ac•A

A•cA

A•dI8:AcA•I10:Ad

•I6:EaA

•I7:EbB•I11:Bd

•I9:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

BG':

S'→EE→aA|bBA→cA|dB→cB|d

项目集I5对活前缀bc有效考虑如下规范推导(1)

SE

bB

bcB(2)

SE

bB

bcB

bccB(3)SE

bB

bcB

bcdI0:S'

•EE•aA

E•bBI5:Bc•B

B•cB

B•dI3:Eb•B

B•cB

B•dI2:Ea•A

A•cA

A•dI1:S'E•I4:Ac•A

A•cA

A•dI8:AcA•I10:Ad

•I6:EaA

•I7:EbB•I11:Bd

•I9:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B同一个项目可能对好几个活前缀都有效G':

S'→EE→aA|bBA→cA|dB→cB|d

同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几个输入符号,或许能够获得解决。5.3.3SLR分析表的构造SLR(1)分析法的引入:LR(0)文法的活前缀识别自动机的每一状态(项目集)都不含冲突性的项目大多数的程序设计语言的文法不能满足LR(0)文法的条件用向前查看一个符号的办法解决冲突例：设文法G的LR(0)项目集规范族中含有如下一个项目集（状态）I：I={ X

•b

/*移进项目*/ A

• /*归约项目*/

Bγ• /*归约项目*/}移进－归约冲突归约－归约冲突解决冲突策略（1）若a=b，则移进（2）若a∈Follow(A),则用A

归约（3）若a∈Follow(B),则用Bγ归约（4）此外，报错用SLR(1)方法解决冲突假定LR(0)规范族的一个项目集I中含有m个移进项目:

A1→α·a1β1，A2→α·a2β2，…，Am→α·amβm同时含有n个归约项目:

B1→α1·,B2→α2·,…,Bn→αn·如果集合｛a1,…,am｝、FOLLOW(B1)、…、FOLLOW(Bn)两两不相交，a是现行输入符号，则:（1）若a是某个ai，i=1,2,…,m，则移进；（2）若a∈FOLLOW(Bi)，i=1,2,…,n， 则用产生式Bi→αi进行归约；（3）此外，报错。例5.11p111

考虑下面的拓广文法(文法5.8)（0）S

E（1）EE+T（2）ET

（3）TT*F（4）TF（5）F(E)（6）FI构造其LR(0)项目集规范族I0:S

·EE

·E+TE

·TT

·T*FT

·FF

·(E)F

·iI1:S

E·E

E·+TI2:E

T·T

T·*FI3:T

F·I4:F

(·E)E

·E+TE

·TT

·T*FT

·FF

·(E)F

·iI5:F

i·I6:E

E+·TT

·T*FT

·FF

·(E)F

·iI7:T

T*·FF

·(E)F

·iI8:F

(E·)E

E·+TI9:E

E+T·T

T·*FI10:T

T*F·I11:F

(E)·移进-接受冲突移进-归约冲突移进-归约冲突DFA图5.8p112FOLLOW(S′)={#},

{#}∩{+}＝φ，因此I1中的冲突可解决。遇‘+’移进，遇‘#’接受其它情况则报错。

I1:S

E·E

E·+T（0）S

E（1）EE+T（2）ET

（3）TT*F（4）TF（5）F(E)（6）FISLR(1)解决方法FOLLOW(E)={+,),#}FOLLOW(E)∩{*}=

φ,因此I2中的冲突可解决。I2:E

T·T

T·*F（0）S

E（1）EE+T（2）ET

（3）TT*F（4）TF（5）F(E)（6）FIFOLLOW(E)={+,),#}FOLLOW(E)∩{*}=

φ,因此I9中的冲突可解决。I9:E

E+T·T

T·*F(0)S

E(1)EE+T(2)ET

(3)TT*F(4)TF(5)F(E)(6)FI构造SLR(1)分析表(1)若A→α·aβ

属于Ik

,且GO(Ik,a)=Ij

, 则置ACTION[k,a]为sj(2)若A→α·

属于Ik，a∈FOLLOW(A)，

则置ACTION[k,a]为rj j是产生式A→α的编号。(3)若S

→S·属于Ik, 则置ACTION[k,#]为acc(4)若GO(Ik,A)=Ij

， 则置GOTO[k,A]=j(5)凡不能用规则(1)~(4)填入的空白格均置为“出错标志”。更正状态ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r2Follow(S

)={#}Follow(E)={#,),+}(0)S

E(1)

EE+T(2)ET

(3)TT*F(4)TF(5)F(E)(6)FI状态ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5SLR(1)分析表图5.5p101(0)S

E(1)

EE+T(2)ET

(3)TT*F(4)TF(5)F(E)(6)FISLR分析表: 按上述方法构造分析表,每个入口不含多重定义SLR(1)文法: 具有SLR表的文法SLR分析器

: 使用SLR表的分析器例：一个非SLR文法的例子p113有如下文法: (文法5.9) (0)S'

S (1)SL=R (2)SR (3)L*R (4)Li (5)RL求LR(0)项目集规范族及识别活前缀的DFAFollow(R)={#,=}识别活前缀的DFAI0:S'

•S

S•L=R

S•RL•*RL•iR•LI6:SL=•R

R•L

L•*RL

•iI2:SL•=R

RL•

I4:L*•R

R•L

L•*R