第5章 自底向上的分析

自底向上分析从输入串开始，通过不断归约到达开始符号，是最右推导的逆过程。LR 系列分析器（LR(0)/SLR(1)/LR(1)/LALR(1)）是其主要实现方式。

5.1 自底向上分析概览

移进-归约分析（Shift-Reduce Parsing）

两种基本动作：

• 移进（shift）：将输入记号压入栈顶
• 归约（reduce）：将栈顶的串 α 替换为产生式左部 A（A → α）

句柄（Handle）

• 定义：右句型中与某个产生式右部匹配且归约后得到下一个右句型的串
• 句柄总是在栈顶位置
• 移进-归约分析的核心任务：确定下一个句柄及其对应的产生式

扩充文法（Augmented Grammar）

• 增加新的开始符号 S' 和产生式 S' → S
• 目的：使分析器有唯一的接受状态

5.2 LR(0) 项的有穷自动机与 LR(0) 分析

LR(0) 项目

• 形式：[A → α·β]，圆点表示分析进度
• A → α·β：已完成 α，期望继续处理 β
• A → αβ·：归约项目（可归约）

项目集的构造

闭包操作：
对于项目集 I，重复：
  若 [A → α·Bβ] ∈ I 且 B → γ 是产生式
  则 [B → ·γ] ∈ I

转换（goto）：
goto(I, X) = Closure({[A → αX·β] | [A → α·Xβ] ∈ I})

LR(0) 分析表

• action[s, a]：状态 s 在输入 a 下的动作（s/i/r/acc）
• goto[s, A]：状态 s 遇到非终结符 A 的转移

LR 分析过程示例

使用文法 E' → E, E → E + T | T, T → id 分析输入 id + id：

步骤 | 状态栈          | 符号栈     | 输入       | 动作
─────┼─────────────────┼────────────┼────────────┼────────────
  1  | 0               |            | id + id $  | 移进
  2  | 0 3             | id         | + id $     | 归约 T→id
  3  | 0 2             | T          | + id $     | 归约 E→T
  4  | 0 1             | E          | + id $     | 移进
  5  | 0 1 4           | E +        | id $       | 移进
  6  | 0 1 4 3         | E + id     | $          | 归约 T→id
  7  | 0 1 4 5         | E + T      | $          | 归约 E→E+T
  8  | 0 1             | E          | $          | 接受

LR(0) 的局限性

• 不利用向前看信息，大量移进-归约冲突
• 实际能力有限

5.3 SLR(1) 分析

改进

• 使用 Follow 集解决归约决策
• 在状态 s 包含归约项目 A → α·时：
  • 仅在 lookahead ∈ Follow(A) 时归约
  • 否则移进或报错

SLR(1) 分析表构造

1. 构造 LR(0) 项目集规范族
2. 构造 action 表：
   - 若 [A → α·aβ] ∈ s 且 goto(s, a) = t：action[s, a] = s t（移进）
   - 若 [A → α·] ∈ s：∀a ∈ Follow(A)，action[s, a] = r A→α（归约）
   - 若 [S' → S·] ∈ s：action[s, $] = acc（接受）
3. 构造 goto 表：
   - 若 goto(s, A) = t：goto[s, A] = t

SLR(1) 冲突条件

若以下条件任一不满足，则存在冲突：

1. 若状态 s 含归约项目 A → α·，则对任何 X（终结符/非终结符），不能同时存在移进项目 A → α·Xβ
2. 若状态 s 含两个不同归约项目 A → α·和 B → β·，则 Follow(A) ∩ Follow(B) = ∅

5.4 LR(1) 和 LALR(1) 分析

LR(1) 项目

• 格式：[A → α·β, a]（a 为向前看符号）
• 比 LR(0) 携带了更多信息以解决冲突

LR(1) 闭包规则

若 [A → α·Bβ, a] ∈ I, B → γ ∈ P
则 ∀b ∈ First(βa): [B → ·γ, b] ∈ I

LR(1) vs SLR(1) 的区别

• SLR(1)：对归约项目使用全局 Follow 集
• LR(1)：对每个项目使用精确的向前看信息（First(βa)）

LALR(1) 分析

• 合并 LR(1) 项目集中的同心项目（去掉向前看后相同的状态）
• 能力比 SLR(1) 强，比 LR(1) 弱
• 表格大小与 LR(0) 相同
• Yacc 使用的方法

文法能力对比

LR(1) ⊇ LALR(1) ⊇ SLR(1) ⊇ LR(0)
           ⊇ LL(1)

5.5 Yacc：LALR(1) 分析程序的生成器

Yacc 输入文件结构

%{
C 声明（包含头文件、类型定义等）
%}

%token 记号声明

%%
语法规则和动作
规则: 选择1 { 动作1 }
    | 选择2 { 动作2 }
    ;

%%
用户子程序（C 代码）

冲突解决

• Yacc 默认规则：
  • 移进-归约冲突 → 选择移进
  • 归约-归约冲突 → 选择先出现的规则
• 可通过 %left、%right、%nonassoc 声明算符优先级

5.6 使用 Yacc 生成 TINY 分析程序

• TINY 的 Yacc 规范
• 需要配合 Lex 扫描程序或手写的扫描程序

5.7 自底向上分析中的错误校正

• Yacc 的默认错误处理：调用 yyerror，尝试丢弃栈状态直到找到特殊错误产生式
• 可通过 error 记号在文法中指定错误恢复

考试重点

★★★ 第一梯队（必考）

★★☆ 第二梯队

★☆☆ 第三梯队

重要对比