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

这题其实和之前的题目一样，只是文法不同，我们可以按照相同的步骤来构造规范 LR 项集族和 LALR 项集族。

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

| I | CLOSURE(I) | GOTO(I, X) |
|---|-----------|------------|
| 0 | {S' -> .S} | |
| 1 | {S' -> S., S -> .SS+, S -> .SS*, S -> .a} | |
| 2 | {S -> SS.+, S -> SS.*} | |
| 3 | {S -> a.} | |

接下来，我们使用 LR(0) 项集族中项目集的核心来构造出规范 LR(1) 项集族。对于这个文法来说，LR(0) 项集族中的每个项目集都是 LR(1) 项集族中的核心，所以我们直接把 LR(0) 项集族中的项目集放入规范 LR(1) 项集族中：

| I | CLOSURE(I) | GOTO(I, X) |
|---|-----------|------------|
| 0 | {S' -> .S} | |
| 1 | {S' -> S., S -> .SS+, S -> .SS*, S -> .a} | |
| 2 | {S -> SS.+, S -> SS.*} | |
| 3 | {S -> a.} | |

现在，我们需要合并一些项目集。对于这个文法来说，项目集 2 和项目集 3 可以合并，因为它们的状态集合相同，且它们的向前看符号也相同，都是 $+$ 或 $*$ 或 $a$。所以，我们把它们合并成一个项目集：

| I | CLOSURE(I) | GOTO(I, X) |
|---|-----------|------------|
| 0 | {S' -> .S} | |
| 1 | {S' -> S., S -> .SS+, S -> .SS*, S -> .a} | |
| 2 | {S -> SS.+ | SS.* | a.} | |

现在，我们需要构造出这个文法的 LALR(1) 项集族。我们需要检查每个项目集的向前看符号，如果两个项目集状态相同，且它们的向前看符号集合也相同，那么我们就可以合并它们。在这个文法中，所有项目集的向前看符号都是一样的，都是 $+$ 或 $*$ 或 $a$，所以我们不需要合并任何项目集。因此，规范 LR(1) 项集族就是上面构造出来的 LALR(1) 项集族：

| I | CLOSURE(I) | GOTO(I, X) |
|---|-----------|------------|
| 0 | {S' -> .S} | |
| 1 | {S' -> S., S -> .SS+, S -> .SS*, S -> .a} | |
| 2 | {S -> SS.+ | SS.* | a.} | |

这就是这个文法的规范 LR 项集族和 LALR 项集族。