规范 LR(1) 分析

SLR给非终结符一份全局“可能接什么”的名单；LR(1)则给每个正在考虑的产生式实例附上一张局部便条。相同的 $R\to L$ 若位于赋值左侧的间接引用里，可以面对 =；若它正构成完整句子，则只能面对结束标记。局部便条把这两种情况分开。图中的LA标记这份向前看集合。

闭包计算 FIRST($\beta a$) 是向内传递便条：$B$ 完成后先遇见它右边的 $\beta$，只有这段能全部消失时，才直接面对外围 $A$ 的后续 $a$。把公式误写为 FIRST($\beta$)，会在空后缀上丢掉全部必要向前看。

精确化赋值文法 ​

仍用

初态从 $[S^{\prime }\to \cdot S,\mathrm{\$}]$ 展开 $S$，得到 $[S\to \cdot L=R,\mathrm{\$}]$ 与 $[S\to \cdot R,\mathrm{\$}]$。前者预测 $L$ 时，FIRST($=R\mathrm{\$}$)只有 =；后者预测 $R$ 时，空后缀让 $\mathrm{\$}$ 继承下来，再经 $R\to \cdot L$ 传给 $L$。所以初态的 $L$ 项目分别带 = 与 $\mathrm{\$}$。

沿 $L$ 边前进后，只有外层两个项目跨过点：

这里没有 $[R\to L\cdot ,=]$。带 = 的 $L$ 预测服务于第一条赋值产生式，并不能反向给另一条 $S\to R$ 路径新增上下文。这一格在 = 上只移进，在 $\mathrm{\$}$ 上只归约。

本例有14个可达项目状态。固定以下状态编号，输入 id=id 的执行如下：

左侧与右侧 id 后到达不同状态，不是因为 token 内容不同，而是它们结束后允许面对的上下文不同。若输入 id=，移进等号后立刻面对 $\mathrm{\$}$，状态8并无此时的动作，因此拒绝缺失的右值。

可空后缀决定便条是否继续向内传 ​

设状态中有 $[A\to \cdot BC,d]$，$C\to c\mid \epsilon$，而 $B\to b$。预测 $B$ 时必须计算 FIRST($Cd$)=$\{c,d\}$，得到两项 $[B\to \cdot b,c]$ 与 $[B\to \cdot b,d]$。若只保留 $c$，输入 bd 会被错误拒绝；若无条件继承 $d$，又会在 $C$ 不可空的文法中允许过宽归约。

这个小例子也说明向前看并非“点后可以出现的第一个字符”：$B\to \cdot b$ 的点后是 $b$，而便条上的 $c,d$ 是 $B$ 结束后才出现的字符。

LR(1)仍可能冲突，尤其歧义文法不可能得到无冲突的确定表。向前看能分开很多SLR合并的上下文，却不是任意CFG的通用解析器；想保留冲突两侧，可转向GLR公理库广义 LR 与图结构栈Generalized LR parsing · GLR parsing以图结构栈共享冲突分支，并以打包森林保存多种语法树的LR泛化方法。。

若 LR(0) 点位置总数为 $m$、终结符数为 $t$，LR(1) 项目最多 $m(t+1)$ 种，项目集合的粗上界为 $2^{m(t+1)}$。实际可达状态往往远少于这个界，但不能据此把构表成本写成输入长度的线性函数。固定表后的解析依旧每次只查看一个 token，并具有与 LR 驱动器相同的线性运行界。

正确性的关键是不丢失也不制造局部右上下文。预测规则来自最右推导中 $B$ 后面的 $\beta a$；goto只移动识别边界；归约只在便条允许的token下发生。把这些不变量与状态栈路径不变量合起来，就能证明无冲突表识别恰好文法的语言。

单元任务：解释冲突，而不是覆盖冲突 ​

拿到本例SLR表在“识别L后、下一token为=”的移进/归约冲突，要求写出两条冲突项目、说明 = 怎样进入 FOLLOW($R$)，再给出 LR(1) 在同一前缀下的便条。

解答是：移进来自 $S\to L\cdot =R$，归约来自 $R\to L\cdot$。全局 FOLLOW 中的等号沿 $S\to L=R$ 到 $L$，再沿 $L\to \ast R$ 到 $R$。但当前初态之后的局部 $R$ 来自 $S\to R$，其便条只有 $\mathrm{\$}$；因此正确动作是移进等号。验收不能只写“LR(1)更强”，必须列出这条不同的传播链，并用 id=id 与 id= 核对成功和拒绝。