关于Aho&Ullman书中LALR(1)分析算法闭包计算的疑问

你疑惑的核心是对闭包算法中lookahead计算规则的理解偏差，加上可能忽略了文法中的某条产生式，具体拆解如下：

闭包算法的正确规则 #

当从项 [A→α.Bβ, a] 生成非终结符B的产生式对应的项时，新项的lookahead是 FIRST(βa)，而非仅 FIRST(β)——这里的β是B之后的文法符号串，a是原项的lookahead集合。如果β可以推导出空串，FIRST(βa)还会包含a中的所有元素。

示例中的具体推导 #

示例里的初始项是 [S'→.S, #]，假设文法中S有两条产生式：S→L=R 和 S→L，闭包计算会分两路展开：

1. 从 [S→.L=R, #] 推导L的产生式：
   • β是=R，a是#，计算FIRST(=R#)。因为=是终结符，所以结果是{=}，对应L的项lookahead为=。
2. 从 [S→.L, #] 推导L的产生式：
   • β是空串（L之后没有符号），计算FIRST(ε#)（ε代表空串），结果就是{#}，对应L的项lookahead为#。

把这两个来源的lookahead集合合并，就得到了示例中项 [L→.*R, =/#] 的lookahead集合——=和#的并集。

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