《龙书》语法分析章节Example-4.64的理解困惑

我们直接结合LALR(1)的闭包算法规则，一步步推导初始闭包的生成过程，就能明白为什么L→.*R和L→.id的向前看符号是#/=：

闭包核心规则回顾 #

对于闭包中的项目 [A → α.Bβ, a]，若存在产生式 B → γ，则计算集合 FIRST(βa)，将所有 [B → .γ, b]（其中b ∈ FIRST(βa)）加入闭包，重复此过程直到没有新项目可添加。

逐步推导初始闭包CLOSURE({ [S'→.S , #] }) #

1. 初始项目：[S'→.S, #]
   根据S的产生式，添加两个项目：

   • [S→.L=R, #]（β为空，FIRST(ε#) = {#}）
   • [S→.R, #]（同理，FIRST(ε#) = {#}）

2. 处理[S→.L=R, #]
   这里A=S，B=L，β= =R，a=#。计算FIRST(=R #)：因为β的首符号是终结符=，所以FIRST(=R #) = {=}。
   对L的两个产生式，添加：

   • [L→.*R, =]
   • [L→.id, =]

3. 处理[S→.R, #]
   根据R的产生式R→L，添加项目：

   • [R→.L, #]（β为空，FIRST(ε#) = {#}）

4. 处理[R→.L, #]
   这里A=R，B=L，β=ε，a=#。计算FIRST(ε#) = {#}。
   对L的两个产生式，添加：

   • [L→.*R, #]
   • [L→.id, #]

合并重复项目 #

将步骤2和步骤4中生成的L相关项目合并，就得到：

• L→.*R, #/=
• L→.id, #/=

这就是原文中两个项目同时带有#和=的原因——它们分别来自两条不同路径的闭包扩展：一条是S→.L=R,#带来的=，另一条是R→.L,#带来的#。

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