SLR (1) 分析

SLR (1) 指的是简单的 LR 分析。 它与 LR(0) 分析相同。 唯一的区别在于分析表。要构造 SLR (1) 分析表，我们使用 LR (0) 项的规范集合。

在 SLR (1) 分析中，我们仅将归约动作放置在左侧的 follow 集中。

SLR (1) 分析中涉及的各种步骤

• 对于给定的输入字符串，编写一个上下文无关文法
• 检查文法的歧义性
• 在给定的文法中添加增广产生式
• 创建 LR (0) 项的规范集合
• 绘制数据流图 (DFA)
• 构造一个 SLR (1) 分析表

SLR (1) 表构造

以下是构造 SLR (1) 表的步骤

如果状态 (I_i) 在终结符上进入某个其他状态 (I_j)，则它对应于动作部分中的移入动作。

如果状态 (I_i) 在变量上进入某个其他状态 (I_j)，则它对应于 Go to 部分中的 go to 动作。

如果状态 (I_i) 包含最终项，例如 A → ab•，它没有到下一个状态的转换，那么该产生式被称为归约产生式。 对于 FOLLOW (A) 中的所有终结符 X，写入包含其产生式编号的归约条目。

示例

SLR ( 1 ) 文法

S → E
E → E + T | T
T → T * F | F
F → id

添加增广产生式，并在 G 中每个产生式的第一个位置插入 '•' 符号

S` → •E
E → •E + T
E → •T
T → •T * F
T → •F
F → •id

I0 状态

将增广产生式添加到 I0 状态并计算闭包

I0 = Closure (S` → •E)

将所有以 E 开头的产生式添加到 I0 状态，因为 "." 后面跟着非终结符。 因此，I0 状态变为

I0 = S` → •E
        E → •E + T
        E → •T

将所有以 T 和 F 开头的产生式添加到修改后的 I0 状态，因为 "." 后面跟着非终结符。 因此，I0 状态变为。

I0= S` → •E
       E → •E + T
       E → •T
       T → •T * F
       T → •F
       F → •id

I1= Go to (I0, E) = closure (S` → E•, E → E• + T)
I2= Go to (I0, T) = closure (E → T•T, T• → * F)
I3= Go to (I0, F) = Closure ( T → F• ) = T → F•
I4= Go to (I0, id) = closure ( F → id•) = F → id•
I5= Go to (I1, +) = Closure (E → E +•T)

将所有以 T 和 F 开头的产生式添加到 I5 状态，因为 "." 后面跟着非终结符。 因此，I5 状态变为

I5 = E → E +•T
       T → •T * F
       T → •F
       F → •id

Go to (I5, F) = Closure (T → F•) = (与 I3 相同)
Go to (I5, id) = Closure (F → id•) = (与 I4 相同)

I6= Go to (I2, *) = Closure (T → T * •F)

将所有以 F 开头的产生式添加到 I6 状态，因为 "." 后面跟着非终结符。 因此，I6 状态变为

I6 = T → T * •F
         F → •id

Go to (I6, id) = Closure (F → id•) = (与 I4 相同)

I7= Go to (I5, T) = Closure (E → E + T•) = E → E + T•
I8= Go to (I6, F) = Closure (T → T * F•) = T → T * F•

绘制 DFA

SLR (1) 表

说明

First (E) = First (E + T) ∪ First (T)
First (T) = First (T * F) ∪ First (F)
First (F) = {id}
First (T) = {id}
First (E) = {id}
Follow (E) = First (+T) ∪ {$} = {+, $}
Follow (T) = First (*F) ∪ First (F)
               = {*, +, $}
Follow (F) = {*, +, $}

• I1 包含驱动 S → E• 的最终项，并且 follow (S) = {$}, 因此动作 {I1, $} = 接受
• I2 包含驱动 E → T• 的最终项，并且 follow (E) = {+, $}, 因此动作 {I2, +} = R2, 动作 {I2, $} = R2
• I3 包含驱动 T → F• 的最终项，并且 follow (T) = {+, *, $}, 因此动作 {I3, +} = R4, 动作 {I3, *} = R4, 动作 {I3, $} = R4
• I4 包含驱动 F → id• 的最终项，并且 follow (F) = {+, *, $}, 因此动作 {I4, +} = R5, 动作 {I4, *} = R5, 动作 {I4, $} = R5
• I7 包含驱动 E → E + T• 的最终项，并且 follow (E) = {+, $}, 因此动作 {I7, +} = R1, 动作 {I7, $} = R1
• I8 包含驱动 T → T * F• 的最终项，并且 follow (T) = {+, *, $}, 因此动作 {I8, +} = R3, 动作 {I8, *} = R3, 动作 {I8, $} = R3.

SLR(1) 分析的优点

• 它非常易于使用且高效。

关于 SLR(1) 分析表经常被问到的问题

1. 列出 SLR(1) 分析表的应用？

答案：以下是 SLR(1) 分析表的各种应用列表

• Compiler
• 数据验证
• 自然语言处理

2. SLR 解析器的缺点是什么？

答案： SLR 解析器的主要缺点是它只能处理属于 SLR(1) 类别的文法。

3. 列出构造 SLR 分析表的步骤？

答案

• 在设计分析表的第一步中，编写增广文法。
• 在收集 LR(1) 项之后查找项。
• 找到 LHS 产生式的 follow 集。
• 在设计分析表的最后一步中，定义 2 个函数
  • goto(): 它包含终端的集合。
  • action(): 它包含非终端的集合。

4. SLR 和 LR 分析表之间的主要区别是什么？

答案： SLR(1) 类似于 LR(0) 分析，因为它只需要规范项来构造分析表，但它们之间的主要区别是移入-归约冲突的可能性。 这可以通过将“归约”存储在终结符状态中来解决，该状态对应于产生式 LHS 的 FOLLOW 集。 此项目集合称为 SLR(1) 分析，用于创建包含提供给文法的表，以表示每个状态的闭包和 goto 操作。