Computer Science

WangMC Blog

LR0分析与预测分析表

发表于 更新于 分类于
本文字数： 5.7k 阅读时长 ≈ 5 分钟

结合AI，根据视频，进行整理

LR(0)分析过程详解

引言

LR(0)分析是一种自底向上的语法分析方法，属于LR分析法中最简单的一种形式。LR(0)分析法的特点是不需要向前看符号就可以确定是进行归约还是移进操作。LR(0)分析的核心思想是构造一个识别文法活前缀的确定有限自动机(DFA)，然后基于这个DFA来构造LR(0)分析表。

LR(0)分析的主要优势在于：

  • 分析能力较强，能够处理大部分实用的程序设计语言文法

  • 分析效率高，时间复杂度为O(n)，其中n是输入串的长度

  • 构造方法系统化，便于自动化实现

基本概念

活前缀

定义： 活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

对于规范句型 ，其中 为句柄，如果 ，则符号串 （）是 的活前缀。（ 必为终结符串）

性质：

  • 活前缀中可能包含句柄的全部符号（此时应进行归约）

  • 活前缀中可能只包含句柄的一部分（此时应继续移进）

  • 活前缀中可能不包含句柄的任何符号（此时应继续移进或归约其他产生式）

在规范归约过程中，保证分析栈中总是活前缀，就说明分析采取的移进/归约动作是正确的。

拓广文法

为了处理输入结束的情况，需要对原始文法进行拓广。

定义： 将文法 拓广为 ，构造方法如下：

  • 构造文法 ，它包含了整个

  • 引进不出现在 中的非终结符

  • 添加产生式

  • 是 的开始符号

称 是 的拓广文法。

作用：

  • 确保文法有唯一的开始符号

  • 便于识别整个句子的接受状态

  • 统一处理归约和接受动作

LR(0)项目

LR(0)项目是刻画分析过程中产生式右部识别进度的工具。

定义： 在每个产生式的右部添加一个圆点（·）来表示当前分析的位置，这样的产生式称为LR(0)项目。

对于产生式 ，可以产生四个项目：

项目分类：

  1. 归约项目： 形如 的项目

    • 表示栈顶已形成句柄 ，下一步动作应该是按该产生式归约
    • 特殊情况： 称为接受项目，表示整个句子已分析完毕

  2. 移进项目： 形如 的项目（）

    • 表示期待从输入串中移进一个终结符 ，以待形成句柄

  3. 待约项目： 形如 的项目（）

    • 表示期待从输入串中进行归约而得到 ，然后进一步得到 的全部右部

LR(0)项目集规范族的构造

LR(0)项目集规范族是构成识别文法活前缀的DFA的项目集（状态）的全体。

CLOSURE函数

CLOSURE函数用于计算项目集的闭包，确保项目集中包含所有可能的有效项目。

定义： 设 是文法 的任一项目集，CLOSURE() 是包含 的最小项目集，满足：

  1. 的任何项目都属于 CLOSURE()

  2. 若 属于 CLOSURE()，则对任何关于 的产生式 ，项目 也属于 CLOSURE()

  3. 重复执行上述两步骤，直到 CLOSURE() 不再增大为止

GO函数

GO函数（状态转换函数）用于计算项目集在输入某个文法符号后的转移。

定义： 设 是拓广文法 的任一项目集， 为一文法符号，则：

其中

直观含义：

  • 若 是对某个活前缀 有效的项目集

  • 那么 便是对 有效的项目集

构造算法

算法步骤：

  1. 初始化：

    • 构造拓广文法
    • 计算初始项目集
    • 将 加入项目集规范族

  2. 迭代构造：

    • 对于 中的每个项目集
    • 对于每个文法符号
    • 计算
    • 如果 非空且不在 中，则将 加入

  3. 终止条件：

    • 不再有新的项目集可以添加到 中

LR(0)分析表的构造

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

ACTION表

定义： ACTION表是一个二维表，行代表状态（项目集），列代表终结符（包括#表示输入结束）。

