例:文法 S→E E→→E+T|T T→T*FF F→(E)|i
例: 文法 S’→E E→E+T│T T→T*F│F F→(E)│i
Lo= closure({S→·S}) S→>E,E→>·E+T,E→>·T,T>·T*,T→>●F,F→>·(E,F→>·i go(o, E) S>E●,E>E●+T 移进归约冲突 Logo(o,T) E→I·T→>IF 移进归约冲突 13-go(o, F) T→F● I4=go(l0() F→>(·E),E→>·E+T,E→>·T,T->·T*F,T→>·F,F→>·(E),F→>·1 Is=go(lo, 1)
I0=closure({S’→•S}) S’→•E, E→•E+T, E→•T, T→•T*F, T→•F, F→•(E), F →•i I1=go(I0 ,E) S’→E•, E→E•+T 移进-归约冲突 I2=go(I0 ,T) E→T•, T→T•*F 移进-归约冲突 I3=go(I0 ,F) T→F• I4=go(I0 ,( ) F→(•E), E→•E+T, E→•T, T→•T*F, T→•F, F→•(E), F →•i I5=go(I0 ,i) F →i•
6=go(l1,+) E→>E+·T,T→>·T*F,T→>●F,F>(E),F>i T→>T*●F,F→>(E),F→>·1 (4E) F→>(E·),E→>E·+T I9=go(6,T) E→>E+T●.T→xT●*F 移进-归约冲突 Lo=go(I, F) TT*F● 11go(l8,)) F→>(E)°
I6=go(I1 ,+) E→E+•T, T→•T*F, T→•F, F→•(E), F →•i I7=go(I2 ,*) T→T*•F, F→•(E), F →•i I8=go(I4 ,E) F→(E•), E→E•+T I9=go(I6 ,T) E→E+T•, T→T•*F 移进-归约冲突 I10=go(I7 ,F) T→T*F• I11=go(I8 ,) ) F→(E)•
四.SLR分析表的构造 1.SLR方法 当某个项目集形如 L={X>abB,A→a°,B→B時}时,出现了移进归 约冲突和归约归约冲突,可用如下方法解决,该 方法称为SLR方法
四. SLR分析表的构造 1. SLR方法 当某个项目集形如 I={X→•b, A→•, B→•}时, 出现了移进-归 约冲突和归约-归约冲突, 可用如下方法解决, 该 方法称为SLR方法
a是当前输入符号, 当{b}∩ FOLLOW(A)∩ FOLLOW(B)=Φ时 (1)a-b,则移进输入符a; (2)a∈ FOLLOW(A则用A→约, (3)a∈ FOLLOW(B,则用B→O归约 (4)此外出错
a是当前输入符号, 当{b}FOLLOW(A) FOLLOW(B)=Φ时 (1)a=b, 则移进输入符a; (2)aFOLLOW(A), 则用A→α归约; (3)aFOLLOW(B), 则用B→α归约; (4)此外出错
2.SLR分析表的构造 (1)C={L0,I1…,In},I对应状态i, lo= closure({S->S})为唯一初态; (2)对每个 若A→>0oaB∈L1,且go(12)1,则 Jaction[a_; 若A→>·∈I1,Ax为第个产生式, 则vb∈ FOLLOW(A, action[i,b]=丁i 若S→>S·∈L则 action[$=acc; (3)若go(1,A1,则goto[i,A (4)凡不能用规则(2)、(3)登记的表项均为“错误
2. SLR分析表的构造 (1)C={I0 ,I1 ,…,In}, Ii对应状态i, I0=closure({S’→•S})为唯一初态; (2)对每个Ii , 若A→•aIi , 且go(Ii ,a)=Ij , 则action[i,a]=sj; 若A→•Ii , A→为第j个产生式, 则bFOLLOW(A), action[i,b]=rj; 若S’→S•Ii , 则action[i,$]=acc; (3)若go(Ii ,A)=Ij , 则goto[i,A]=j; (4)凡不能用规则(2)、(3)登记的表项均为“错误
若由该方法构造的分析表,不含多重入 口,则该分析表称为SLR分析表相应文法 G称为SLR(1)文法
若由该方法构造的分析表, 不含多重入 口, 则该分析表称为SLR分析表,相应文法 G称为SLR(1)文法
LR分析表 状态 action goto SETF y4 2 0123456 s6 acc r2 [4 746 S4 246 r4 2 r6 r 6r6 y4 3 s5 10 73 Sr r r 5 5 135 r r5
LR分析表 状态0123456789 10 11 action goto i + * ( ) $ E T F s5 s4 1 2 3 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 8 2 3 r6 r6 r6 r6 s5 s4 9 3 s5 s4 10 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5
五.关于二义文法 例1:G(E)E→E+EE*E(E)i 拓广文法 0)S→E 1)E→E+E (2E→E*E (3)E→(E (4)E→i
五. 关于二义文法 例1: G(E) E→E+E|E*E|(E)|i 拓广文法: (0)S’→E (1)E→E+E (2)E→E*E (3)E→(E) (4)E→i
Lo= closure({S→·E}) S->·E,E→>·E+E,E→>·E*E,E→>·(E),E→·i go(o, E) S>E●E>●+EE→>E·*E 移进-归约冲突 l2=go(l0() E→>(E),E→>·E+E,E→·E*E,E→>·(E,E→>·1 go(o, 1) E→) E→>E+·E,E→>·+E,E→·*E,E→>(E,E→>·i s=go(l12*) E→>E*E,E→>E+E,E→·E*E,E→>(E)E→·i
I0=closure({S’→•E}) S’→•E, E→•E+E,E→•E*E, E→•(E), E →•i I1=go(I0 ,E) S’→E•, E→E•+E, E→E•*E 移进-归约冲突 I2=go(I0 ,( ) E→(•E), E→•E+E, E→•E*E, E→•(E), E →•i I3=go(I0 ,i) E→i• I4=go(I1 ,+) E→E+•E, E→•E+E, E→•E*E, E→•(E), E →•i I5=go(I1 ,*) E→E*•E, E→•E+E, E→•E*E, E→•(E), E →•i