SLR(1) 分析

LR(0) 分析的局限性：

• 满足要求的文法不多，如文法中含有产生式 $A\to ϵ$ 通常会遇到问题，对应的项目 $A\to .$ 是归约项目，容易引起移进-归约冲突
• 只根据栈顶状态确定进行移进还是归约

非 LR(0) 文法举例：

解决冲突的方法：向前查看一个符号

• 根据下一个输入符号是否属于要归约的非终结符的 Follow 集来决定是否进行归约
• 如果 LR(0) 状态中所有归约项中要归约的非终结符的 Follow 集互不相交，则可以解决归约-归约冲突
• 如果 LR(0) 状态中所有归约项中要归约的非终结符的 Follow 集与所有移进项目要移进的符号集互不相交，则可以解决移进-归约冲突

SLR(1) 分析表的构建

只需对 LR(0) 分析表 做一些修改：

• 若项目 $A\to \alpha .a\beta \in I_k$ 且 $\text{GO}(I_k,a)=I_j$，$a$ 为终结符，则 $\text{ACTION}[k,a]=sj$
• ! 若项目 $A\to \alpha .\in I_k$，则对任何终结符 $a\in Follow(A)$，$\text{ACTION}[k,a]=rj$，其中 $A\to \alpha$ 为第 $j$ 个产生式
• 若项目 $S^{\prime }\to S.\in I_k$，则 $\text{ACTION}[k,\#]=acc$
• 若 $\text{GO}(I_k,A)=I_j$，$A$ 为非终结符，则 $GOTO(k,A)=j$
• 其余位置为 $err$

SLR(1) 文法

按上述算法构造的分析表，如果各表项均无多重定义，则称该文法为 SLR(1) 文法

SLR(1)文法的 LR(0) FSM 中每个状态满足

• 该状态的任何项目 $A\to u.av$，不存在项目 $B\to w.$ 使得 $a\in Follow(B)$
• 对该状态的任何两个项目 $A\to u.$ 和 $B\to v.$，满足 $Follow(A)\cap Follow(b)=\varnothing$

局限性

只考虑所归约的非终结符的 Follow 符号，没有考虑非终结符 Follow 集中的符号是否也是句柄的 Follow 符号（一个输入符号属于所归约非终结符的 Follow 集合，未必是句柄后可以跟的符号），这会导致报错时机向后延迟。

$$\begin{array}{rl}S& \to aAc\\ S& \to bAb\\ A& \to d\end{array}$$

$A$ 的 Follow 集为 $\{c,b\}$，但如果分析过程中前文已经有了 $a$，则 $A$ 后面只能跟 $c$