LR分析中shift/reduce reduce/reduce冲突解决方案SLR(1)与LR(1)

此篇文章要求读者对编译原理前端部分有一定了解 此篇文章中，我们以大写英文作为非终结符，小写英文作为终结符

1. LR(0)分析法简述

LR分析法从左至右移进输入的终结符（词法分析器的输出实际是token，但在语法分析阶段会代表是一个终结符），并将终结符压入到堆栈，称为shift。如果当前栈上的符号恰好符合某个非终结符的生成式，则此时进行归约操作：将这些符号弹出栈，然后将规约后的非终结符压入堆栈，这一步就称为reduce。然后继续上面的步骤，直到没有输入。 如果最终栈上只有一个非终结符，且该非终结符就是目标符号，那证明识别成功，否则识别失败。 名称LR得名于：从左(Left)到右扫描（L）,反向（Reverse）最右推导（R）。

2. LR(0)分析法的不足

上面描述的算法存在一个问题，我们以下面的语法为例说明：

// 例1
B : A c
A : b d
  | b

对于上面的语法，当语法分析器遇到终结符b时，面临着两个选择，一个是继续移进下一个终结符，一个是使用生成式A : b进行归约。这种情况称为shift/reduce冲突。 继续看下面一个例子：

// 例2
A : b
C : b
D : A a
E : C d

对于上面的语法，当语法分析器遇到终结符b时，面临着两个选择，一个是根据A : b，归约为A，另一个选择是使用生成式C : b进行归约。这种情况称为reduce/reduce冲突。

因为这两种冲突的存在导致了LR(0)分析法在实际语法分析中基本不可用，必须找到解决这两种冲突的方案才行，那么如何这两种冲突呢？

3. SLR(1)

对于这两种冲突，我们首先先看一种简单的解决方案：SLR(1) (Simple LR)分析法。 SLR(1)分析法首先求出所有非终结符的Follow Set，即 跟在非终结符之后的所有终结符的集合，然后前瞻一个符号（即从词法分析器中预先读入下一个终结符），如果该前瞻符号在一个非终结符的Follow Set中，就根据此非终结符的生成式进行归约。

我们以上面的例2为例，SLR(1)分析器先求出A的Follow Set为{a},C的Follow Set为{b}，假设当前输入为b a，输入b之后，语法分析器面临选择：归约到A or 归约到C，此时分析器前瞻一个符号即c，由于c属于A的Follow Set，所以分析器选择归约到A。

上面的例1也可以通过此算法解决shift/reduce冲突。

遗憾的是SLR(1)依然存在问题，这里举个例子就清楚了：

// 例3
T : S
S : aAd
S : bAc
S : aec
S : bed
A : e

首先求出各个非终结符的Follow Set:

Follow(T) = {}
Follow(S) = {}
Follow(A) = {d, c}

我们假设当前的输入为a e c, 当输入e时，SLR(1)分析器面临两个选择：继续移进下一个符号 or 根据A : e归约到A，此时SLR(1)分析器前瞻符号c，c存在于Follow(A)中，但此时又可以选择移进c，所以SLR(1)此时又面临着冲突了。

SLR(1)不足之处在于Follow Set太宽泛，处于Follow Set中的前瞻符号不一定能合法的跟在非终结符之后。实际上SLR(1)忽略了分析的上下文，针对SLR(1)的不足由提出了LR(1)分析法。

4. LR(1)

LR(1)的基本原理就是只要前瞻符号能合法跟在归约的非终结符之后就可以进行归约，LR(1)会为每个生成式绑定一个** LookAhead Set**，只有前瞻符号处于这个集合之中才进行归约，它是Follow Set的子集。那么LookAhead Set如何生成呢？

4.1 LookAhead Set生成

我们将生成式一般化为下面的样子：

s -> α .x β， C 
x -> . r

其中 s,x都是非终结符，α β r可以是终结符也可以是非终结符，C 为生成式的LookAhead Set。

x的LookAhead Set = First(β C)，即β的FirstSet与C串起来之后的First集

First Set可以理解为非终结符所有生成式中第一个终结符的集合

5. Merak

我将LR(1)分析算法封装成了一个Golang Parser库：Merak，并且用它实现了一个面向对象语言的Parser: Mizar。对此有兴趣的同学可以试用下，它将为你省略手写语法分析器的过程，节省宝贵的时间投入到更加有趣的编译器后端工作中。