byyl-ch5.自底向上优先分析.ppt

6.5.1 LR(1) 分析思想 LR(1)分析 若[A→??B?]属于项目集I时，则[B→??]也属于I，把FIRST(?)作为用产生式B→?归约的有哪些信誉好的足球投注网站符（用以代替SLR(1)分析中的FOLLOW(B)），并把此有哪些信誉好的足球投注网站符号的集合也放在相应项目的后面，这种处理方法即为LR(1)方法 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: B? 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 B B a 文法G‘：(0)S’ ? S (1)B ? aB (2)S ? BB (3)B ? b LR(1)项目集和转换函数 向前有哪些信誉好的足球投注网站符集合 状态 ACTION GOTO a b # S B 0 S3 S4? ? 1 2 ?1 ? acc? 2 S6 S7? 5 3 S3 S4 ? 8 4 r3 r3 ? 5 ? r1 6? S6 S7? ? 9 7 r3 8 r2 r2 9 r2 6.5.1 LR(1) 分析思想 LR(1)的优缺点： 优点：LR(1)分析对有哪些信誉好的足球投注网站符的计算方法比较确切，没有无效归约，适应的文法更广 缺点：LR(1)分析表的状态数目庞大。 6.5.2 LALR(1)分析思想 LALR(1)方法是介于SLR(1)和LR(1)之间的一种方法，即其功能比SLR(1)强，比LR(1)弱。 它具有SLR(1)的状态数少的优点和LR(1)的适用范围广的优点。 LALR(1)分析 对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集 LALR(1)分析大大减少项目集（状态）的数目。 分析可发现I3和I6 ， I4和I7 ， I8和I9分别为同心集 I3: B ? a ? B, a/b B ? ? aB, a/b B ? ? b, a/b I6: B ? a ? B, # B ? ? aB, # B ? ? b, # I4: B ? b ?, a/b I7: B ? b ?, # I8: B ? a B ?, a/b I9: B ? a B ?, # I3,6: B ? a ? B, a/b/# B ? ? aB, a/b/# B ? ? b, a/b/# 合并为 I4,7: B ? b ?, a/b/# 合并为 I8,9: B ? a B ?, a/b/# 合并为 同心集合并后不包含冲突，是LALR(1)项目集 状态 ACTION GOTO a b # S B 0 S3,6 S4,7? ? 1 2 ?1 ? acc? 2 S3,6 S4,7? 5 3,6 S3,5 S4,7 ? 8,9 4,7 r3 r3 r3 5 ? r1 8,9 r2 r2 r2 二义性文法的应用 已知算术表达式文法，试构造该文法的LR分析表；并用来分析输入串i+i*i#的分析过程。 （1）E?E+E （2）E?E*E （3） E?(E)|i 该文法是一个二义性文法，设计出该文法的LR分析表，输入i+i*i#判断该输入串是否合法。 将文法拓广为： （0）E′?E （1）E?E+E （2）E?E*E （3） E?(E)|i + I0： E′?·E E?·E+E E?·E*E E?·(E) E?·i I1： E′?E· E?E·+E E?E·*E E I2： E? (·E) E?·E+E E?·E*E E?·(E) E?·i ( I3： E?i· i + I4： E?E+·E E?·E+E E?·E*E E?·(E) E?·i * I5： E?E*·E E?·E+E E?·E*E E?·(E) E?·i E I6： E? (E·) E?E·+E E?E·*E E I7： E?E+E· E?E·+E E?E·*E E I8： E?E*E· E?E·+E E?E·*E ) I9： E? (E) · ( i ( ( i * + + * * 在I1中，归约项目E′?E·实际上为接受项目。由于FOLLOW（E?）={#}也就是只有遇到句子的结束标志“#”才能接受；因而与移进项目的移进符号“+”，“*”不会冲突，所以可以用SLR(1)