为练习 4.2.1 的文法 S -> S S + | S S * | a 构造 规范 LR 项集族 LALR 项集族

首先，我们需要构造出这个文法的 LR(0) 项集族：

$I_0$:

S -> .S S +
S -> .S S *
S -> .a

$I_1$:

S -> S .S +   [S]
S -> S .S *   [S]
S -> .S S +   [S, +]
S -> .S S *   [S, *]
S -> .a        [$]

$I_2$:

S -> S S .+   [+, S]
S -> S S .*   [*, S]

$I_3$:

S -> S S +.   [$]
S -> S S *.   [$]

现在我们需要合并这些项集，来构造出文法的 LALR 项集族：

$I_0$:

S -> .S S +     [S]
S -> .S S *     [S]
S -> .a          [$]

$I_1$:

S -> S .S +     [S]
S -> S .S *     [S]
S -> .S S +     [S, +]
S -> .S S *     [S, *]
S -> .a          [$]

$I_2$:

S -> S S .+     [S]
S -> S S .*     [S]
S -> .S S +     [+, S]
S -> .S S *     [*, S]

$I_3$:

S -> S S +.     [$]
S -> S S *.     [$]

可以看出，LALR 项集族与 LR(0) 项集族基本相同，只有 $I_2$ 和 $I_3$ 不同。在 LR(0) 项集族中，$I_2$ 和 $I_3$ 是分开的项集，但在 LALR 项集族中，我们将它们合并为一个项集。这样做的好处是减少了冲突，从而使得分析表更容易构造和使用。