证明以下文法是 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 3 = goto(I 0 , c)
∴ 动作[0, c] = shift 3
∴ 将 s3 写在行状态 0 和列 c 的前面。
同样，考虑另一个条目。
即，I 7 = goto(I2, d)
∴ 动作[2, d] = shift 7
∴ 在第 2 行和第 d 列前面写上 s7。类似地，将其他班次条目填充到动作表中。
填写“减少”条目(r)
应用构造CLR解析表的规则(2b)。考虑形式 A → α ∙ , a
例如，考虑
我4 = 转到（我0， 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。
考虑另一个例子
我9 = 转到（我9， C）
C → c C ∙, $
由于 C → c C 是给定问题中的生产编号 (2)。
∴ 在行状态 9 和列 $前面写 r2，因为 $是附加到产生式的前瞻符号。
∴ 动作 [9, $] = r2
同样，将归约的所有条目填充到解析表中。
填写goto条目
在 goto 中，仅按列显示非终端，
例如
我8 = 转到（我3， C）
∴ 动作 [3, C] = 8
即，在第 3 行和第 C 列前面写 8。
填写“接受”条目
应用 CLR 解析表的规则 (2c)
找出产生形式 S′ → S ∙, $的状态
∴ 状态 I 1
∴ 在Row state 1 & 前面写accept $列。
以上是 证明以下文法是 LR (1) S → A a |b A c |B c | b B a A → d B → d 的全部内容， 来源链接： utcz.com/z/363391.html
