编译原理_ 4章_ 3 _ LR分析.pptVIP

例：构造G[S]的项目集规范族 S?abdD S?aBc B?b S’?S S’??S, S??abdD , S??aBc I0=Closure({S’??S})： I1=GO(I0, S)： S’?S? I2=GO(I0, a)： VN={S’,S,B,D} VT={a,b,c,d} S?a?bdD, S?a?Bc, B??b I3=GO(I2, b)： S?ab?dD, B?b? I4=GO(I2, B)： S?aB?c I5=GO(I3, d)： S?abd?D, D??d I6=GO(I4, c)： S?aBc? D?d I7=GO(I5, D)： S?abdD? I8=GO(I5, d)： D?d? 夕药赣坍逼耪絮死工舶须砰孟沼脾吐集树衷锯眷麦窃敦级派抽汀末清炔牵编译原理_ 4章_ 3 _ LR分析编译原理_ 4章_ 3 _ LR分析 S’??S, S??abdD , S??aBc I0=Closure(S’??S)： I1=GO(I0, S)： S’?S? I2=GO(I0, a)： S?a?bdD, S?a?Bc, B??b I3=GO(I2, b)： S?ab?dD, B?b? I4=GO(I2, B)： S?aB?c I5=GO(I3, d)： S?abd?D, D??d I6=GO(I4, c)： S?aBc? I7=GO(I5, D)： S?abdD? I8=GO(I5, d)： D?d? S’??S S??abdD S??aBc I0 S’?S? I1 S?a?bdD S?a?Bc B??b I2 S?ab?dD B?b? I3 S?aB?c I4 S?abd?D D??d I5 S?aBc? I6 S?abdD? I7 D?d? I8 S a b B d c D d 什罐硅踞事稀洁氟剂箍戮涸肋莉州潮干盖家驹荫捂揍署赞拦止评葬怪鞠亭编译原理_ 4章_ 3 _ LR分析编译原理_ 4章_ 3 _ LR分析 S’??S S??abdD S??aBc I0 S’?S? I1 S?a?bdD S?a?Bc B??b I2 S?ab?dD B?b? I3 S?aB?c I4 S?abd?D D??d I5 S?aBc? I6 S?abdD? I7 D?d? I8 S a b B d c D d 考虑I3，有： Action(3, d) = S5 Action(3, x) = r4 (2) S?abdD (3) S?aBc (4) B?b (1) S’?S (5) D?d 因为FOLLOW(B)={c}，如果b归约为B，则期望后面出现c，故令： Action(3, d) = S5 Action(3, c) = r4 Action(3, x) = Err (x≠c, x≠d) 痕硝麻呻纵纶埔氢滓纸癸耕芋蜜浑纺翠侣臻慨摆缓嚣闻匆齐派猩匡白弧贸编译原理_ 4章_ 3 _ LR分析编译原理_ 4章_ 3 _ LR分析 4.3.3 SLR(1)分析法 (1) GO(Ii, a)=Ij，若a?VT，则置Action(i, a)=Sj；若a?VN，则置Goto(i, a)=j (2) 对A?α??Ii, A不是开始符号,对任何a?FOLLOW(A),置Action(i, a)=rk (3) 对A?α??Ii, A是开始符号，置Action(i, #)=acc。 (4) 分析表中的空白表示出错。 SLR(1)分析表构造算法： 茅灭驳味额慧迄而穿拈概厌豫知晚选川香瞒紧瘟射挡宜施鲁缅转轨闸哼寐编译原理_ 4章_ 3 _ LR分析编译原理_ 4章_ 3 _ LR分析 构造FOLLOW集合 S?abdD S?aBc B?b S’?S D?d First(S’)= First(S)= First(B)= First(D)= First(S’)={a} First(S)={a} First(B)={b} First(D)={d} Follow(S’)={#} Follow(S)={} Follow(B)={} Follow(D)={} Follow(S)={#} (1) 置初值：对任一A?VN，令FOLLOW(A)={}，若A是开始符号，则FOLLOW(A)={#}； (2) 若有A?αBβ，B?VN，置FOLLOW(B)=FOLLOW(B) ∪ ( FIRST(β)-{ε} )； (3) 若有A?αB，置FOLLOW(B)=FOLLOW(B) ∪ FOLLOW(A)； (4) 若有A?αBβ, β?ε，置FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)； * Follow(B)={c} Follow(D)={#} 只耐端貌污绑维佩缎吝睫呐催螺捉嫂液万势淮然硫酞浆捍谚鬼翱维拘钻肥编译原理_ 4章_ 3 _ LR分析编译原理_ 4章_