语法分析-自底向上分析.ppt

* 例：文法G 0)G→S 1)S →E=E 2)S →i 3)E →T 4)E →E+T 5)T →i 6)T →T*i 生成项目集规范族。 * 状态 LR(1)项目 转换函数 0 G→.S,# S →.E=E, # S →.i , # E →.T , =：+ E →.E+T , =：+ T →.i,=：*：+ T →.T*i , =：*：+ GO[0,S]=17 GO[0,E]=1 GO[0,i]=3 GO[0,T]=2 GO[0,E]=1 GO[0,i]=3 GO[0,T]=2 1 S →E.=E, # E →E.+T,=：+ GO[1,=]=4 GO[1,+]=5 2 E →T.,=：+ T →T.*i , =：*：+ GO[2,*]=11 3 S →i., # T →i.,=：*：+ 4 S →E=.E, # E →.T, #：+ E →.E+T , #：+ T →.i, #：+：* T →.T*i,#：+：* GO[4,E]=6 GO[4,T]=7 GO[4,E]=6 GO[4,i]=8 GO[4,T]=7 5 E →E+.T,=：+ T →.i, =：+：* T →.T*i,=：+：* GO[5,+]=10 GO[5,i]=9 GO[5,T]=10 状态 LR(1)项目 转换函数 6 S →E=E., # E →E.+T, #：+ GO[6,+]=13 7 E →T., #：+ T →T.*i,#：+：* GO[7,*]=15 8 T →i.,#：+：* 9 T →i.,=：+：* 10 E →E+T.,=：+ T →T.*i,=：+：* GO[10,*]=11 11 T →T*.i,=：+：* GO[11,i]=12 12 T →T*i.,=：+：* 13 E →E+.T, #：+ T →.i, # ：+：* T →.T*i, # ：+：* GO[13,+]=14 GO[13,i]=8 GO[13,T]=14 14 E →E+T., #：+ T →T.*i, # ：+：* GO[14,*]=15 15 T →T*.i, # ：+：* GO[15,i]=16 16 T →T*i., # ：+：* 17 G→S.,# 文法G 0)G→S 1)S →E=E 2)S →i 3)E →T 4)E →E+T 5)T →i 6)T →T*i 文法G 0)G→S 1)S →E=E 2)S →i 3)E →T 4)E →E+T 5)T →i 6)T →T*i C0= CLOSURE(G→.S,#)={G→.S,#、 S →.E=E, #、S →.i , # } ={G→.S,#、 S →.E=E, #、S →.i , #、 E →.T , =、 E →.E+T , =} ={G→.S,#、 S →.E=E, #、S →.i , #、 E →.T, =、E →.E+T, = 、 T →.i,=、T →.T*i , = 、E →.T , +、 E →.E+T , + } ={G→.S,#、 S →.E=E, #、S →.i , #、 E →.T , =、 E →.E+T , =、 T →.i,=、T →.T*i , = 、E →.T , +、 E →.E+T , +、 T →.i,*、 T →.T*i ,*、 T →.i,+、T →.T*i ,+ } ={G→.S,#、 S →.E=E, #、S →.i , #、 E →.T,=:+、 E →.E+T, =:+、 T →.i,=:*:+、T →.T*i , =:*:+} * LR(1)分析表的构造 设文法G’的LR(1)项目集规范族C={ C0, C1,…,Cn}, 每个项目集的下标作为分析器的状态,令包含项目[S’→.S,#]的项目集Ck的下标k为分析器初态，则构造LR(1)分析表的算法如下： 1) 若项目[A→α.aβ,b]∈Ci且GO[Ci,a]=Cj,为终结符,置ACTION[i,a]=Sj; 2) 若项目[A→α.,a]∈Ci ,则置ACTION[i,a]=rj(假定A→α是文法G’的第j条产生式); 3) 若项目[S’→S.,#]∈ Ci ,则置ACTION[i,#]=acc 4) 若GO[Ci,A]= Cj,A 为非终结符,则置GOTO[i,A]=j 5) 分析表中凡不能用规则1- 4添入信息的单元为空或均置上ERROR。 LR(1)文法：若按上述算法构造的LR(1)分析表不含 多重定义，称该文法是LR(1)文法。 * 状态 LR