SLR(1)分析法

文章目录

• SLR分析法的基本思想
• SLR(1)分析表的构造

LR(0)文法要求文法的每一个LR(0)项目都不含有冲突的项目，这个条件比较苛刻。对于大多数程序设计语言来说，一般都不能满足LR(0)文法的条件。

例如：

不难看出在状态$I_2$中既存在规约项目，又存在移进项目，因而这个文法不是LR(0)文法。

为了对语言句子进行确定性的分析，需要解决冲突。可以采用对含有冲突的项目集向前查看一个输入符号的办法来解决冲突，这种分析法称为简单的LR分析法，即SLR(1)分析法。

分析构造LR(0)分析表的方法，易看出是分析表出现多重定义的原因在于其中的规则2。即对于每一个项目集$I_k$中的规约项目$A\to \alpha \cdot$，不管当前输入符号是什么，都将ACTION表中第k行的各个元素均置为$r_j$。

因此当一个LR(0)项目集闺范族中存在一个含有冲突的项目集，例如：

I k = { X → δ ⋅ b B ， A → α ⋅ ， B → r ⋅ } I_k = \{X \rightarrow{\delta·bB，A\rightarrow{\alpha·}，B\rightarrow{r·}}\} Ik​={X→δ⋅bB，A→α⋅，B→r⋅}
当遇到符号b时，必然会出现多重定义元素。

如要解决则需要向前查看一个输入符号以考察当前所处环境。对规约项目$A\to \alpha \cdot$和$B\to r\cdot$,只需要考察当讲句柄$\alpha$或r规约为A或B时，直接跟在A或B后面的终结符集合即FOLLOW(A)和FOLLOW(B)互不相交且不包含移进符号b，即满足：
$$FOLLOW(A)\cap FOLLOW(B)=\varnothing$$

F O L L O W ( A ) ∩ { b } = ∅ FOLLOW(A) \cap \{b\} = \varnothing FOLLOW(A)∩{b}=∅

F O L L O W ( B ) ∩ { b } = ∅ FOLLOW(B) \cap \{b\} = \varnothing FOLLOW(B)∩{b}=∅

那么，当状态k面临输入符号a是，可按下列规则解决冲突：

1. 若a=b则移进
2. 若$a\in FOLLOW(A)$，则用规则$A\to \alpha$进行规约
3. 若$a\in FOLLOW(B)$，则用规则$B\to r$进行规约
4. 此外都报错

---

SLR分析法的基本思想

这种用来解决分析动作冲突的方法称为SLR(1)方法。如果对于一个文法的某些LR(0)项目集或LR(0)分析表中所含有的动作冲突都能用SLR(1)方法解决，则称这个文法是SLR(1)文法。

SLR(1)分析表的构造

SLR(1)分析表的构造与LR(0)分析表的构造基本相同。（LR(0)分析表的构造方法在这里）

仅对LR(0)分析表构造方法的第二步进行如下修改：

若规约项目$A\to \alpha \cdot$属于$I_k$，则对任何终结符$\alpha \in FOLLOW(A)$置$ACTION[k,a]=r_j$，其中$A\to \alpha$为文法的第j条的规则。