LR(0)与LR(1)的GOTO函数是否存在差异？LALR(1)解析器生成器构建困惑

问题背景 #

你在编写LALR(1)解析器生成器时，参考《龙书》构建解析表，对GOTO函数的使用产生困惑，使用的语法为：

S -> E
E -> E + T | T
T -> T * F | F
F -> ( E ) | id

相关状态定义：

• LR(0)起始状态0是{[S -> .E]}的闭包，GOTO(0, T)得到状态1，项集为{[E -> T.], [T -> T .* F]}
• 构建LALR(1)自动机时，给LR(0)核心项添加向前看符号后，状态0核心项为{[S -> .E, $]}，状态1核心项为{[E -> T., $/+/)], [T -> T .* F, $/+/*/)]}

你的疑问：标准解析器生成器输出的LALR(1)表显示GOTO(0, T)=1（和LR(0)结果一致），但你自己计算LR(1)的GOTO(0, T)得到项集{[E -> T., $/+], [T -> T .* F, $/+/*]}，和状态1的项集不匹配，想知道哪里出错。

问题解答 #

核心原因：LALR(1)基于LR(1)同心项集合并 #

你混淆了LR(1)自动机和LALR(1)自动机的构建逻辑：

• 你计算的LR(1)中GOTO(0,T)的项集是正确的，但这个项集和状态1对应的LR(1)项集是同心项集——即它们的LR(0)核心部分完全相同，仅向前看符号不同。
• LALR(1)的核心优化就是将所有同心的LR(1)项集合并为一个状态，合并后该状态的向前看符号取所有同心项集的向前看符号的并集。你算出的GOTO(0,T)的LR(1)项集，和状态1的LR(1)项集属于同心项，因此在LALR(1)中会被合并为同一个状态（也就是状态1），这就是标准生成器显示GOTO(0,T)=1的原因。

细节纠正：状态1的向前看符号是合并结果 #

状态1的LALR(1)向前看符号$/+/*/)是合并多个同心LR(1)项集的结果：

• 你算出的GOTO(0,T)的项集提供了向前看符号$/+（来自E→.T的推导）和$/+/*（来自T→.T*F的推导）
• 状态1还会接收其他路径的LR(1)项集（比如从处理( E的状态通过T转移过来的项集），这些项集的向前看符号包含)，合并后就得到了完整的$/+/*/)集合。

LALR(1)的GOTO函数实现逻辑 #

LALR(1)的GOTO函数并非直接复用LR(0)的GOTO，而是遵循以下逻辑：

1. 先构建完整的LR(1)项集，合并所有同心项集
2. 合并后状态的GOTO，对应原LR(1)项集GOTO结果的同心项合并后的状态
   但由于同心项集的GOTO结果必然也是同心的，因此实际实现中可以基于LR(0)的状态转移关系，再为合并后的状态添加合并后的向前看符号，最终效果和直接合并LR(1)项集完全一致。

内容的提问来源于stack exchange，提问作者sudgy