SLR分析表的构造PPT学习教案

1、会计学1 SLR分析表的构造分析表的构造 * R R 1 2 A S LRLR分析理论的一条基本定理分析理论的一条基本定理: : 在任何时候，在任何时候， 分析栈中的活前缀分析栈中的活前缀X X1 1X X2 2.X.Xm m的有效项目集正的有效项目集正 是栈顶状态是栈顶状态S Sm m所代表的那个集合。所代表的那个集合。 第1页/共20页 I0: SE E aA E bB I5: BcB B cB B d I3: EbB B cB B d I2:EaA A cA A d I1: S E I4:AcA A cA A d I8:Ac A I10:A d I6:EaA I7:EbB I11:B d

2、 I9:BcB b E a c c c c d d d d A A B B G: SE EaA|bB AcA|d BcB|d 项目集项目集I I5 5 对活前缀对活前缀 bc有效有效 考虑如下规范推导考虑如下规范推导 (1) S E bB bcB (2) S E bB bcB bccB (3) S E bB bcB bcd 第2页/共20页 I0: SE E aA E bB I5: BcB B cB B d I3: EbB B cB B d I2:EaA A cA A d I1: S E I4:AcA A cA A d I8:Ac A I10:A d I6:EaA I7:EbB I11:B d

3、 I9:BcB b E a c c c c d d d d A A B B 同一个项目可能对同一个项目可能对 好几个活前缀都有好几个活前缀都有 效效 G: SE EaA|bB AcA|d BcB|d 第3页/共20页 同一个活前缀，可能存在若干个项目对它都是有效同一个活前缀，可能存在若干个项目对它都是有效 的，而且告诉我们应做的事情各不相同，相互冲突的，而且告诉我们应做的事情各不相同，相互冲突 。 这种冲突通过向前多看几个输入符号这种冲突通过向前多看几个输入符号, , 或许能够获或许能够获 得解决。得解决。 第4页/共20页 第5页/共20页 移进归约冲突移进归约冲突 归约归约冲突归约归约冲突

4、 解决冲突策略解决冲突策略 （1）若）若a=b，则移进，则移进 （2）若）若aFollow(A), 则用则用 A 归约归约 （3）若）若aFollow(B), 则用则用 B归约归约 （4）此外，报错）此外，报错 第6页/共20页 第7页/共20页 第8页/共20页 I0: S E E E + T E T T T * * F T F F (E) F i I1: S E E E + T I2: E T T T * * F I3: T F I4: F ( E) E E + T E T T T * * F T F F (E) F i I5: F i I6: E E + T T T * * F T F

5、F (E) F i I7: T T * * F F (E) F i I8: F (E ) E E + T I9: E E + T T T * * F I10: T T * * F I11: F (E ) 移进移进-接受接受冲突冲突 移进移进-归约归约冲突冲突 移进移进-归约归约 冲突冲突 DFA 图图5.8 p112 第9页/共20页 I1: S E E E + T （0） S E （1） E E+T （2） E T （3） T T*F （4） T F （5） F (E) （6） F I 第10页/共20页 I2: E T T T * F （0） S E （1） E E+T （2） E T （

6、3） T T*F （4） T F （5） F (E) （6） F I 第11页/共20页 I9: E E + T T T * F (0) S E (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F I 第12页/共20页 更正更正 第13页/共20页 状状 态态 ACTIONGOTO i+*()#E TF 0s5s4123 1s6acc 2r2 s7r2r2 Follow(S )=# Follow(E)=# , ) , + (0) S E (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F

7、I 第14页/共20页 状状 态态 ACTIONGOTO i+*()#ETF 0s5s4123 1s6acc 2r2 s7r2r2 3r4 r4r4r4 4s5s4823 5r6 r6r6r6 6s5s493 7s5s410 8s6s11 9r1 s7r1r1 10r3 r3r3r3 11r5 r5r5r5 SLR(1)分析表分析表 图图5.5 p101 (0) S E (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F I 第15页/共20页 第16页/共20页 第17页/共20页 Follow(R) = # , = 识别活识别活 前缀的前缀的 DFADFA I0: SS S L=R S R L *R L i R L I6: SL=R R L L *R L i I2: SL=R R L I4:L* R R L L *R L i I1: SS I3:SR I7:L*R I8:RL I5:Li I9:SL=R = R * R L i R S * i i L * L I2 2: :移进移进- -归约冲突归约冲突 (0)S S (1)S L=R (2)S R (3)L *R (4)L i (5)R L 无法用无法用SLR(1)SLR(1)法解决法解决 第18页/共20页 r1 9 r5 r58 r3 r37 98S4