LR(k) 的含义#

• L：从左到右扫描输入符号。
• R：最右推导的逆过程（即规范归约/最左归约）。
• k：向前看 k 个符号，用以确定归约所用规则。（k=0 → LR(0)，k=1 → LR(1)）

相比算符优先的优点#

• 算符优先只看终结符优先关系，适应面窄；发现最左素短语尾后还要回头找头。
• LR 用状态记住分析历史，直接判断句柄是否形成，适应面宽。

LR 分析器组成#

分析表（ACTION[s,a] 与 GOTO[s,X]）+ 状态栈 + 符号栈 + 总控程序。

• sn：移进，把符号和状态 n 压栈。
• rn：用第 n 个产生式归约。
• acc：接受；空格：error。

LR(0) 项目#

在产生式右部某位置加圆点 ·。圆点左=已识别部分，右=待识别部分。

• 例 S→aAcBe 有 6 个项目：S→·aAcBe、S→a·AcBe、…、S→aAcBe·。
• 特别地 A→ε 只有一个项目 A→·。

项目四分类#

CLOSURE（闭包）#

求项目集 I 的闭包：

1. I 中项目都在 CLOSURE(I) 中。
2. 若 A→α·Bβ∈CLOSURE(I)，则所有 B→·γ 也加入。
3. 重复直到不再增加新项目。

GO 转移函数#

GO(I,X) = CLOSURE({ A→αX·β | A→α·Xβ∈I }) —— 把 I 中圆点在 X 前的项目，圆点越过 X，再求闭包。

项目集规范族（构造识别活前缀的 DFA）#

1
C = { CLOSURE({S′→·S}) };
2
while (C 有新项目集) {
3
   for (每个 I∈C，每个 X∈V_N∪V_T)
4
      if (GO(I,X)≠∅ 且 GO(I,X)∉C)  C = C∪{GO(I,X)};
5
}

每个项目集是 DFA 的一个状态。

构造算法#

对项目集 Iᵢ（状态 i）：

• A→α·aβ∈Iᵢ 且 GO(Iᵢ,a)=Iⱼ ⟹ ACTION[i,a]=sj
• A→α·Bβ∈Iᵢ 且 GO(Iᵢ,B)=Iⱼ ⟹ GOTO[i,B]=j
• A→α·∈Iᵢ（归约项目）⟹ 对所有 a∈V_T∪{#}，ACTION[i,a]=rj
• S′→S·∈Iᵢ ⟹ ACTION[i,#]=acc
• 空格置 error。

冲突与 LR(0) 文法#

• 移进-归约冲突：I 中既有移进项目又有归约项目。
• 归约-归约冲突：I 中含≥2 个归约项目。
• I 无冲突称相容。若所有 I 都相容，则 G 是 LR(0) 文法。

LR(0) 分析算法#

状态栈顶为 s，输入符 a：

• ACTION[s,a]=si：a 入符号栈、i 入状态栈，输入指针后移。
• ACTION[s,a]=rj（用 A→β）：弹出 |β| 个符号/状态，A 入符号栈，GOTO[栈顶状态,A] 入状态栈，输出规则。
• ACTION[s,a]=acc：接受返回。
• 否则 error。

动机#

LR(0) 太弱：一有移进-归约或归约-归约冲突就不能用。

解决方法#

对冲突项目集 I={X→α·bβ, A→γ·, B→δ·}，面临输入 a：

• 若 a=b → 移进；
• 若 a∈FOLLOW(A) → 用 A→γ· 归约；若 a∈FOLLOW(B) → 用 B→δ· 归约；
• 否则报错。

要求相关 FOLLOW 集互不相交且与移进符不冲突。

构造 SLR(1) 表（与 LR(0) 唯一区别）#

归约项目 A→α· 只对 a∈FOLLOW(A) 填 ACTION[i,a]=rj（LR(0) 是对所有终结符填）。

本质：面临的输入符属于欲归约非终结符的 FOLLOW 集时才归约。 SLR(1) 分析表无冲突 → G 是 SLR(1) 文法，能力强于 LR(0)。

动机#

SLR 用整个 FOLLOW 集，信息仍不够精确。LR(1) 在构造状态时就带上后继符（搜索符）。

LR(1) 项目#

形如 [A→α·β, a]，a 是向前搜索符（FOLLOW 集的子集）。

闭包 CLOSURE(I)（关键区别）#

若 [A→α·Bβ, a]∈I，B→η 是产生式，则对每个 b∈FIRST(βa)，把 [B→·η, b] 加入。

• 当 β⇒ε 时 b=a，称 继承的后继符；否则称 自生的后继符。

GO 转移#

GO(I,X)=CLOSURE({ [A→αX·β,a] | [A→α·Xβ,a]∈I })

构造 LR(1) 表#

• [A→α·aβ,b]∈Iᵢ 且 GO(Iᵢ,a)=Iⱼ ⟹ ACTION[i,a]=sj
• [A→α·,a]∈Iᵢ ⟹ ACTION[i,a]=rj（仅对搜索符 a 归约）
• GO(Iᵢ,A)=Iⱼ ⟹ GOTO[i,A]=j
• [S′→S·,#]∈Iᵢ ⟹ ACTION[i,#]=acc

LR(1) 表无冲突 → G 是 LR(1) 文法，能力最强、表最大。

动机#

LR(1) 状态数太多。合并同心集以减少状态。

同心集#

• 心：项目的 LR(0) 部分（去掉搜索符）。
• 心相同的 LR(1) 项目集合并为一个，搜索符集取并集。
• 合并后转移函数自动合并，仍是同心集。
• 合并只可能引入归约-归约冲突，不会引入移进-归约冲突；合并会推迟发现错误，但出错位置依然准确。

构造步骤#

1. 构造 LR(1) 项目集规范族 C={I₀,…,Iₙ}。
2. 合并所有同心集，得 C′={J₀,…}。
3. 由 C′ 构造 ACTION/GOTO（方法同 LR(1)）。

无冲突且合并后无归约-归约冲突 → G 是 LALR(1) 文法。状态数与 LR(0) 相同，是实用主流。

判定文法属于哪类的流程#

1. 构造 LR(0) 项目集，看冲突：无冲突 → LR(0)。
2. 有冲突，用 FOLLOW 能否解决：能 → SLR(1)。
3. SLR 仍冲突，构造 LR(1)：无冲突 → LR(1)。
4. 合并同心集后无归约-归约冲突 → LALR(1)。

🧮 经典例（赋值语句文法，区分 SLR 与 LR(1)）#

S′→S, S→L=R|R, L→*R|i, R→L：

• I₂={S→L·=R, R→L·}：面临 = 时，因 =∈FOLLOW(R)，SLR 出现移进-归约冲突 → 不是 SLR(1)。
• LR(1) 中 I₂ 里 R→L· 的搜索符只有 #，面临 = 只移进不归约，冲突消除 → 是 LR(1) 文法，也是 LALR(1)。