LALR(1)解析器DFA构建中核心产生式前瞻符添加规则疑问

我们以如下语法为例：

S -> E
E -> ( E )
E -> N O E
E -> N
N -> 1
N -> 2
N -> 3
O -> +
O -> -

构建LALR(1)的DFA时，发现goto(0, N)对应的项目集为：
{[E -> N.O E, $/)]; [E -> N., $/)]}
疑问在于：)这个前瞻符的来源是什么？为何会出现在这个项目集中？

核心原因：同心项目集合并与FOLLOW集传递 #

1. 初始项目集的闭包
   状态0的初始项目是[S -> .E, $]，通过闭包计算生成的核心项目包括：

   • [E -> .( E ), $]
   • [E -> .N O E, $]
   • [E -> .N, $]

2. 分支路径的前瞻符传递
   当计算goto(0, ()时，得到项目[E -> ( .E ), $]。根据LALR(1)的闭包规则：对于项目[A -> α . B β, a]，B的产生式B -> γ会生成项目[B -> .γ, FIRST(βa)]。
   此处β=)，a=$，FIRST()$)的结果是)，因此该项目的闭包会生成：

   • [E -> .( E ), )]
   • [E -> .N O E, )]
   • [E -> .N, )]

3. 同心项目集的合并
   上述两条路径中：

   • 从状态0的[E -> .N O E, $]/[E -> .N, $]执行goto(N)，得到项目集{[E -> N.O E, $]; [E -> N., $]}
   • 从分支路径的[E -> .N O E, )]/[E -> .N, )]执行goto(N)，得到项目集{[E -> N.O E, )]; [E -> N., )]}

   这两个项目集是同心项目集——核心产生式完全一致，仅前瞻符不同。LALR(1)的核心优化逻辑就是合并所有同心项目集，合并后将两个项目集的前瞻符合并，因此最终的项目集就同时包含了$和)，即你看到的$/)]。

补充说明 #

你提到状态2的[E -> .N, )]与[E -> N., $]合并正确，本质上是同样的逻辑：状态2本身就是合并了不同来源的同心项目，而goto(0, N)对应的项目集也是跨路径的同心项目合并结果，并非仅来自状态0的初始项目传递。

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