LR(0) 项的规范集合

LR(0) 项是一个产生式 G，其中点位于产生式右侧的某个位置。

LR(0) 项用于指示在解析过程中，在给定点之前已经扫描了多少输入。

在 LR(0) 中，我们将规约节点放置在整行中。

示例

给定文法

添加增广产生式，并在 G 中每个产生式的第一个位置插入 '•' 符号

I0 状态

将增广产生式添加到 I0 状态并计算闭包

I0 = Closure (S` → •S)

将以 S 开头的所有产生式添加到 I0 状态，因为 "•" 后跟非终结符。 因此，I0 状态变为

I0 = S` → •S
       S → •AA

将以 "A" 开头的所有产生式添加到修改后的 I0 状态，因为 "•" 后跟非终结符。 因此，I0 状态变为。

I0= S` → •S
       S → •AA
       A → •aA
       A → •b

I1= Go to (I0, S) = closure (S` → S•) = S` → S•

在此，产生式被规约，因此关闭状态。

I1= S` → S•

I2= Go to (I0, A) = closure (S → A•A)

将以 A 开头的所有产生式添加到 I2 状态，因为 "•" 后跟非终结符。 因此，I2 状态变为

I2 =S→A•A
       A → •aA
       A → •b

Go to (I2,a) = Closure (A → a•A) = (与 I3 相同)

Go to (I2, b) = Closure (A → b•) = (与 I4 相同)

I3= Go to (I0,a) = Closure (A → a•A)

在 I3 中添加以 A 开头的产生式。

A → a•A
A → •aA
A → •b

Go to (I3, a) = Closure (A → a•A) = (与 I3 相同)
Go to (I3, b) = Closure (A → b•) = (与 I4 相同)

I4= Go to (I0, b) = closure (A → b•) = A → b•
I5= Go to (I2, A) = Closure (S → AA•) = SA → A•
I6= Go to (I3, A) = Closure (A → aA•) = A → aA•

绘制 DFA

DFA 包含 7 个状态 I0 到 I6。

LR(0) 表

• 如果一个状态通过终结符到达另一个状态，则对应于移入操作。
• 如果一个状态通过变量到达另一个状态，则对应于转移操作。
• 如果一个状态在特定行中包含最终项，则完整地写入规约节点。

说明

• I0 在 S 上到达 I1，因此将其写为 1。
• I0 在 A 上到达 I2，因此将其写为 2。
• I2 在 A 上到达 I5，因此将其写为 5。
• I3 在 A 上到达 I6，因此将其写为 6。
• I0、I2 和 I3 在 a 上到达 I3，因此将其写为 S3，表示移入 3。
• I0、I2 和 I3 在 b 上到达 I4，因此将其写为 S4，表示移入 4。
• I4、I5 和 I6 所有状态都包含最终项，因为它们在最右端包含 •。 因此，将产生式评定为产生式编号。

产生式编号如下

• I1 包含最终项，该项驱动 (S` → S•)，因此 action {I1, $} = Accept。
• I4 包含最终项，该项驱动 A → b•，并且该产生式对应于产生式编号 3，因此在整行中将其写为 r3。
• I5 包含最终项，该项驱动 S → AA•，并且该产生式对应于产生式编号 1，因此在整行中将其写为 r1。
• I6 包含最终项，该项驱动 A → aA•，并且该产生式对应于产生式编号 2，因此在整行中将其写为 r2。