LALR1分析

LALR(1) 分析

LALR(1)（Look-Ahead LR）通过合并 LR(1) 的同心项目集来压缩状态数。

同心项目集

同心项目集：LR(0) 部分相同、仅搜索符不同的 LR(1) 项目集。

示例：

$I_{k} = {[A \to α \cdot, a], [B \to β \cdot, c]}$ $I_{j} = {[A \to α \cdot, b], [B \to β \cdot, d]}$

$I_{k}$ 和 $I_{j}$ 同心（LR(0) 部分相同），可合并为：

$I_{kj} = {[A \to α \cdot, a / b], [B \to β \cdot, c / d]}$

GO 函数合并

合并后 GO 函数也相应合并：若 $GO (I_{k}, X) = I_{p}$ 、 $GO (I_{j}, X) = I_{q}$ 且 $I_{p}$ 、 $I_{q}$ 也同心，则 $GO (I_{kj}, X) = I_{pq}$ 。

合并的性质

不引入移进-规约冲突

若合并前无移进-规约冲突，合并后也不会引入（反证法证明）。

证明思路：若合并后某状态对输入 $a$ 有移进-规约冲突，则合并前至少有一个同心项目集对 $a$ 有冲突，与前提矛盾。

可能引入规约-规约冲突

合并可能将不同搜索符合并，导致同一状态下多个规约项目共享搜索符，产生规约-规约冲突。

重点 LALR(1) 合并不引入移进-规约冲突，但可能引入规约-规约冲突。

LALR(1) 错误延迟

相比 LR(1)，LALR(1) 合并后可能延迟发现错误：在错误状态下多执行若干步规约后才报告错误，但不会漏报。

LALR(1) 完整示例

文法 $G$ ：

$(0) S^{'} \to S (1) S \to L = R ∣ R (2) L \to * R ∣ I (3) R \to L$

LR(1) 项目集规范族（共 9 个状态 $I_{0} \sim I_{8}$ ）：

状态	内容
$I_{0}$	$[S' \to ·S, \$ ], [S \to ·L=R, $], [S \to ·R, $], [L \to ·*R, =/$], [L \to ·I, =/$], [R \to ·L, $]$
$I_{1}$	$[S' \to S·, \$ ]$
$I_{2}$	$[S \to L·=R, \$ ], [R \to L·, $]$
$I_{3}$	$[S \to R·, \$ ]$
$I_{4}$	$[L \to ·R, =/\$ ], [R \to ·L, =/$], [L \to ·R, =/$], [L \to ·I, =/$]$
$I_{5}$	$[L \to I·, =/\$ ]$
$I_{6}$	$[S \to L=·R, \$ ], [R \to ·L, $], [L \to ·*R, $], [L \to ·I, $]$
$I_{7}$	$[L \to *R·, =/\$ ]$
$I_{8}$	$[R \to L·, \$ ]$

同心项目集： $I_{4}$ 和 $I_{6}$ （LR(0) 部分相同，仅搜索符不同 $=/\$$ vs$ $$），可合并。

合并后 LALR(1) 将 9 状态压缩为 8 状态（ $I_{4}$ 与 $I_{6}$ 合并），分析表也相应合并。

四种方法选择流程

LR(0) → 有冲突？
  ├── 无冲突 → LR(0) 文法 ✓
  └── 有冲突 → 尝试 SLR(1)
                ├── 无冲突 → SLR(1) 文法 ✓
                └── 有冲突 → 尝试 LR(1)
                              ├── 无冲突 → 尝试 LALR(1) 合并
                              │             ├── 无冲突 → LALR(1) 文法 ✓
                              │             └── 有冲突 → LR(1) 文法 ✓
                              └── 有冲突 → 文法不是 LR 文法 ✗

LR(0)：能力最弱，冲突最多
SLR(1)：用 FOLLOW 集部分解决冲突
LR(1)：能力最强，但状态数最多
LALR(1)：接近 LR(1) 能力，状态数接近 SLR(1)

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

Notes@Tsukino

探索