第83集：SLR(1)分析法

学习目标

  • 理解SLR(1)分析的基本概念和原理
  • 掌握FOLLOW集的计算方法
  • 学习SLR(1)分析表的构造方法
  • 理解SLR(1)分析如何解决LR(0)分析的冲突
  • 掌握SLR(1)分析的过程和步骤
  • 比较SLR(1)分析与LR(0)分析的优缺点
  • 通过示例练习SLR(1)分析的各个步骤

一、SLR(1)分析的基本概念

1. SLR(1)分析的定义

SLR(1)（Simple LR(1)）分析是对LR(0)分析的一种改进，它通过使用FOLLOW集（后续符号集）来解决LR(0)分析中的移进-归约冲突。SLR(1)分析的基本思想是：

  • 对于归约项 A → α.，只在输入符号属于FOLLOW(A)时才进行归约
  • 这样可以减少归约操作的次数，从而解决部分移进-归约冲突

SLR(1)分析的名称中：

  • S 表示简单（Simple）
  • L 表示从左到右扫描输入串
  • R 表示构造最右推导的逆过程（最左归约）
  • 1 表示使用一个展望符（lookahead）来决定归约操作

2. SLR(1)分析与LR(0)分析的区别

SLR(1)分析与LR(0)分析的主要区别在于分析表的构造规则：

  • LR(0)分析：对于归约项 A → α.，对所有终结符a（包括$）都进行归约
  • SLR(1)分析：对于归约项 A → α.，只对属于FOLLOW(A)的终结符a进行归约

这种区别使得SLR(1)分析能够解决部分LR(0)分析中的移进-归约冲突，从而扩大了适用范围。

3. SLR(1)分析的局限性

虽然SLR(1)分析比LR(0)分析具有更强的能力，但它仍然有局限性：

  • SLR(1)分析只使用FOLLOW集来决定归约操作，而FOLLOW集是基于整个文法计算的，可能包含一些在当前上下文中不可能出现的符号
  • 这可能导致在某些情况下，SLR(1)分析仍然无法解决移进-归约冲突
  • 对于归约-归约冲突，SLR(1)分析通常也无法解决

二、FOLLOW集的计算

1. FOLLOW集的定义

FOLLOW集是针对文法非终结符的一个集合，表示该非终结符后面可能跟随的终结符集合。形式上，对于非终结符A，FOLLOW(A)是所有终结符a的集合，使得存在推导：

S ⇒* αAβ

其中β以a开头（β可以是空串，此时a是$）。

2. FOLLOW集的计算规则

计算FOLLOW集的规则如下：

  1. 开始符号的FOLLOW集：将$添加到FOLLOW(S)中，其中S是文法的开始符号
  2. 对于产生式A → αBβ：将FIRST(β)中除ε以外的所有符号添加到FOLLOW(B)中
  3. **对于产生式A → αB或A → αBβ且ε∈FIRST(β)**：将FOLLOW(A)中的所有符号添加到FOLLOW(B)中

3. FOLLOW集的计算算法

计算FOLLOW集的算法如下：

  1. 初始化：对于文法的开始符号S，设置FOLLOW(S) = {$}
  2. 重复应用以下规则，直到所有FOLLOW集不再变化：
    • 对于每个产生式A → αBβ：
      • 计算FIRST(β)，将其中非ε的符号添加到FOLLOW(B)中
      • 如果ε∈FIRST(β)，则将FOLLOW(A)中的符号添加到FOLLOW(B)中
    • 对于每个产生式A → αB：
      • 将FOLLOW(A)中的符号添加到FOLLOW(B)中

4. FIRST集的回顾

在计算FOLLOW集时，需要用到FIRST集（首符号集）。FIRST集的定义和计算规则如下：

  • FIRST集的定义：对于符号串α，FIRST(α)是α推导出的所有可能的首终结符的集合
  • FIRST集的计算规则：
    1. 对于终结符a，FIRST(a) = {a}
    2. 对于非终结符A，FIRST(A)是所有产生式A→α的FIRST(α)的并集
    3. 对于符号串α = X₁X₂...Xₙ：
      • 将FIRST(X₁)中除ε以外的符号添加到FIRST(α)中
      • 如果ε∈FIRST(X₁)，则将FIRST(X₂)中除ε以外的符号添加到FIRST(α)中
      • 以此类推，直到某个Xᵢ的FIRST集不包含ε，或者所有Xᵢ的FIRST集都包含ε

