证明以下文法是 LR (1) S → A a |b A c |B c | b B a A → d B → d

解决方案

Step1 - 构建增强语法

(0) S′ → S

(1) S → A a

(2) S → b A c

(3) S → B c

(4) S → b B a

(5) A → d

(6) B→d

Step2 - 找到闭包 去。构造一组 LR (1) 项。这里所有的框都代表新的状态。

LR(1)解析表

因此，LR (1) Parsing Table 没有多个条目。语法是 LR (1)。

LR(1)或Canonical LR Parsing Table的构造

输入- 增强语法 G'。

输出- 规范 LR (1) 解析表

方法

填充“移位” Entries(s)- 应用构造 CLR 解析表的规则 (2a)。

考虑 I ₃ = goto(I ₀ , c)

∴ 动作[0, c] = shift 3

∴ 将 s3 写在行状态 0 和列 c 的前面。

同样，考虑另一个条目。

即，I ₇ = goto(I2, d)

∴ 动作[2, d] = shift 7

∴ 在第 2 行和第 d 列前面写上 s7。类似地，将其他班次条目填充到动作表中。

填写“减少”条目(r)

应用构造CLR解析表的规则(2b)。考虑形式 A → α ∙ , a

例如，考虑

我₄ = 转到（我₀， d）

C → d ∙, c | d

这里, C → d ∙, c | d 的形式为 A → α ∙ , a。因此，将 Action [4, c] 和 Action [4, d] 设置为 r3。

由于 C → d 是给定问题中的生产编号 3。

∴ 在行状态 4 和列 c 和 d 的前面写上 r3。

因为 c, d 在产生式 C → d ∙ , c | 中向前看符号 d。

考虑另一个例子

我₉ = 转到（我₉， C）

C → c C ∙, $

由于 C → c C 是给定问题中的生产编号 (2)。

∴ 在行状态 9 和列 $前面写 r2，因为 $是附加到产生式的前瞻符号。

∴ 动作 [9, $] = r2

同样，将归约的所有条目填充到解析表中。

填写goto条目

在 goto 中，仅按列显示非终端，

例如

我₈ = 转到（我₃， C）

∴ 动作 [3, C] = 8

即，在第 3 行和第 C 列前面写 8。

填写“接受”条目

应用 CLR 解析表的规则 (2c)

找出产生形式 S′ → S ∙, $的状态

∴ 状态 I ₁

∴ 在Row state 1 & 前面写accept $列。