第56集：LR(0)和SLR(1)分析器

学习目标

  • 掌握LR(0)分析器的项集构建方法
  • 理解LR(0)分析表的生成过程
  • 掌握SLR(1)分析器的工作原理
  • 学会处理移进-归约冲突
  • 能够手动构建LR(0)和SLR(1)分析表

1. LR(0)分析器详解

1.1 LR(0)项

LR(0)项是一个产生式加上一个点，表示分析过程中的一个状态。点的位置指示了当前的分析进度。例如：

  • A → ·α：表示等待分析 α
  • A → α·β：表示 α 已经分析完成，等待分析 β
  • A → α·：表示 α 已经分析完成，可以归约

1.2 扩展文法

为了处理开始符号，通常需要将文法扩展，添加一个新的开始符号 S'，并添加产生式 S' → S，其中 S 是原文法的开始符号。这样可以确保分析过程有一个明确的结束点。

1.3 闭包运算

闭包运算是构建LR(0)项集的核心操作，它的作用是：对于项集中的每个项 A → α·Bβ，将所有 B → ·γ 形式的项添加到项集中，重复这个过程直到项集不再变化。

算法：

function CLOSURE(I) {
    J = I
    repeat {
        for each item A → α·Bβ in J {
            for each production B → γ in G {
                if item B → ·γ not in J {
                    add B → ·γ to J
                }
            }
        }
    } until J doesn't change
    return J
}

1.4 GOTO运算

GOTO运算是从一个项集转移到另一个项集的操作，它的定义是：

GOTO(I, X) = CLOSURE({ A → αX·β | A → α·Xβ ∈ I })

其中，I 是一个项集，X 是一个文法符号，CLOSURE 是闭包运算。

1.5 项集规范族的构建

项集规范族是由所有可能的LR(0)项集组成的集合，构建算法如下：

