给定拓展后的文法 G 如下:

1)S'->S 2)S->AS 3)S->ε 4)A->aA 5)A->b

请给出其 LR(0) 项目集族内容:LR(0) 项目是指形如 $A\rightarrow\alpha\cdot\beta$ 的项目,其中 $A$ 是文法符号,$\alpha$ 和 $\beta$ 是文法符号串。

LR(0) 项目集族的构造过程如下:

  1. 构造初始项目集 $I_0={S' \rightarrow \cdot S}$,其中 $S'$ 是增广文法的起始符号,$S$ 是文法符号。

  2. 对于每个项目集 $I_i$,以及每个 $I_i$ 中的项目 $A \rightarrow \alpha\cdot B\beta$,对于文法中的每个产生式 $B \rightarrow \gamma$,构造新的项目 $B \rightarrow \cdot\gamma$,加入到 $I_i$ 中。

  3. 对于每个项目集 $I_i$,以及每个 $I_i$ 中的项目 $A \rightarrow \alpha\cdot B\beta$,对于文法中的每个终结符号 $a$,如果存在 $B \rightarrow \gamma$ 且 $a$ 是 $FIRST(\beta)$ 中的一个元素,则构造新的项目 $B \rightarrow \cdot\gamma$,加入到 $I_i$ 中。

  4. 重复步骤 2 和步骤 3,直到没有新的项目可以加入到项目集中。

最终得到的 LR(0) 项目集族如下:

$I_0$

S' -> .S

$I_1$

S' -> S.
S -> .AS
A -> .aA
A -> .b

$I_2$

S -> A.S
A -> .aA
A -> .b

$I_3$

S -> A.S
A -> a.A
A -> .aA
A -> .b

$I_4$

A -> b.

$I_5$

A -> aA.

$I_6$

S -> AS.
A -> .aA
A -> .b

$I_7$

S -> AS.
A -> a.A
A -> .aA
A -> .b

其中,$S'$ 表示增广文法的起始符号,点 '.' 表示当前的分析位置。

LR(0) 项目集族详解:文法分析方法

原文地址: https://www.cveoy.top/t/topic/oneb 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录