LR(0) 项目自动机与移进归约

状态栈保存了沿“当前文法符号栈”运行 DFA 所经过的状态。移进是在这条路径末端续上一条边。归约则先撤去一段表示右部的路径，再从它之前的状态沿左部非终结符边前进。正因保留了整条状态历史，归约后不用从 $I_0$ 重新扫描整栈。

文法符号栈是某个最右句型中不越过最右句柄的前缀，称为可行前缀。闭包中的预测项目表达：若下一段打算识别 $B$，那么 $B$ 的任何产生式都可开始；goto 则同时推进所有可能项目。有限项目集合足以总结前缀的解析可能性，栈深度可以继续增长。

七个状态完整解析 cdd ​

给产生式编号：$r_1:S\to CC$，$r_2:C\to cC$，$r_3:C\to d$。加 $S^{\prime }\to S$ 后，可达项目集如下：

全部表格为：

s3 表示消费一个 token 后压状态 3，r3 表示按产生式 3 归约。输入 cdd 的每一步为：

第二次归约弹掉的是状态 3 和 6，露出 0，再查 GOTO[0,C]=1。若误用归约前的栈顶 6 查询 GOTO，就会查不到正确后继。

输入 cd 则只形成第一个 $C$。栈到 $[0,1]$ 时输入已经结束，ACTION[1,$\mathrm{\$}$] 为空，因此拒绝。最后读到 $d$ 或曾经归约成 $C$ 都不等于整句完成。

完整项目也可能过早 ​

改用 $S\to aS\mid a$。读入一个 $a$ 后，状态中同时有 $S\to a\cdot S$ 与 $S\to a\cdot$，闭包还预测能继续读 $a$。下一 token 为 $a$ 时，移进和立即归约都被 LR(0) 规则放进同一格。

这个冲突没有证明语言有歧义；语言只是非空的 $a$ 串。它说明“一个右部已经完整”还不足以决定此时该不该结束它。SLR公理库SLR 分析表SLR parsing · Simple LR parsing保留LR(0)状态，只在左部FOLLOW集合上允许归约的确定解析方法。加入 FOLLOW，LR(1)公理库规范 LR(1) 分析Canonical LR(1) parsing在项目中保存局部右上下文，以一个向前看token区分归约的LR构表方法。把更精确的右上下文直接附在项目上。

LR 驱动器的栈不变量解释了为何无需回溯：若表无冲突，选定动作对应唯一可行的句柄处理；每次归约都是反向走一条最右推导。接受时归约得到开始符号且输入恰好结束，因此生成的树确实属于文法。完整性还依赖 LR(0) 无冲突条件，不能对任意 CFG 的任意冲突消解作相同承诺。

令项目总数为 $m=\sum _{A\to \alpha }(|\alpha |+1)$，项目集最多有 $2^m$ 种，因此构表最坏可指数膨胀。令实际状态数为 $q$，稠密 ACTION/GOTO 表占 $O(q(|V|+|\mathrm{\Sigma }|))$。固定有用的无冲突文法后，移进/归约次数随解析树大小增长，通常按输入长度记为 $O(n)$ 时间、$O(n)$ 栈空间；构表成本与运行成本应分开报告。

状态编号没有数学意义。本页编号由按符号排序的可达搜索确定；检查另一份表时应比较项目集和转移，而不是要求“状态3”在所有资料中都代表同一集合。