第81集：自底向上分析概述

学习目标

• 理解自底向上分析的基本思想和工作原理
• 掌握移进-归约分析的基本概念和操作
• 理解句柄的定义和识别方法
• 了解LR分析法的基本原理和发展历史
• 比较自底向上分析与自顶向下分析的优缺点
• 通过示例理解自底向上分析的过程

一、自底向上分析的基本思想

自底向上分析是一种从输入串开始，逐步进行归约，直到归约到文法的开始符号的语法分析方法。其基本思想可以概括为：

1. 从叶子节点开始：从输入串的符号开始，这些符号对应于语法树的叶子节点
2. 逐步归约：将输入串中的符号或符号串逐步归约为文法的非终结符
3. 构建语法树：归约过程对应于自下而上构建语法树的过程
4. 到达开始符号：当整个输入串被归约为文法的开始符号时，分析成功

自底向上分析的过程可以看作是自顶向下分析的逆过程。自顶向下分析是从开始符号出发，通过推导产生输入串；而自底向上分析则是从输入串出发，通过归约到达开始符号。

示例：算术表达式的自底向上分析

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

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

对于输入串 id + id * id，自底向上分析的过程如下：

1. 初始状态：输入串为 id + id * id
2. 归约1：将第一个 id 归约为 F，得到 F + id * id
3. 归约2：将 F 归约为 T，得到 T + id * id
4. 归约3：将 T 归约为 E，得到 E + id * id
5. 移进：将 + 移进，得到 E + id * id
6. 归约4：将第二个 id 归约为 F，得到 E + F * id
7. 归约5：将 F 归约为 T，得到 E + T * id
8. 移进：将 * 移进，得到 E + T * id
9. 归约6：将第三个 id 归约为 F，得到 E + T * F
10. 归约7：将 T * F 归约为 T，得到 E + T
11. 归约8：将 E + T 归约为 E，得到 E
12. 分析成功：归约到了文法的开始符号 E

二、移进-归约分析

移进-归约分析是自底向上分析的一种主要方法，其核心操作包括移进和归约两种：

1. 移进操作

移进（Shift）是指将输入串中的下一个符号移到分析栈的栈顶。这一操作相当于在语法树中构建叶子节点，或者在等待更多的符号以形成一个可以归约的短语。

2. 归约操作

归约（Reduce）是指将分析栈顶的一个或多个符号（称为句柄）替换为对应的非终结符。这一操作相当于在语法树中构建内部节点，将叶子节点或较小的子树组合成更大的子树。

3. 分析栈的使用

移进-归约分析器使用一个栈来存储已经分析过的符号和归约得到的非终结符。分析过程中，分析器不断地在移进和归约操作之间做出选择，直到：

• 成功：栈中只剩下开始符号，且输入串已全部处理完毕
• 失败：无法进行有效的移进或归约操作

4. 移进-归约分析的状态表示

在移进-归约分析过程中，分析器的状态可以用以下三个部分来表示：

1. 分析栈：存储已经处理过的符号和归约得到的非终结符
2. 剩余输入：尚未处理的输入符号
3. 下一步操作：移进或归约

示例：移进-归约分析过程

对于输入串 id + id * id，使用上述算术表达式文法，移进-归约分析的过程如下：

三、句柄的概念

1. 句柄的定义

在自底向上分析中，句柄（Handle）是一个重要的概念。对于一个句型（由文法的开始符号推导得到的符号串），句柄是指：

• 该句型中的一个子串
• 这个子串可以被归约为一个非终结符
• 归约之后得到的新句型仍然是文法的一个句型
• 句柄对应于语法树中的一个直接子树的叶子节点

更形式化地说，设文法G，开始符号为S，αβγ是G的一个句型。如果存在推导序列：

S ⇒* αAγ ⇒ αβγ

其中A → β是G的一个产生式，那么β是句型αβγ相对于非终结符A的句柄。

2. 句柄的性质

句柄具有以下重要性质：

• 唯一性：对于一个句型，可能存在多个句柄（当文法是二义性的时），但对于无歧义文法，每个句型有且仅有一个句柄
• 最左性：在移进-归约分析中，我们总是选择句型中最左边的句柄进行归约，这种归约称为最左归约
• 与推导的关系：最左归约是最右推导的逆过程。最右推导也称为规范推导，因此最左归约也称为规范归约

