LR(0) 项目集族详解:文法分析方法
给定拓展后的文法 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) 项目集族的构造过程如下:
- 
构造初始项目集 $I_0={S' \rightarrow \cdot S}$,其中 $S'$ 是增广文法的起始符号,$S$ 是文法符号。
 - 
对于每个项目集 $I_i$,以及每个 $I_i$ 中的项目 $A \rightarrow \alpha\cdot B\beta$,对于文法中的每个产生式 $B \rightarrow \gamma$,构造新的项目 $B \rightarrow \cdot\gamma$,加入到 $I_i$ 中。
 - 
对于每个项目集 $I_i$,以及每个 $I_i$ 中的项目 $A \rightarrow \alpha\cdot B\beta$,对于文法中的每个终结符号 $a$,如果存在 $B \rightarrow \gamma$ 且 $a$ 是 $FIRST(\beta)$ 中的一个元素,则构造新的项目 $B \rightarrow \cdot\gamma$,加入到 $I_i$ 中。
 - 
重复步骤 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'$ 表示增广文法的起始符号,点 '.' 表示当前的分析位置。
原文地址: https://www.cveoy.top/t/topic/oneb 著作权归作者所有。请勿转载和采集!