LR分析

LR 分析器结构

LR 分析器由三部分组成：

• ACTION 表：$ACTION[s_m,a_i]$ 指定状态 $s_m$ 遇到终结符 $a_i$ 时的操作
• GOTO 表：$GOTO[s_m,A]$ 指定状态 $s_m$ 遇到非终结符 $A$ 时转入的状态
• 双栈：状态栈 + 符号栈（符号栈可省略，由状态栈隐含）

四种操作

操作	含义	条件
S（移进）	将输入符号和下一状态压栈	$ACTION[s_m,a_i]=S_n$
R（规约）	按产生式 $A\to \beta$ 规约，弹出 $\Vert \beta \Vert$ 个状态	$ACTION[s_m,a_i]=R_k$
ACC（接受）	分析成功	ACTION[s_m, \] = ACC$
空/出错	语法错误	表中无定义

规约操作步骤：

1. 弹出 $2\Vert \beta \Vert$ 个元素（$\Vert \beta \Vert$ 个状态 + $\Vert \beta \Vert$ 个符号）
2. 将 $A$ 压入符号栈
3. 查 $GOTO[s_{top},A]$ 压入状态栈

LR(0) 项目

LR(0) 项目 = 产生式右部加入原点 ·。

四种 LR(0) 项目分类：

类型	形式	含义
规约项目	$A\to \alpha \cdot$	右部已完全识别，可规约
接受项目	$S^{\prime }\to S\cdot$	整个句子分析完毕（特殊规约项）
移进项目	$A\to \alpha \cdot a\beta$	期待移进终结符 $a$
待约项目	$A\to \alpha \cdot B\beta$	期待先识别 $B$

活前缀

规范句型的前缀，不包含句柄之后任何符号。

项目集规范族

B 包（Closure）计算

对于项目集 $I$，重复以下规则直到不变：

1. $I\subseteq closure(I)$
2. 若 $A\to \alpha \cdot B\beta \in closure(I)$，则对所有 $B\to \gamma \in P$，将 $B\to \cdot \gamma$ 加入 $closure(I)$

GO 函数

$GO(I,X)=closure(\{A\to \alpha X\cdot \beta \mid A\to \alpha \cdot X\beta \in I\})$

正规构造项目集规范族：

1. $C=\{closure(\{S^{\prime }\to \cdot S\})\}$
2. 对 $C$ 中每个 $I$ 和每个文法符号 $X$，若 $GO(I,X)\notin C$，则加入
3. 重复直到 $C$ 不再增大

LR(0) 分析表构造算法

前提：构造好项目集规范族 $C=\{I_0,I_1,\dots ,I_n\}$，每个 $I_k$ 对应状态 $k$。

规则 1（移进）：若 $A\to \alpha \cdot a\beta \in I_k$ 且 $GO(I_k,a)=I_j$，则 $ACTION[k,a]=S_j$。

规则 2（归约）：若 $A\to \alpha \cdot \in I_k$，则对任意 a \in V_T \cup \{\}$，$ACTION[k, a] = R_m$（$m$为产生式$A \to \alpha$的编号，$A \neq S’$）。

规则 3（接受）：若 $S^{\prime }\to S\cdot \in I_k$，则 ACTION[k, \] = ACC$。

规则 4（GOTO）：若 $GO(I_k,A)=I_j$（$A\in V_N$），则 $GOTO[k,A]=j$。

表中其余未定义的条目为出错。

重点 LR(0) 分析表构造四条规则必须掌握。

LR 分析完整示例

以 $S\to aSb\mid ab$ 为例（对应字符串 $a,b,a$ 的 LR 分析过程）：

1. 初始状态：状态栈 $[0]$，输入 $a,b,a$
2. 移进 $a$ → 状态变换
3. 规约 → 符号栈变换
4. 循环至接受或出错

冲突

• 移进 - 规约冲突：同一状态中，对同一输入符号同时存在移进项目和规约项目
• 规约 - 规约冲突：同一状态中，对同一输入符号同时存在多个规约项目

LR(0) / SLR(1) / LR(1) / LALR(1) 对比

方法	核心思想	冲突解决	表达能力
LR(0)	任意终符都规约	无解决	最弱
SLR(1)	仅当输入在 FOLLOW 中才规约	用 FOLLOW 集区分	中等
LR(1)	搜索符精确控制	每个项目带搜索符	最强
LALR(1)	同心项目集合并	合并 LR(1) 状态	接近 LR(1)

四种方法选择流程：LR(0) → 有冲突试 SLR(1) → 再试 LR(1) → LALR(1) 合并压缩

⚠️ LR 分析环环相扣，前步错后步全错。