silverlightbriefing-mix07.ppt

例：有如下文法G[E]： E ?TE’ E’?+TE’ | ε T ?FT’ T’?*FT’ | ε F?(E) | i FIRST(E)= FIRST(T)= FIRST(F) ={(,i} FIRST(E’)= {+,ε} FIRST(T’)= {*,ε} FOLLOW(E)= {),#} FOLLOW(E’)= FOLLOW(E)= {),#} FOLLOW(T)= FIRST(E’)-{ε} ∪FOLLOW(E) ={+,),#} FOLLOW(T’)= FOLLOW(T)= {+,),#} FOLLOW(F)= FIRST(T’)-{ε} ∪FOLLOW(T) ={*,+,),#} E ?TE’ E’?+TE’ | ε T ?FT’ T’?*FT’ | ε F?(E) | i FIRST(E)= FIRST(T)= FIRST(F) ={(,i} FIRST(E’)= {+,ε} FIRST(T’)= {*,ε} FOLLOW(E)= FOLLOW(E’)={),#} FOLLOW(T)= FOLLOW(T’)= {+,),#} FOLLOW(F)= {*,+,),#} F T’ T E’ E # i ) ( * + E ?TE’ E ?TE’ E’ ?+TE’ T ?FT’ T ?FT’ T’ ?*FT’ F ?(E) F ?i E’?ε E’?ε T’?ε T’?ε T’?ε 当元素内无产生式时，表明用非终结符号U向下推导时，遇到了不该出现的输入符号。所以元素内容可以存放转向出错处理的错误信息. LR分析器的逻辑结构： 总控程序 状 态 栈 s0 s1 sm … 符 号 栈 # x1 xm … a1a2…aiai+1…an# 分析表 动作表 状态转化表 输出 分析表是LR分析器的核心，它跟文法有关，它包括 动作表(Action)和状态转换表(Goto)两部分，总控程序 据分析表确定分析动作。 3 2 8 s4 s5 4 r4 r4 r4 r4 3 r2 r2 s7 r2 2 Acc s6 1 3 2 1 s4 s5 0 F T E # ) ( * + i Goto（转换） Aciton（动作） 状态 例：有文法G[E] S’?EE?aA|bBA?cA|dB?cB|d 文法G[S’]的项目有： 1.S’?.E 2.S’?E. 3.E?.aA 4.E?a.A 5.E?aA. 6.A?.cA 7. A?c.A 8. A?cA. 9. A?.d 10.A?d. 11.E?.bB 12.E?b.B 13.E?bB. 14.B?.cB 15.B?c.B 16.B?cB. 17.B?.d 18.B?d. ? S0 S’?.E E?.aAE?.bB E S1: S’?E. S2 a E?a.A A?.cAA?.d b S3 E?b.B B?.cBB?.d c S4 A?c.A A?.cAA?.d A S6: E?aA. d S10: A?d. c S5 B?c.B B?.cBB?.d B S7: E?bB. d S11: B?d. A S8: A?cA. d B S9: B?cB. c d c  状态 Action Goto 0 2 3 4 5 6 7 8 9 10 11 1 a b c d # E A B S2 1 S3 Acc S4 S10 6 S5 S11 7 ? S0 S’?.E E?.aA E S1: S’?E. S2 a E?a.A A?.cA b S3 E?b.B B?.cB c S4 A?c.A A?.cA A S6: E?aA. d S10: A?d. c S5 B?c.B B?.cB B S7: E?bB. d S11: B?d. A S8: A?cA. d B S9: B?cB. c d E?.bB A?.d B?.d A?.d B?.d c S4 S10 8 S5 S11 9 (0)S’?E(1)E?aA(2)E?bB (3)A?cA (4)A?d (5)B?cB(6)B?d r1 r1 r1 r1 r1 r2 r2 r2 r2 r2 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 r4 r4 r4 r4 r4 r6 r6 r6 r6 r6 r5 r5 r5 r5 11 r3 r3 r3 r3 10 r1 r1 s7 r1 9 s11 s6 8 10 s4 s5 7 3 9 s4 s