语法分析—--自下而上分析.ppt

“改进的”SLR(1)分析： 对所有非终结符都求出其FOLLOW集合，这样只有归约项目仅对面临输入符号包含在该归约项目左部非终结符的FOLLOW集合中，才采取用该产生式归约的动作。 改进的SLR(1)分析表的ACTION表和GOTO表的构造步骤：a) 若项目A→? ? a?属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACTION[k,a]为Sjb) 若项目A→? ?属于Ik ，则对a为任何终结符或‘#’，且满足a?FOLLOW(A)时，置ACTION[k,a] = rj ，j为产生式在文法G‘中的编号c) 若GO(Ik,A)= Ij ，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号d) 若项目S‘→S ?属于Ik ，则置ACTION[k,#] = acce) 其它填上“报错标志” 仍有许多文法构造的LR(0)项目集规范族存在的动作冲突不能用SLR(1)方法解决 LR(1)分析 若项目集[A→??B?]属于I时，则[B→??]也属于I 把FIRST(?)作为用产生式归约的搜索符（称为向前搜索符），作为用产生式B→?归约时查看的符号集合（用以代替SLR(1)分析中的FOLLOW集），并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR(1)方法 LR(1)项目集族的构造：针对初始项目S’→?S,#求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。 1）构造LR（1）项目集的闭包函数a)I的项目都在CLOSURE(I)中b)若A→? ? B?，a属于CLOSURE(I)， B→ ?是文法的产生式，??V*，b?FIRST(?a),则B→? ?,b也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大 2)转换函数的构造GOTO（I，X）= CLOSURE（J）其中：I为LR(1)的项目集，X为一文法符号 J={任何形如A→?X ? ?,a的项目| A→? ? X ?,a属于I} I0: S’ ? ? S, # S ? ? aAd, # S ? ? bAc, # S ? ? aec, # S ? ? bed, # 文法G‘：(0) S’ ? S(1) S ? aAd (2) S ? bAc(3) S ? aec(4) S ? bed(5) A ? e I1: S’ ? S ?, # I2: S ? a ?Ad, # S ? a ? ec, # A ? ? e, d I3: S ? b ? Ac, # S ? b ? ed, # A ? ? e, c I4: S ? aA ? d, # I5: S ? ae ? c, # A ? e ?, d I6: S ? bA ? c, # I7: S ? be ? d, # A ? e ?, c I8: S ? aAd ?, # I9: S ? ae c ?, # I10: S ? bAc ?, # I11: S ? bed ?, # 查看I5 ，I7中的冲突，体会LR(1)如何解决 LR(1)分析表的构造 1) 若项目[A→? ? a?,b]属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACTION[k,a]为Sj 2) 若项目[A→? ? ,a]属于Ik ，则对a为任何终结符或‘#’，置ACTION[k,a] = rj ，j为产生式在文法G‘中的编号 3) 若GO(Ik,A)= Ij ，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号 4) 若项目[S‘→S ? ,#]属于Ik ，则置ACTION[k,#] = acc 5) 其它填上“报错标志” LR(1)项目集的构造对某些同心集的分裂可能使状态数目剧烈的增长 文法G‘：(0) S’ ? S(1) B ? aB (2) S ? BB(3) B ? b I0: S’ ? ? S, # S ? ? BB, # B ? ? aB, a/b B ? ? b, a/b I1: S’ ? S ?, # I2: S ? B ? B, # B ? ? a B, # B ? ? b, # I5: S ? B B ?, # I6: S ? a ? B, # B ? ? aB, # B ? ? b, # I9: B ? a B ?, # I4: B ? b ?, a/b I3: B ? a ? B, a/b B ? ? aB, a/b B ? ? b, a/b I8: B ? a B ?, a/b I7: B ? b ?, # S B b b B b b a a a a B B LR(1)项目集和转换函数 分析可发现I3和I6 ， I4和I7 ， I8和I9分别为同心集 I3: B ? a ? B, a/b B