3. 句柄的识别

在自底向上分析中，识别句柄是关键步骤。不同的自底向上分析方法有不同的句柄识别方法：

• 简单优先分析：通过优先关系矩阵识别句柄
• 算符优先分析：通过算符优先关系识别句柄
• LR分析：通过分析表和状态栈识别句柄

在LR分析中，句柄的识别是通过分析表和状态栈来实现的，这使得LR分析具有更强的能力和更广的适用范围。

四、LR分析法的基本原理

1. LR分析的概念

LR分析是一种有效的自底向上分析方法，其中：

• L 表示从左到右扫描输入串
• R 表示构造最右推导的逆过程（最左归约）

LR分析的核心思想是：在分析过程中，利用已分析的历史信息和当前输入符号来决定下一步的操作（移进或归约），而不需要回溯。

2. LR分析器的组成

一个典型的LR分析器由以下部分组成：

• 输入缓冲区：存储待分析的输入串
• 分析栈：存储状态和文法符号
• 分析表：指导分析器的操作，包括移进表和归约表
• 控制程序：根据分析表和当前状态执行移进或归约操作

3. LR分析的过程

LR分析的基本过程如下：

1. 初始化：分析栈中压入初始状态和结束符$，输入指针指向输入串的第一个符号
2. 查找分析表：根据当前栈顶状态和当前输入符号，查找分析表
3. 执行操作：
   • 移进：将输入符号移进栈，同时将对应的下一状态压入栈
   • 归约：根据产生式将栈顶的句柄归约为非终结符，同时弹出栈中对应的状态和符号，然后根据归约后的非终结符和当前栈顶状态查找分析表，将对应的新状态压入栈
   • 接受：分析成功
   • 报错：发现语法错误
4. 重复步骤2-3：直到分析成功或报错

4. LR分析的发展历史

LR分析方法的发展经历了以下几个重要阶段：

• LR(0)分析：由Knuth于1965年提出，是最早的LR分析方法，但能力较弱
• SLR(1)分析：Simple LR，是对LR(0)的改进，利用FOLLOW集解决冲突
• LR(1)分析：由Kasami和Shamir于1969年提出，通过引入展望符提高分析能力
• LALR(1)分析：Look-Ahead LR，由DeRemer于1971年提出，是对LR(1)的优化，具有与LR(1)相同的能力但状态数更少

五、自底向上分析与自顶向下分析的比较

六、自底向上分析的类型

自底向上分析方法主要包括以下几种类型：

1. 简单优先分析

• 基本思想：通过定义文法符号之间的优先关系来识别句柄
• 优缺点：实现简单，但适用范围有限，只能处理部分文法

2. 算符优先分析

• 基本思想：专门用于处理算符文法，通过定义算符之间的优先关系来识别句柄
• 优缺点：实现简单，适用于表达式分析，但只能处理算符文法

3. LR分析

• 基本思想：通过分析表和状态栈来识别句柄，是一种表驱动的分析方法
• 类型：包括LR(0)、SLR(1)、LR(1)和LALR(1)等
• 优缺点：分析能力强，能处理大多数上下文无关文法，但实现较复杂

4. 移进-归约分析的其他变体

• Earley算法：一种通用的自底向上分析算法，能处理任意上下文无关文法
• CYK算法：基于动态规划的自底向上分析算法，用于识别上下文无关文法

七、自底向上分析的示例

示例：if语句的自底向上分析

考虑以下简化的if语句文法：

S → if E then S else S | assign
E → true | false
assign → id = expr
expr → id | num

对于输入串 if true then id = x else id = y，自底向上分析的过程如下：

1. 移进 if
2. 移进 true
3. 归约 true 为 E（使用E → true）
4. 移进 then
5. 移进 id
6. 移进 =
7. 移进 x
8. 归约 x 为 expr（使用expr → id）
9. 归约 id = expr 为 assign（使用assign → id = expr）
10. 归约 assign 为 S（使用S → assign）
11. 移进 else
12. 移进 id
13. 移进 =
14. 移进 y
15. 归约 y 为 expr（使用expr → id）
16. 归约 id = expr 为 assign（使用assign → id = expr）
17. 归约 assign 为 S（使用S → assign）
18. 归约 if E then S else S 为 S（使用S → if E then S else S）
19. 分析成功

