为练习 4.2.1 的文法 s -> s s + | s s * | a 构造 规范 lr 项集族 lalr 项集族

在为文法 S -> S S | S S * | a 构造规范 LR(1)项集族和LALR(1)项集族之前，我们需要先构造这个文法的LR(1)项目集规范族。

首先，我们需要计算文法的FIRST和FOLLOW集合。

FIRST(S) = {a}
FIRST(*) = {*}
FOLLOW(S) = {$, *, a}

接下来，我们可以开始构造该文法的LR(1)项目集规范族。

I0:
S' -> .S [$]
S -> .S S [$]
S -> .S S * [$]
S -> .a [$]

I1:
S' -> S. [$]

I2:
S -> S. S [$, *]
S -> S. S * [$, *]

I3:
S -> S S. [$, *]
S -> S S. * [$, *]

I4:
S -> a. [$, *]

现在，我们可以根据项目集的转换关系来构造LR(1)项集族。

LR(1) 项集族
---------------------
I0:
S' -> .S [$]
S -> .S S [$]
S -> .S S * [$]
S -> .a [$]

I1:
S' -> S. [$]

I2:
S -> S. S [$, *]

I3:
S -> S S. [$, *]
S -> S S. * [$, *]

I4:
S -> a. [$, *]

LALR(1) 项集族
------------------------
I0:
S' -> .S [$]
S -> .S S [$]
S -> .S S * [$]
S -> .a [$]

I1:
S' -> S. [$]

I2:
S -> S. S [$, *]

I3:
S -> S S. [$, *]
S -> S S. * [$, *]

I4:
S -> a. [$, *]

上述项集族就是该文法的规范LR(1)项集族和LALR(1)项集族。