function ITEM_SETS(G') {
    C = { CLOSURE({ S' → ·S }) }
    repeat {
        for each item set I in C {
            for each grammar symbol X {
                if GOTO(I, X) is not empty and not in C {
                    add GOTO(I, X) to C
                }
            }
        }
    } until C doesn't change
    return C
}

1.6 示例：构建LR(0)项集规范族

考虑以下简单表达式文法：

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

扩展文法：

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

构建过程：

  1. 初始项集 I0：

    I0 = CLOSURE({ S' → ·E })

    应用闭包运算：

    I0:
S' → ·E
E → ·E + T
E → ·T
T → ·T * F
T → ·F
F → ·( E )
F → ·id

  2. **计算 GOTO(I0, E)**：

    GOTO(I0, E) = CLOSURE({ S' → E·, E → E· + T })

    应用闭包运算：

    I1:
S' → E·
E → E· + T

  3. **计算 GOTO(I0, T)**：

    GOTO(I0, T) = CLOSURE({ E → T·, T → T· * F })

    应用闭包运算：

    I2:
E → T·
T → T· * F

  4. **计算 GOTO(I0, F)**：

    GOTO(I0, F) = CLOSURE({ T → F· })

    应用闭包运算：

    I3:
T → F·

  5. **计算 GOTO(I0, ()**：

    GOTO(I0, () = CLOSURE({ F → (· E ) })

    应用闭包运算：

    I4:
F → (· E )
E → ·E + T
E → ·T
T → ·T * F
T → ·F
F → ·( E )
F → ·id

  6. **计算 GOTO(I0, id)**：

    GOTO(I0, id) = CLOSURE({ F → id· })

    应用闭包运算：

    I5:
F → id·

  7. 继续计算其他GOTO值，直到所有可能的项集都被构建完成。

1.7 LR(0)分析表的生成

LR(0)分析表由ACTION表和GOTO表组成。

ACTION表生成规则：

  • 对于项集 I 中的每个项 A → α·aβ，如果 GOTO(I, a) = J，则 ACTION[I, a] = sJ（移进）
  • 对于项集 I 中的每个项 A → α·，如果 A 不是开始符号，则对于所有输入符号 a，ACTION[I, a] = rk（归约，k是产生式编号）
  • 对于项集 I 中的项 S' → S·，则 ACTION[I, $] = accept（接受）

GOTO表生成规则：

  • 对于每个项集 I 和非终结符 A，如果 GOTO(I, A) = J，则 GOTO[I, A] = J

1.8 LR(0)分析器的局限性

LR(0)分析器的主要局限性是它无法处理移进-归约冲突。例如，在项集 I1 中：

I1:
S' → E·
E → E· + T

当输入符号是 + 时，既可以移进（根据 E → E· + T），又可以归约（根据 S' → E·），这就产生了移进-归约冲突。

2. SLR(1)分析器详解

2.1 基本思想

SLR(1)分析器是对LR(0)分析器的改进，它的基本思想是：在处理归约操作时，使用FOLLOW集来限制归约的条件，只有当当前输入符号在归约产生式左部非终结符的FOLLOW集中时，才进行归约操作。

2.2 FOLLOW集的计算

对于非终结符 A，FOLLOW(A) 是所有可能出现在 A 之后的终结符的集合。计算方法如下：

  1. 对于开始符号 S，将 $ 加入 FOLLOW(S)
  2. 对于产生式 A → αBβ：
    • 将 FIRST(β) 中除 ε 以外的符号加入 FOLLOW(B)
    • 如果 ε ∈ FIRST(β)，则将 FOLLOW(A) 加入 FOLLOW(B)

2.3 SLR(1)分析表的生成

SLR(1)分析表的生成与LR(0)类似，但在处理归约操作时使用FOLLOW集：

ACTION表生成规则：

  • 对于项集 I 中的每个项 A → α·aβ，如果 GOTO(I, a) = J，则 ACTION[I, a] = sJ（移进）
  • 对于项集 I 中的每个项 A → α·，如果 A 不是开始符号，则对于所有 a ∈ FOLLOW(A)，ACTION[I, a] = rk（归约，k是产生式编号）
  • 对于项集 I 中的项 S' → S·，则 ACTION[I, $] = accept（接受）

GOTO表生成规则：

  • 对于每个项集 I 和非终结符 A，如果 GOTO(I, A) = J，则 GOTO[I, A] = J

2.4 示例：构建SLR(1)分析表

考虑之前的表达式文法：

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

计算FOLLOW集：

  • FOLLOW(S') = { $ }
  • FOLLOW(E) = { +, ), $ }
  • FOLLOW(T) = { +, *, ), $ }
  • FOLLOW(F) = { +, *, ), $ }

构建SLR(1)分析表：

状态 ACTION GOTO
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 (E→T) s7 r2 (E→T) r2 (E→T)
3 r4 (T→F) r4 (T→F) r4 (T→F) r4 (T→F)
4 s5 s4 8 2 3
5 r6 (F→id) r6 (F→id) r6 (F→id) r6 (F→id)
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r3 (E→E+T) s7 r3 (E→E+T) r3 (E→E+T)
10 r5 (T→T*F) r5 (T→T*F) r5 (T→T*F) r5 (T→T*F)
11 r1 (F→(E)) r1 (F→(E)) r1 (F→(E)) r1 (F→(E))

2.5 SLR(1)分析器的工作过程

以输入串 id + id * id 为例，SLR(1)分析器的工作过程如下：

步骤：

  1. 初始状态：状态栈 [0]，符号栈 [$]，输入 id + id * id $
  2. ACTION[0, id] = s5（移进），状态栈 [0, 5]，符号栈 [$id]，输入 + id * id $
  3. ACTION[5, +] = r6（归约 F→id），弹出状态 5，状态栈 [0]，GOTO[0, F] = 3，状态栈 [0, 3]，符号栈 [$F]，输入 + id * id $
  4. ACTION[3, +] = r4（归约 T→F），弹出状态 3，状态栈 [0]，GOTO[0, T] = 2，状态栈 [0, 2]，符号栈 [$T]，输入 + id * id $
  5. ACTION[2, +] = r2（归约 E→T），弹出状态 2，状态栈 [0]，GOTO[0, E] = 1，状态栈 [0, 1]，符号栈 [$E]，输入 + id * id $
  6. ACTION[1, +] = s6（移进），状态栈 [0, 1, 6]，符号栈 [$E+]，输入 id * id $
  7. ACTION[6, id] = s5（移进），状态栈 [0, 1, 6, 5]，符号栈 [$E+id]，输入 * id $
  8. ACTION[5, *] = r6（归约 F→id），弹出状态 5，状态栈 [0, 1, 6]，GOTO[6, F] = 3，状态栈 [0, 1, 6, 3]，符号栈 [$E+F]，输入 * id $
  9. ACTION[3, *] = r4（归约 T→F），弹出状态 3，状态栈 [0, 1, 6]，GOTO[6, T] = 9，状态栈 [0, 1, 6, 9]，符号栈 [$E+T]，输入 * id $
  10. ACTION[9, ] = s7（移进），状态栈 [0, 1, 6, 9, 7]，符号栈 [$E+T]，输入 id $
  11. ACTION[7, id] = s5（移进），状态栈 [0, 1, 6, 9, 7, 5]，符号栈 [$E+T*id]，输入 $
  12. ACTION[5, $] = r6（归约 F→id），弹出状态 5，状态栈 [0, 1, 6, 9, 7]，GOTO[7, F] = 10，状态栈 [0, 1, 6, 9, 7, 10]，符号栈 [$E+T*F]，输入 $
  13. ACTION[10, $] = r5（归约 T→T*F），弹出状态 7, 10，状态栈 [0, 1, 6, 9]，GOTO[6, T] = 9，状态栈 [0, 1, 6, 9]，符号栈 [$E+T]，输入 $
  14. ACTION[9, $] = r3（归约 E→E+T），弹出状态 6, 9，状态栈 [0, 1]，GOTO[0, E] = 1，状态栈 [0, 1]，符号栈 [$E]，输入 $
  15. ACTION[1, $] = acc（接受），分析成功

3. 移进-归约冲突的处理

3.1 冲突的产生

移进-归约冲突是指在某个状态下，既可以移进当前输入符号，又可以归约某个产生式。例如：

I1:
S' → E·
E → E· + T

当输入符号是 + 时，既可以移进（根据 E → E· + T），又可以归约（根据 S' → E·）。

3.2 SLR(1)的解决方法

SLR(1)分析器通过检查输入符号是否在归约产生式左部非终结符的FOLLOW集中来解决冲突：

  • 如果输入符号在FOLLOW集中，则选择归约
  • 否则，选择移进

在上面的例子中，FOLLOW(S') = { $ }，而输入符号是 +，不在FOLLOW(S')中，所以选择移进，从而解决了冲突。

3.3 归约-归约冲突

归约-归约冲突是指在某个状态下，可以归约多个不同的产生式。例如：

I:
A → α·
B → β·

当输入符号 a 同时在 FOLLOW(A) 和 FOLLOW(B) 中时，就会产生归约-归约冲突。

3.4 冲突的解决策略

对于无法用SLR(1)解决的冲突，可以考虑以下策略：

  1. 修改文法：重写文法，消除冲突
  2. 使用优先级规则：为产生式或终结符定义优先级
  3. 使用结合性规则：为终结符定义结合性
  4. 升级到LR(1)或LALR(1)分析器：使用更强大的分析方法

4. 实战案例：构建SLR(1)分析器

4.1 文法定义

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

4.2 扩展文法

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

4.3 计算FIRST集和FOLLOW集

FIRST集：

  • FIRST(S) = FIRST(L) = {*, id}
  • FIRST(L) = {*, id}
  • FIRST(R) = FIRST(L) = {*, id}

FOLLOW集：

  • FOLLOW(S') = { $ }
  • FOLLOW(S) = { $ }
  • FOLLOW(L) = {=, $ }
  • FOLLOW(R) = {=, $ }

4.4 构建项集规范族

I0:

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

I1 (GOTO(I0, S)):

S' → S·

I2 (GOTO(I0, L)):

S → L· = R
R → L·

I3 (GOTO(I0, R)):

S → R·

*I4 (GOTO(I0, )):

L → *· R
R → ·L
L → ·* R
L → ·id

I5 (GOTO(I0, id)):

L → id·

I6 (GOTO(I2, =)):

S → L = ·R
R → ·L
L → ·* R
L → ·id

I7 (GOTO(I4, R)):

L → * R·

I8 (GOTO(I6, R)):

S → L = R·

4.5 构建SLR(1)分析表

状态 ACTION GOTO
id * = $ S L R
0 s5 s4 1 2 3
1 acc
2 s6 r3 (R→L)
3 r2 (S→R)
4 s5 s4 2 7
5 r5 (L→id) r5 (L→id)
6 s5 s4 2 8
7 r4 (L→*R) r4 (L→*R)
8 r1 (S→L=R)

4.6 分析示例

输入： * id = id

分析过程：

  1. 0 $ * id = id $
  2. 0 4 $ * id = id $
  3. 0 4 5 $ * id = id $
  4. 0 4 5 r5 $ * L = id $ （归约 L→id）
  5. 0 4 2 $ * L = id $ （GOTO(I4, L)=2）
  6. 0 4 2 r3 $ * R = id $ （归约 R→L）
  7. 0 4 7 $ * R = id $ （GOTO(I4, R)=7）
  8. 0 4 7 r4 $ L = id $ （归约 L→*R）
  9. 0 2 $ L = id $ （GOTO(I0, L)=2）
  10. 0 2 6 $ L = id $ （移进 =）
  11. 0 2 6 5 $ L = id $ （移进 id）
  12. 0 2 6 5 r5 $ L = L $ （归约 L→id）
  13. 0 2 6 2 $ L = L $ （GOTO(I6, L)=2）
  14. 0 2 6 2 r3 $ L = R $ （归约 R→L）
  15. 0 2 6 8 $ L = R $ （GOTO(I6, R)=8）
  16. 0 2 6 8 r1 $ S $ （归约 S→L=R）
  17. 0 1 $ S $ （GOTO(I0, S)=1）
  18. 0 1 $ S $ （接受）

5. 自测题

  1. LR(0)分析器和SLR(1)分析器的主要区别是什么？

  2. 如何计算LR(0)项集的闭包？

  3. 什么是移进-归约冲突？SLR(1)分析器如何解决这种冲突？

  4. 构建以下文法的SLR(1)分析表：

    S → A
A → aA | b

  5. 分析输入串 aab 使用你构建的SLR(1)分析表。

6. 小结

在本集中，我们详细介绍了LR(0)和SLR(1)分析器的工作原理、项集构建和分析表生成方法。LR(0)分析器是最基本的LR分析器，它通过构建项集规范族和分析表来进行语法分析，但无法处理移进-归约冲突。SLR(1)分析器通过使用FOLLOW集来限制归约的条件，解决了部分移进-归约冲突，是一种实用的语法分析方法。

7. 下集预告

下一集将介绍 LR(1)和LALR(1)分析器，详细讲解它们的工作原理、项集构建和分析表生成方法，以及如何处理SLR(1)无法解决的冲突。

8. 参考资料

  1. 《编译原理》（龙书），Alfred V. Aho 等著
  2. 《编译原理教程》，蒋立源等著
  3. 《编译器设计》，Alexander A. Stepanov 等著
  4. LR parser - Wikipedia：https://en.wikipedia.org/wiki/LR_parser
  5. Simple LR parser - Wikipedia：https://en.wikipedia.org/wiki/Simple_LR_parser
« 上一篇 LR分析器简介 下一篇 » LR(1)和LALR(1)分析器
↑