三、SLR(1)分析表的构造

1. SLR(1)分析表的构造步骤

SLR(1)分析表的构造步骤如下：

  1. 扩展文法：添加新的开始符号S'和产生式S'→S
  2. 构造LR(0)项集规范族：使用闭包和转移操作构造所有可能的LR(0)项集
  3. 计算FOLLOW集：为每个非终结符计算FOLLOW集
  4. 构造分析表：
    • 移进表（Action表）构造：
      • 对于状态i中的每个移进项 A → α.aβ，如果Goto(i, a) = j，则Action[i][a] = shift j
      • 对于状态i中的每个归约项 A → α.，对于每个终结符a∈FOLLOW(A)，Action[i][a] = reduce A→α
      • 对于接受项 S' → S.，Action[i][$] = accept
    • goto表构造：
      • 对于每个状态i和非终结符A，如果Goto(i, A) = j，则Goto[i][A] = j

2. SLR(1)分析表的冲突

SLR(1)分析通过使用FOLLOW集来解决部分移进-归约冲突，但仍然可能存在冲突：

  • 移进-归约冲突：当状态i中存在移进项 A → α.aβ 和归约项 B → γ.，且a∈FOLLOW(B)时，会产生移进-归约冲突
  • 归约-归约冲突：当状态i中存在多个归约项 A → α. 和 B → β.，且FOLLOW(A)和FOLLOW(B)有交集时，会产生归约-归约冲突

3. SLR(1)分析的适用条件

一个文法是SLR(1)文法，当且仅当构造的SLR(1)分析表中不存在冲突。SLR(1)文法比LR(0)文法具有更广泛的适用范围，但仍然无法处理所有上下文无关文法。

四、SLR(1)分析的过程

1. SLR(1)分析的基本步骤

SLR(1)分析的过程与LR(0)分析的过程类似，具体步骤如下：

  1. 初始化：

    • 分析栈中压入初始状态0和结束符$
    • 输入指针指向输入串的第一个符号

  2. 分析循环：
    重复以下步骤，直到分析完成：

    • 获取当前状态：栈顶的状态为当前状态s
    • 获取当前输入符号：输入指针指向的符号为当前输入符号a
    • 查找分析表：查找Action[s][a]的值
    • 执行操作：
      • 移进（shift j）：将输入符号a和状态j压入栈，输入指针向前移动一位
      • 归约（reduce A→α）：
        • 从栈中弹出2*|α|个元素（|α|是产生式右部的长度，每个符号对应一个状态）
        • 此时栈顶的状态为t
        • 查找Goto[t][A] = k，将非终结符A和状态k压入栈
        • 输出归约信息
      • 接受（accept）：分析成功，结束分析
      • 错误（error）：分析失败，报告错误

2. SLR(1)分析的示例

示例：算术表达式的SLR(1)分析

考虑以下算术表达式文法：

E → E + T | T
T → T * F | F
F → ( E ) | id

扩展后的文法为：

S' → E
E → E + T | T
T → T * F | F
F → ( E ) | id

1. 构造LR(0)项集规范族

按照LR(0)分析的方法，构造LR(0)项集规范族，得到项集I0到I12（与第82集相同）。

2. 计算FOLLOW集

计算各个非终结符的FOLLOW集：

  • **FOLLOW(S')**：根据规则1，FOLLOW(S') = {$}
  • **FOLLOW(E)**：
    • 从产生式S'→E：将FOLLOW(S')添加到FOLLOW(E)，所以FOLLOW(E) = {$}
    • 从产生式E→E+T：β=+T，FIRST(+T)={+}，所以添加+到FOLLOW(E)
    • 从产生式F→(E)：β=)，FIRST())={)}，所以添加)到FOLLOW(E)
    • 最终FOLLOW(E) = {$+,)}
  • **FOLLOW(T)**：
    • 从产生式E→E+T：β=ε（因为E→E+T的右部是E+T，当考虑T时，β是空串），所以将FOLLOW(E)添加到FOLLOW(T)
    • 从产生式T→T*F：β=F，FIRST(F)={}，所以添加到FOLLOW(T)
    • 最终FOLLOW(T) = {$+,),*}
  • **FOLLOW(F)**：
    • 从产生式T→TF：β=ε（因为T→TF的右部是T*F，当考虑F时，β是空串），所以将FOLLOW(T)添加到FOLLOW(F)
    • 最终FOLLOW(F) = {$+,),*}

