《编译原理》期末总复习.pptVIP

SLR(1)分析法举例 对下列文法： (1)S′::=S (2)S::=bRST (3)S::=bR (4)R::=dSa (5)R::=e (6)T::=fRa (7)T::=f ①求各非终结符号的FIRST和FOLLOW集 ②构造该文法的SLR(1)分析表 ③分析符号串bebefea FIRST集 FIRST(S′)={b} FIRST(S)={b} FIRST(R)={d,e} FIRST(T)={f} FOLLOW集 FOLLOW(S′)={#} FOLLOW(S)={a,f,#} FOLLOW(R)={a,b,f,#} FOLLOW(T)=FOLLOW(S)={a,f,#} 文法的所有项目 1.S′::=?S 2. S′::=S? 3.S::=?bRST 4. S::=b?RST 5. S::=bR?ST 6.S::=bRS?T 7. S::=bRST? 8. S::=?bR 9.S::=b?R 10.S::=bR? 11.R::=?dSa 12.R::=d?Sa 13.R::=dS?a 14.R::=dSa? 15.R::=?e 16.R::=e? 17.T::=?fRa 18.T::=f?Ra 19.T::=fR?a 20.T::=fRa? 21.T::=?f 22.T::=f? 构造识别可归前缀的DFA S′::=?S S::=?bRST S::=?bR I0 S S′::=S? I1 b S::=b?RST S::=b?R R::=?dSa R::=?e I2 R S::=bR?ST S::=bR? S::=?bRST S::=?bR I3 e R::=d?Sa S::=?bRST S::=?bR I4 d R::=e? I5 S S::=bRS?T T::=?fRa T::=?f I6 b R::=dS?a S I7 b S::=bRST? I8 T f T::=f?Ra T::=f? R::=?dSa R::=?e I9 R::=dSa? I10 R T::=fR?a a a T::=fRa? d e I11 I12 冲突项目集 冲突项目集 SLR(1)分析表 状态 ACTION GOTO a b c d e f # S R T 0 1 2 3 4 5 6 7 8 9 10 11 12 1 S2 acc r2 r3 r3 r3 6 7 S4 S5 r5 r5 r5 r5 r7 r7 r7 S9 S10 r4 r4 r4 r4 r6 r6 r6 3 S2 FOLLOW(S)={a,f,#} S2 FOLLOW(R)={a,b,f,#} 8 r2 r2 11 S4 S5 FOLLOW(T)={a,f,#} S12 化简步骤1 1、初始划分由两个子集组成，即： ｛q4｝（终态） ｛q0,q1,q2,q3｝(非终态） ∏： q0 q1 q2 q3 0 q4 a b a b a b a b a b 初态 终态 ∏={｛q0,q1,q2,q3｝,｛q4｝} 化简步骤2 2、考查子集｛q0,q1,q2,q3｝ ∏={｛q0,q1,q2,q3｝,｛q4｝} 表示对q0、q1、q2、q3输入符号a转移到的下一状态所组成的集合。 ｛ q0,q1,q2,q3 ｝a： 化简步骤2－－（1） （1）｛q0,q1,q2,q3｝a= ∏={｛q0,q1,q2,q3｝,｛q4｝} q0 q1 q2 q3 0 q4 a b a b a b a b a b 初态 终态 ∏={｛q0,q1,q2｝， ｛q3｝，｛q4｝} {q1 }?{q0,q1,q2,q3} ｛q0,q1,q2,q3｝b={ q2, q3 ,q4} ?｛q0,q1,q2,q3｝ ?｛q4｝ ｛q0,q1,q2｝b={q2,q3｝ ｛q3｝b={q4} ｛q0,q1,q2,q3｝ ｛q0,q1,q2｝ ｛q3｝ 化简步骤2－－（2） （2）考查子集｛q0,q1,q2｝ q0 q1 q2 q3 0 q4 a b a b a b a b a b 初态 终态 ∏={｛q0,q1,q2｝，｛q3｝，｛q4｝} ∏={｛q0,q2｝， ｛q1｝,｛q3｝,｛q4｝} ｛q0,q1,q2｝a={ q1 }?{q0,q1,q2} ｛q0,q1,q2｝b={ q2 ,q3｝ ?｛q0,q1,q2｝ ｛q0,q1,q2｝ ｛q0,q2｝ ｛q1｝ 化简步骤2－－（3） （3）考查子集｛q0,q2｝ ∏={｛q0,q2｝,｛q1｝,｛q3｝,｛q4｝} ∏={｛q0,q2｝，｛q1｝,｛q3｝,｛q4｝} q0 q1 q2 q3 0 q4 a b a b a b a b a b 初态 终态 ｛q0,