八、自底向上分析的优缺点

优点

• 分析能力强：能处理更多类型的文法，包括左递归文法
• 无需回溯：分析过程确定，不需要回溯，效率高
• 错误检测：虽然错误检测较晚，但错误恢复能力较强
• 适用性广：LR分析方法能处理大多数实际编程语言的文法

缺点

• 实现复杂：特别是LR分析表的构建较为复杂
• 分析表大小：对于复杂文法，LR分析表可能会非常大
• 错误定位：错误检测位置可能离实际错误位置较远
• 学习曲线：理解LR分析的原理和实现需要较多的时间和精力

九、LR分析的变体

LR分析有多种变体，每种变体都有其特点和适用场景：

1. LR(0)分析

• 特点：分析表构造简单，但分析能力最弱
• 适用场景：只能处理部分简单文法
• 冲突：容易产生移进-归约冲突和归约-归约冲突

2. SLR(1)分析

• 特点：通过使用FOLLOW集解决部分冲突，是对LR(0)的改进
• 适用场景：能处理更多文法，但仍有局限性
• 冲突：比LR(0)少，但仍可能存在冲突

3. LR(1)分析

• 特点：通过引入展望符（lookahead）解决冲突，分析能力最强
• 适用场景：能处理大多数上下文无关文法
• 缺点：分析表可能非常大，空间复杂度高

4. LALR(1)分析

• 特点：通过合并LR(1)分析表中的同心状态，减少表的大小
• 适用场景：在分析能力和表大小之间取得平衡，是实际编译器中最常用的LR变体
• 工具：Yacc/Bison等工具使用LALR(1)分析方法

十、自测问题

1. 选择题：自底向上分析的基本思想是：
   A. 从开始符号出发，推导产生输入串
   B. 从输入串出发，归约到开始符号
   C. 同时从开始符号和输入串出发，双向推导
   D. 随机选择推导或归约操作

2. 选择题：在移进-归约分析中，句柄是指：
   A. 当前输入符号
   B. 栈顶的符号
   C. 句型中可以归约的子串
   D. 文法的开始符号

3. 简答题：简述LR分析的基本原理和过程。

4. 简答题：比较自底向上分析与自顶向下分析的优缺点。

5. 实践题：对于文法 E → E + T | T, T → T * F | F, F → ( E ) | id，给出输入串 ( id + id ) * id 的自底向上分析过程。

十一、小结

本集介绍了自底向上分析的基本概念和方法，包括：

1. 自底向上分析的基本思想：从输入串开始，逐步归约到文法的开始符号
2. 移进-归约分析：通过移进和归约操作进行分析
3. 句柄的概念：句型中可以归约的子串，对应于语法树的一个直接子树
4. LR分析法的基本原理：通过分析表和状态栈识别句柄，不需要回溯
5. 自底向上分析与自顶向下分析的比较：自底向上分析具有更强的分析能力，但实现更复杂
6. LR分析的变体：包括LR(0)、SLR(1)、LR(1)和LALR(1)等

自底向上分析，特别是LR分析方法，是现代编译器中最常用的语法分析方法之一。它具有强大的分析能力，能处理大多数实际编程语言的文法，同时通过表驱动的方式实现了高效的分析过程。

十二、下集预告

下一集我们将详细学习LR(0)分析方法，包括LR(0)项集的构造、LR(0)自动机的构建、LR(0)分析表的构造以及LR(0)分析的过程。这将为我们后续学习更复杂的LR变体（如SLR(1)、LR(1)和LALR(1)）打下基础。

参考资料

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

通过本集的学习，你应该对自底向上分析的基本概念和方法有了全面的了解。自底向上分析是一种强大的语法分析方法，特别是LR分析方法，它为现代编译器的语法分析提供了坚实的理论基础。在后续的学习中，我们将深入探讨各种LR分析变体的具体实现和应用。