3. 构造SLR(1)分析表

根据LR(0)项集规范族和FOLLOW集，构造SLR(1)分析表：

状态 Action Goto
id + * ( ) $ E T F
0 s6 s5 1 2 3
1 s7 acc
2 s7 r2 r2
3 r4 s8 r4 r4
4 r6 r6 r6 r6
5 s6 s5 9 2 3
6 r7 r7 r7 r7
7 s6 s5 10 3
8 s6 s5 11
9 s7 s12
10 r3 s8 r3 r3
11 r5 r5 r5 r5
12 r1 r1 r1 r1

其中：

  • s6表示移进到状态6
  • r2表示用产生式2（E→T）进行归约
  • acc表示接受
  • 空格表示错误

4. 分析输入串 id + id * id

分析过程如下：

步骤 分析栈 剩余输入 Action Goto 说明
1 0 id + id * id $ s6 移进id，进入状态6
2 0 id 6 + id * id $ r7 3 用F→id归约，Goto(0,F)=3
3 0 F 3 + id * id $ r4 2 用T→F归约，Goto(0,T)=2
4 0 T 2 + id * id $ r2 1 用E→T归约，Goto(0,E)=1
5 0 E 1 + id * id $ s7 移进+，进入状态7
6 0 E 1 + 7 id * id $ s6 移进id，进入状态6
7 0 E 1 + 7 id 6 * id $ r7 3 用F→id归约，Goto(7,F)=3
8 0 E 1 + 7 F 3 * id $ r4 10 用T→F归约，Goto(7,T)=10
9 0 E 1 + 7 T 10 * id $ s8 移进*，进入状态8
10 0 E 1 + 7 T 10 * 8 id $ s6 移进id，进入状态6
11 0 E 1 + 7 T 10 * 8 id 6 $ r7 11 用F→id归约，Goto(8,F)=11
12 0 E 1 + 7 T 10 * 8 F 11 $ r5 10 用T→T*F归约，Goto(7,T)=10
13 0 E 1 + 7 T 10 $ r3 1 用E→E+T归约，Goto(0,E)=1
14 0 E 1 $ acc 接受

五、SLR(1)分析与LR(0)分析的比较

1. 能力比较

  • SLR(1)分析的能力更强：SLR(1)分析通过使用FOLLOW集来解决部分LR(0)分析中的移进-归约冲突，因此能够处理更多的文法
  • LR(0)分析的局限性：LR(0)分析不考虑展望符，容易产生移进-归约冲突，只能处理部分简单的文法

2. 实现复杂度比较

  • SLR(1)分析的实现：比LR(0)分析复杂，需要计算FOLLOW集
  • LR(0)分析的实现：相对简单，不需要计算FOLLOW集

3. 分析表大小比较

  • SLR(1)分析表：与LR(0)分析表大小相同，因为它们使用相同的项集规范族
  • LR(0)分析表：与SLR(1)分析表大小相同

4. 错误处理比较

  • SLR(1)分析的错误处理：与LR(0)分析类似，错误检测能力相当
  • LR(0)分析的错误处理：与SLR(1)分析类似

六、SLR(1)分析的局限性

1. SLR(1)分析的冲突问题

虽然SLR(1)分析比LR(0)分析具有更强的能力，但它仍然存在局限性：

  • 移进-归约冲突：当状态i中存在移进项 A → α.aβ 和归约项 B → γ.，且a∈FOLLOW(B)时，会产生移进-归约冲突
  • 归约-归约冲突：当状态i中存在多个归约项 A → α. 和 B → β.，且FOLLOW(A)和FOLLOW(B)有交集时，会产生归约-归约冲突

2. SLR(1)分析的理论局限性

SLR(1)分析的理论局限性主要在于它使用的是全局的FOLLOW集，而不是上下文相关的展望符：

  • FOLLOW集的全局性：FOLLOW集是基于整个文法计算的，包含了所有可能的后续符号，而不仅仅是当前上下文中可能出现的符号
  • 上下文无关性：SLR(1)分析不考虑当前的分析上下文，可能会在某些情况下做出错误的归约决策

3. SLR(1)分析的改进方向

