编译原理之语法分析-自下而上分析(三)

　　在上一篇博客中我们已经讲过如何构造LR(0)分析表，SLR构造分析表的前五个步骤是与LR(0)一样的，因此这里就不再对前五个步骤讲解。

　　前五个步骤一样的原因：一个文法如果是SLR文法，则它一定是LR（0）文法，因此我们在判断它是不是SLR文法之前要先判断是不是LR(0)文法。

　　https://www.cnblogs.com/scm2019/p/12899757.html (前五个步骤可参考上一篇博客)

　　(一)SLR分析法

　　　　SLR分析法作用：SLR基于LR(0)，通过一个前看符号，来决定是否执行归约动作或执行哪个归约动作。

　　　　SLR分析法优点：1、有可能减少需要归约的情况 　　2、能够去除某些移进-归约冲突

　　　　SLR分析法缺点：仍然有冲突出现的可能。

　　　　SLR(1)解决冲突的办法：

　　　　首先看一下比较标准的解释：

　　　　举个例子理解上图，假如这里有一个项目集，如下图。

 　　　　　 很明显这是一个s-r冲突，所以它不属于LR(0)文法，但是根据SLR(1)的解决方法，我们可以先求出产生式左侧终结符的Follow集。

　　　  假如Follow(R) = { +, - } ，Follow(T) = { ！，* }

　　　  这时根据R和T的Follow集和移进项目圆点后的非终结符有以下三种情况：

　　　  1、当输入符号为 = 时，这时我们就把第一个产生式进行移进操作。

　　　  2、当输入符号属于Follow（R）时(+ 或者 -)，就将R->L·进行归约。

　　　  3、当输入符号属于Follow（T）时(! 或者 *)，就将T->T·进行归约。

　　　  以上为成功消除冲突的情况。

　　　  假如Follow(R) = { =, * } ，Follow(T) = { +，* }

 　　　　　 1、移进项目圆点后的终结符(=)属于Follow（R），因此报错，即还是存在移进-归约冲突。因为我们还是不知道当输入符号为=时，要对S->L·=R进行移进，还是对R->L·进行归约。

　　　  2、此外，Follow（R） ∩ Follow（T） = { * }，报错，即还是存在归约-归约冲突。因为我们还是不知道当输入符号为*时，要对R->L·进行归约，还是对T->L·进行归约。

　　　  以上为消除冲突失败的情况。

　　　  总结：如果想消除项目中的集冲突，必须满足以下两种情况（重要事情说三遍）

　　　　      总结：如果想消除项目中的集冲突，必须满足以下两种情况（重要事情说三遍）

　　　　　  总结：如果想消除项目中的集冲突，必须满足以下两种情况（重要事情说三遍）

　　　　　  1、移进项目圆点后的终结符(严格来说是圆点后的First集)，不属于归约项目的Follow集。

　　　　　  2、所有归约项目的Follow集两两相交必须为空。

　　　　（二）构造SLR分析表

　　　　　　，判断文法是否属于SLR文法，如果是给出SLR分析表

　　　　　　1、列出文法的规范项目集

 　　　　　　2、构造识别活前缀的NFA

　　　　3、识别或前缀的DFA

 　　　　　　4、根据DFA判断LR(0)

　　　　　　显然，在I₁中面对符号E我们无法判断要进行归约还是移进，及存在S-R冲突。

　　　　　　同样，在I₂中面对终结符id,也存在着S-R冲突。

　　　　　　因此该文法不是LR(0)文法。

　　　　5、算出Follow集，然后判断能否使用SLR的方法消除冲突，如果可以则是SLR文法　　　　　　　　

　　　　　　在I₁中， Follow(S)={#} 不包含终结符+,因此I₁中的S-R冲突可以消解。

　　　　　　在I₂中，Follow(E)={ #, ),+ },不包含终结符( ,因此I₂的S-R冲突可以消解。

　　　　　　综上所述，冲突能够被消除，该文法属于SLR(1)文法。

　　　　6、画出SLR(1)分析表

　　　　　    文法编号为:　　　　　　

　　　　　　1 : S->E

　　　　　　2 : E -> id

　　　　　　3 : E -> id(E)

　　　　　　4 : E -> E+ id

 　　　　　　　　构造SLR（1）方法技巧：

　　　　　　 其实LR(0)和SLR(1)分析表雷同，SLR(1)分析表只是比LR(0)分析表少几个归约项。

　　　　　　 假如该文法是一个LR（0）文法，那么跟上图不一样的是3、6、7所在的行应该填满，即3所在行全填r2，6所在行全填r4，7所在行全填r3。其余的和上图一模一样。

　　　　　　 但是为什么SLR(1)比LR(0)分析表少几个呢？

　　　　　　 其实我们找到r2对应的归约产生式为E->id，而发现Follow（E）={ (，+，# }，即Follow(E)中不存在id 和 ( ，因此就不需要将id 和 ( 所在列也填上r2，否则使我们发现错误不及时，造成效率低额问题。

　　　　　　 同理r3和r4对应归约产生式为 E -> id(E) 和  E -> E+ id，同样Follow（E）={ (，+，# }。因此id 和 （ 不需要填r3 和 r4。

　　　　如果还没明白我们再举一个例子，有如下文法。

 　　　　　　该文法LR(0)分析表为：

　　　　该文法SLR(1)分析表为：

　　　　　r1对应的归约产生式为S->BB·，r2和r3对应的归约产生式为B->aB· 和 B->b·

　　　　　在状态5所在的行，LR(0)分析表全部填写了r1，但是Follow（S）= { # }，并没有a和b，所以在SLR(1)分析表中，只需要在状态5的#所在列填写r1。

　　　　　同理，我们先计算r2和r3产生式的Follow集，Follow（B）= { a，b，# }，三个都有，因此在SLR（1）分析表中和LR(0)分析表中对应状态行都应该填写上。

　　　　　总结，LR(0)和SLR(0)分析表结构一样，唯一不同的就是归约项目所在的状态行，LR(0)不需要判断直接全部填写Rn，而在SLR(1)分析表中需要先判断Follow集，然后根据Follow集中已有的终结符去填SLR(1)表。

　　　　   下边分别给出构造LR(0)和SLR(1)分析表比较系统的描述，可根据上述例子去理解一下：

　　　　 以上均为个人学习总结，如有错误或异议欢迎提出（自下而上分析法未完待续......）。