构造规则：

  1. 移进动作：

    • 若项目 在 中
    • 且
    • 则 ACTION[k][a] = “s j”（移进a，转向状态j）

  2. 归约动作：

    • 若项目 在 中
    • 且该产生式是拓广文法中的第m个产生式
    • 则对于所有终结符 ，ACTION[k][a] = “r m”（按第m个产生式归约）

  3. 接受动作：

    • 若项目 在 中
    • 则 ACTION[k][#] = “acc”（接受）

GOTO表

定义： GOTO表是一个二维表，行代表状态（项目集），列代表非终结符。

构造规则：

  • 若 （ 是非终结符）

  • 则 GOTO[k][A] = j

构造算法

算法步骤：

  1. 构造项目集规范族：

    • 按照前述方法构造LR(0)项目集规范族

  2. 构造ACTION表：

    • 对于每个状态 （对应项目集 ）
    • 对于每个终结符
    • 根据项目集中的项目类型设置相应的动作

  3. 构造GOTO表：

    • 对于每个状态
    • 对于每个非终结符
    • 计算 并设置相应的状态转移

  4. 检查冲突：

    • 若任何状态中同时存在移进项目和归约项目，则存在移进/归约冲突
    • 若任何状态中存在多个归约项目，则存在归约/归约冲突
    • LR(0)文法要求不存在上述冲突

实例分析

让我们通过一个具体的例子来说明LR(0)分析的完整过程。

示例文法

考虑以下文法 ：

1
2
3
E → aA
A → cA
A → d

步骤1：拓广文法

构造拓广文法 ：

1
2
3
4
0: S' → E
1: E → aA
2: A → cA
3: A → d

步骤2：构造项目集规范族

初始项目集 I0：

  • 包含项目：

    • （因为 是非终结符）

计算其他项目集：

    • 项目： （接受项目）

    • 项目：
    • 闭包：

    • 项目： （归约项目，对应产生式1）

    • 项目：
    • 闭包：

    • 项目： （归约项目，对应产生式2）

    • 项目： （归约项目，对应产生式3）

  • （自循环）

步骤3：构造LR(0)分析表

ACTION表和GOTO表：

状态 ACTION GOTO
a c d # E A
0 s2 1
1 acc
2 s4 s6 3
3 r1 r1 r1 r1
4 s4 s6 5
5 r2 r2 r2 r2
6 r3 r3 r3 r3

步骤4：分析输入串 “acd#”

分析过程：

步骤 状态栈 符号栈 余留输入串 ACTION GOTO
1 0 # acd# s2
2 02 #a cd# s4
3 024 #ac d# s6
4 0246 #acd # r3 5
5 0245 #acA # r2 3
6 023 #aA # r1 1
7 01 #E # acc

分析结果： 输入串 “acd#” 是合法的句子。

tranformfunciton

image-20251022111006175

冲突处理

在构造LR(0)分析表时，可能会遇到两种类型的冲突：

移进/归约冲突 (Shift/Reduce Conflict)

定义： 在同一个项目集中同时存在移进项目和归约项目。

示例：

1
2
3
项目集 I:
A → α · aβ  (移进项目)
B → γ ·     (归约项目)

处理方法：

  • LR(0)文法不允许这种冲突

  • 需要使用更强的LR分析法，如SLR(1)、LR(1)或LALR(1)

  • SLR(1)方法通过Follow集来解决冲突

归约/归约冲突 (Reduce/Reduce Conflict)

定义： 在同一个项目集中存在多个归约项目。

示例：

1
2
3
项目集 I:
A → α ·     (归约项目)
B → β ·     (归约项目)

处理方法：

  • LR(0)文法不允许这种冲突

  • 需要修改文法结构

  • 或者使用LR(1)方法通过向前看符号来解决

SLR(1)方法简介

SLR(1)（Simple LR(1)）是对LR(0)的改进，通过Follow集来解决移进/归约冲突。

Follow集定义：

  • Follow(A) 是所有可能在句型中紧跟在A后面的终结符的集合

SLR(1)解决冲突规则：

  • 对于移进项目 和归约项目

  • 如果 ，则在输入符号为a时选择移进

  • 如果 ，则在输入符号为a时选择归约

SLR预测分析表

SLR文法的定义

定义： 如果一个文法 的拓广文法 的LR(0)项目集规范族中存在冲突，但是这些冲突可以通过Follow集来解决，则称 是SLR(1)文法。

SLR(1)（Simple LR(1)）是对LR(0)的改进，通过引入Follow集来解决移进/归约冲突。

Follow集的计算

定义： Follow(A) 是所有可能在句型中紧跟在非终结符A后面的终结符的集合。

计算规则：

  1. 基本规则：

    • You can't use 'macro parameter character #' in math modeFollow(S’) = {#}，其中 是拓广文法的开始符号
    • 如果有产生式 ，则
    • 如果有产生式 或 且 ，则

  2. 算法：

    • 初始化 You can't use 'macro parameter character #' in math modeFollow(S’) = {#}
    • 反复应用上述规则，直到Follow集不再变化为止

SLR分析表的构造算法

算法12.1：SLR分析表构造算法

输入： 拓广文法 ，LR(0)项目集规范族 ，Follow集

输出： SLR分析表

步骤：

  1. 初始化：

    • 同LR(0)分析表的初始化

  2. 构造ACTION表：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    for each state k in 0..n:
        for each item [A → α·aβ] in Ik:
            j = GOTO(k, a)
            ACTION[k][a] = "shift j"
        
        for each item [A → α·] in Ik:
            if A is S':
                ACTION[k][#] = "accept"
            else:
                m = production_number(A → α)
                for each a in Follow(A):
                    if ACTION[k][a] is error:
                        ACTION[k][a] = "reduce m"
                    else:
                        return "conflict cannot be resolved"

  3. 构造GOTO表：

    • 同LR(0)分析表的GOTO表构造

SLR与LR(0)的比较

能力比较：

  • SLR(1)的分析能力强于LR(0)

  • SLR(1)能够处理许多LR(0)无法处理的文法

  • 但SLR(1)仍然弱于LR(1)和LALR(1)

实现复杂度：

  • SLR(1)的实现复杂度略高于LR(0)

  • 需要额外计算Follow集

  • 冲突解决逻辑更复杂

冲突处理能力：

冲突类型 LR(0) SLR(1)
移进/归约 无法处理 可以通过Follow集处理
归约/归约 无法处理 无法处理

SLR分析表的实例

示例文法：

1
2
3
S → L = R | R
L → *R | id
R → L

拓广文法：

1
2
3
4
5
6
0: S' → S
1: S → L = R
2: S → R
3: L → *R
4: L → id
5: R → L

Follow集计算：

  • Follow(S’) = {#}

  • Follow(S) = {#}

  • Follow(L) = {=, #}

  • Follow® = {=, #}

SLR分析表的部分内容：

状态 ACTION GOTO
id * = # S L R
0 s5 s4 1 2 3
1 acc
2 s6 r2
3 r4 r4
4 s5 s4 7 8
5 r6 r6
6 s5 s4 9 10
7 r1 r1
8 r3 r3
9 s6 r2
10 r4 r4

SLR分析的局限性

1. 归约/归约冲突无法解决：

  • SLR(1)仍然无法处理归约/归约冲突

  • 需要修改文法或使用更强的分析方法

2. Follow集可能过于宽泛：

  • Follow集包含了所有可能的后继符号

  • 可能导致在某些情况下做出错误的归约决策

3. 某些文法仍然无法处理：

  • 存在一些文法既不是LR(0)也不是SLR(1)

  • 需要使用LR(1)或LALR(1)方法

LR分析方法的比较

各种LR方法的能力比较

分析方法 能力 实现复杂度 表大小 适用场景
LR(0) 最弱 最简单 最小 理论研究，简单文法
SLR(1) 较强 简单 小 教学，简单语言
LALR(1) 强 中等 中等 大多数程序设计语言
LR(1) 最强 复杂 大 理论研究，复杂语言