为了克服SLR(1)分析的局限性，后续发展了更高级的LR分析方法：

  • LR(1)分析：通过在项中添加上下文相关的展望符，解决SLR(1)分析的冲突
  • LALR(1)分析：通过合并LR(1)项集中的同心项集，减少分析表的大小，同时保持LR(1)分析的能力

七、SLR(1)分析的实践练习

练习：构造SLR(1)分析表

考虑以下简单文法：

S → A
A → aAb | ε
  1. 扩展文法，添加新的开始符号S'
  2. 构造LR(0)项集规范族
  3. 计算FOLLOW集
  4. 构造SLR(1)分析表
  5. 分析输入串 aabb 的过程

解决方案：

  1. 扩展文法：

    S' → S
S → A
A → aAb | ε

  2. 构造LR(0)项集规范族：

    • I0: S'→.S, S→.A, A→.aAb, A→.ε
    • I1: S'→S.
    • I2: S→A.
    • I3: A→a.Ab, A→.aAb, A→.ε
    • I4: A→aA.b
    • I5: A→aAb.

  3. 计算FOLLOW集：

    • FOLLOW(S') = {$}
    • FOLLOW(S) = {$}
    • FOLLOW(A):
      • 从S→A：将FOLLOW(S)添加到FOLLOW(A)，所以FOLLOW(A) = {$}
      • 从A→aAb：β=b，FIRST(b)={b}，所以添加b到FOLLOW(A)
      • 最终FOLLOW(A) = {$b}

  4. 构造SLR(1)分析表：

    状态 Action Goto
    a b $ S A
    0 s3 r3 r3 1 2
    1 acc
    2 r2
    3 s3 r3 r3 4
    4 s5
    5 r1 r1

  5. **分析输入串 aabb**：

    步骤 分析栈 剩余输入 Action Goto 说明
    1 0 aabb $ s3 移进a，进入状态3
    2 0 a 3 abb $ s3 移进a，进入状态3
    3 0 a 3 a 3 bb $ s4 移进b，进入状态4
    4 0 a 3 a 3 b 4 b $ s5 移进b，进入状态5
    5 0 a 3 a 3 b 4 b 5 $ r1 4 用A→aAb归约，Goto(3,A)=4
    6 0 a 3 A 4 $ r1 2 用A→aAb归约，Goto(0,A)=2
    7 0 A 2 $ r2 1 用S→A归约，Goto(0,S)=1
    8 0 S 1 $ acc 接受

八、SLR(1)分析的示例：处理移进-归约冲突

示例：文法的SLR(1)分析

考虑以下文法：

S → L = R | R
L → * R | id
R → L

  1. 扩展文法：

    S' → S
S → L = R | R
L → * R | id
R → L

  2. 构造LR(0)项集规范族：

    • I0: S'→.S, S→.L=R, S→.R, L→.*R, L→.id, R→.L
    • I1: S'→S.
    • I2: S→L.=R
    • I3: S→R., L→* .R, R→.L, L→.*R, L→.id
    • I4: L→id.
    • I5: S→L= .R, R→.L, L→.*R, L→.id
    • I6: L→*R., R→L.
    • I7: R→L.
    • I8: S→L=R.

  3. 计算FOLLOW集：

    • FOLLOW(S') = {$}
    • FOLLOW(S) = {$}
    • FOLLOW(L):
      • 从S→L=R：β==R，FIRST(=R)={=}，所以添加=到FOLLOW(L)
      • 从R→L：将FOLLOW(R)添加到FOLLOW(L)
      • 从S→R：将FOLLOW(S)添加到FOLLOW(R)，所以FOLLOW(R)={$}
      • 从R→L：将FOLLOW(R)添加到FOLLOW(L)，所以添加$到FOLLOW(L)
      • 最终FOLLOW(L) = {=$}
    • FOLLOW(R):
      • 从S→L=R：将FOLLOW(S)添加到FOLLOW(R)，所以FOLLOW(R)={$}
      • 从L→R：β=ε（因为L→R的右部是*R，当考虑R时，β是空串），所以将FOLLOW(L)添加到FOLLOW(R)，所以FOLLOW(R)={$=}

  4. 构造SLR(1)分析表：

    状态 Action Goto
    id * = $ S L R
    0 s4 s3 1 2 3
    1 acc
    2 s5
    3 s4 s3 r3 r3 7 6
    4 r4 r4 r4 r4
    5 s4 s3 7 8
    6 r1 r1
    7 r5 r5
    8 r2

  5. **分析输入串 *id=id**：

    步骤 分析栈 剩余输入 Action Goto 说明
    1 0 *id=id $ s3 移进*，进入状态3
    2 0 * 3 id=id $ s4 移进id，进入状态4
    3 0 * 3 id 4 =id $ r4 7 用L→id归约，Goto(3,L)=7
    4 0 * 3 L 7 =id $ r5 6 用R→L归约，Goto(3,R)=6
    5 0 * 3 R 6 =id $ r1 2 用L→*R归约，Goto(0,L)=2
    6 0 L 2 =id $ s5 移进=，进入状态5
    7 0 L 2 = 5 id $ s4 移进id，进入状态4
    8 0 L 2 = 5 id 4 $ r4 7 用L→id归约，Goto(5,L)=7
    9 0 L 2 = 5 L 7 $ r5 8 用R→L归约，Goto(5,R)=8
    10 0 L 2 = 5 R 8 $ r2 1 用S→L=R归约，Goto(0,S)=1
    11 0 S 1 $ acc 接受

九、自测问题

  1. 选择题：SLR(1)分析是对LR(0)分析的改进，它通过使用什么来解决移进-归约冲突？
    A. FIRST集
    B. FOLLOW集
    C. SELECT集
    D. CLOSURE集

  2. 选择题：计算FOLLOW集时，对于产生式A→αBβ，以下说法正确的是：
    A. 将FIRST(β)中的所有符号添加到FOLLOW(B)中
    B. 将FIRST(β)中除ε以外的所有符号添加到FOLLOW(B)中
    C. 将FOLLOW(A)中的所有符号添加到FOLLOW(B)中
    D. 将β中的所有符号添加到FOLLOW(B)中

  3. 简答题：简述SLR(1)分析表的构造规则。

  4. 简答题：解释SLR(1)分析如何解决LR(0)分析的移进-归约冲突。

  5. 实践题：对于文法 S→A | B, A→aA | ε, B→bB | ε，构造SLR(1)分析表，并分析输入串 aab 的过程。

十、小结

本集详细介绍了SLR(1)分析方法，包括：

  1. SLR(1)分析的基本概念：对LR(0)分析的改进，通过使用FOLLOW集解决移进-归约冲突
  2. FOLLOW集的计算：根据文法规则计算每个非终结符的后续符号集
  3. SLR(1)分析表的构造：结合LR(0)项集规范族和FOLLOW集构造分析表
  4. SLR(1)分析的过程：利用分析表指导移进和归约操作
  5. SLR(1)分析的局限性：仍然可能存在移进-归约冲突和归约-归约冲突
  6. SLR(1)分析与LR(0)分析的比较：SLR(1)分析具有更强的能力，但实现更复杂
  7. SLR(1)分析的改进方向：LR(1)分析和LALR(1)分析

SLR(1)分析是LR分析家族中的重要成员，它通过引入FOLLOW集来解决LR(0)分析的部分冲突，扩大了LR分析的适用范围。虽然SLR(1)分析仍然存在局限性，但它为后续更高级的LR分析方法（如LR(1)和LALR(1)）奠定了基础。

十一、下集预告

下一集我们将学习LR(1)分析方法，它通过在项中添加上下文相关的展望符，解决SLR(1)分析的冲突，具有更强的分析能力。LR(1)分析是理解LALR(1)分析的基础，而LALR(1)分析是实际编译器中最常用的LR分析方法之一。

参考资料

  1. 《编译原理》（龙书）- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
  2. 《现代编译原理》（虎书）- Andrew W. Appel
  3. 《编译器设计》- Keith D. Cooper, Linda Torczon
  4. SLR(1)分析算法的历史与发展
  5. Yacc/Bison用户手册

通过本集的学习，你应该对SLR(1)分析方法有了全面的了解。SLR(1)分析通过使用FOLLOW集来解决LR(0)分析的部分冲突，是LR分析家族中的重要成员。在后续的学习中，我们将继续深入探讨更高级的LR分析方法，如LR(1)和LALR(1)分析，这些方法在实际编译器中得到了广泛的应用。

« 上一篇 LR(0)分析法 下一篇 » LR(1)分析法
↑