SLR(1)分析法

阳光穿透心脏的1/2处 2022-01-27 09:34 455阅读 0赞

### 文章目录 ###

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

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

例如：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

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

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

分析构造LR(0)分析表的方法，易看出是分析表出现多重定义的原因在于其中的**规则2**。即对于每一个项目集 I k I\_k Ik中的规约项目 A → α ⋅ A\\rightarrow\{\\alpha·\} A→α⋅，不管当前输入符号是什么，都将`ACTION`表中第k行的各个元素均置为 r j r\_j rj。

因此当一个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 → α ⋅ A \\rightarrow\{\\alpha·\} A→α⋅和 B → r ⋅ B\\rightarrow\{r·\} B→r⋅,只需要考察当讲句柄 α \\alpha α或`r`规约为`A`或`B`时，直接跟在`A`或`B`后面的终结符集合即`FOLLOW(A)`和`FOLLOW(B)`互不相交且不包含**移进符号b**，即满足：  
 F O L L O W ( A ) ∩ F O L L O W ( B ) = ∅ FOLLOW(A) \\cap FOLLOW(B) = \\varnothing FOLLOW(A)∩FOLLOW(B)=∅

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 ∈ F O L L O W ( A ) a\\in FOLLOW(A) a∈FOLLOW(A)，则用规则 A → α A \\rightarrow\{\\alpha\} A→α进行规约
3.  若 a ∈ F O L L O W ( B ) a\\in FOLLOW(B) a∈FOLLOW(B)，则用规则 B → r B \\rightarrow\{r\} B→r进行规约
4.  此外都报错

--------------------

# SLR分析法的基本思想 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

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

# SLR(1)分析表的构造 #

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

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

若规约项目 A → α ⋅ A\\rightarrow\{\\alpha·\} A→α⋅属于 I k I\_k Ik，则对任何终结符 α ∈ F O L L O W ( A ) \\alpha \\in FOLLOW(A) α∈FOLLOW(A)置 A C T I O N \[ k , a \] = r j ACTION\[k,a\] = r\_j ACTION\[k,a\]=rj，其中 A → α A\\rightarrow\{\\alpha\} A→α为文法的第j条的规则。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20220127/37b2ed3160a94738b3bab477e02c45bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20220127/a58491d2eda74809ac8c9813cff0c6b7.png
[Link 1]: https://blog.csdn.net/hjc256/article/details/90572695