编译原理之语法分析-自下而上分析(三)
从不洗头的程序猿 人气:2在上一篇博客中我们已经讲过如何构造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)
显然，在I1中面对符号E我们无法判断要进行归约还是移进，及存在S-R冲突。
同样，在I2中面对终结符id,也存在着S-R冲突。
因此该文法不是LR(0)文法。
5、算出Follow集，然后判断能否使用SLR的方法消除冲突，如果可以则是SLR文法
在I1中， Follow(S)={#} 不包含终结符+,因此I1中的S-R冲突可以消解。
在I2中，Follow(E)={ #, ),+ },不包含终结符( ,因此I2的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)分析表比较系统的描述，可根据上述例子去理解一下：
以上均为个人学习总结，如有错误或异议欢迎提出（自下而上分析法未完待续......）。
加载全部内容