证明以下文法是 LR(1) 的\nS → A a |b A c |B c | b B a\nA → d\nB → d

解决方案

步骤1 - 构造扩充文法

(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

步骤2 - 查找闭包和 goto。构造 LR(1) 项目集。这里所有框都表示新状态。

LR(1) 分析表

因此，LR(1) 分析表没有多个条目。文法是 LR(1) 的。

LR(1) 或规范 LR 分析表的构造

输入 - 扩充文法 G’。

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

方法

填充“移进”条目 (s) - 应用 CLR 分析表构造的规则 (2a)。

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

∴ Action[0, c] = shift 3

∴ 在第 0 行和第 c 列前面写入 s3。

类似地，考虑另一个条目。

即，I₇ = goto(I2, d)

∴ Action[2, d] = shift 7

∴ 在第 2 行和第 d 列前面写入 s7。类似地，移进的其他条目填充到 Action 表中。

填充“归约”条目 (r)

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

例如，考虑

I₄ = goto(I₀, 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 中是前瞻符号。

考虑另一个例子

I₉ = goto(I₉, C)

C → c C ∙, $

因为 C → c C 是给定问题中的产生式 (2)。

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

∴ Action[9, $] = r2

类似地，将所有归约条目填充到分析表中。

goto 条目的填充

在 goto 中，只有非终结符以列的形式出现。

例如

I₈ = goto(I₃, C)

∴ Action[3, C] = 8

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

“接受”条目的填充

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

查找包含形如 S′ → S ∙, $ 的产生式的状态

∴ 它是状态 I₁

∴ 在第 1 行和第 $ 列前面写入 accept。

Ginni

更新于: 2021-11-02

6K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始