【编译原理与技术】LR1分析表的构造

以这个文法为例:

A → A + B
A → a
B → b

这个文法可以推导出 a,a + b,a + b + b 之类的字符串。不过,它也是左递归的(LL 分析中,A → A + B 会使得语法生成树向左下无限生长)。这使得这个语法不适用于 LL 文法分析,只能使用 LR 分析。要构造 LR 表,我们需要先添加一个额外的产生式:

S → A

现在就可以逐步构造 DFA 了。

造表

第一个状态由 S → A 生成。而我们知道,一个 LR(1) 项看起来长这样:[A → α·β, t]。其中 t 是一个终止符(所谓的 lookahead),而黑点则标志着我们现在的位置(已经看见了 α,正在找 β)。
对后面的每一个状态,只要依次考虑以下几点:

  1. 它从哪里来?
  2. 它的闭包是什么?
  3. 它需要归约吗?
  4. 它需要转移吗?

State 0

我们从 [S → ·A, $] 开始,构造这个状态的闭包,也就是加上所有能从这个产生式推出的表项。首先,我们寻找非终止符前是否有个 ·。嗯对了,这个 · 在 A 前面。所以我们就要接着找所有由 A → 推出的产生式,并将它们添加进闭包里。这加上了 [A → ·A + B, $] 和 [A → ·a, $]。够了吗?我们导入了另一个在非终止符前有 · 的项。所以下面我们需要再求一次闭包。这次加入的产生式包括 [A → ·A + B, +] 和 [A → ·a, +]。这次,产生式形如 ·A +,理论上我们要用另一个项来表达它所引入的产生式,不过实际上这个项就是 [A → ·A + B, +],所以不用导入新的项了。

现在 S0 包含的项有:

[S → ·A, $]
[A → ·A + B, $]
[A → ·a, $]
[A → ·A + B, +]
[A → ·a, +]

下一步,就是为这个状态添加转移了。对每个符号 X 后有个 · 的项,都可以从 State 0 过渡到其它状态。看一下这五个,满足条件的是 ·A 和 ·a 吧?把前者转移的状态定义为 State 1,后者定义为 State 2 吧。

State 1

先要看看 State 1 中出现了哪些项吧。我们从 State 0 通过 A 转移到这里,所以我们找出所有 State 0 中在 A 前有 · 的项,这包括:

[S → ·A, $]
[A → ·A + B, $]
[A → ·A + B, +]

因此,将 · 向后推一格,就得到了 State 1 的项了:

[S → A·, $]
[A → A· + B, $]
[A → A· + B, +]

现在再来求闭包,由于没有在非终止符前有 · 的项了,所以这就是全部了(耶!)

最后,从 State 1 出发,可以去哪里呢?由于在这个状态的 [S → A·, $] 项中,· 已经移动到了产生式尾部,因此我们需要应用 S → A 规则来进行归约。除此之外,对每个前面有 · 的状态,都有对应转移出去的状态。这里满足要求的就是 [A → A· + B, +] 这个了。这里我们约定 + 对应转移到 State 3。

State 2

我们是从哪里过来的呢?State 0 中的 a。所以我们从所有 State 0 项中 a 前带有 · 的开始吧。

State 0 的项:

[A → ·a, $]
[A → ·a, +]

将 · 后移得到:

[A → a·, $]
[A → a·, +]

再看看有没有在非终止符前有 · 的项吧。嗯好,没有了,这下不用再求闭包了。下面就是归约了。约定从 + 或 $,归约 A → a。现在没有前面具有 · 的其它符号,因此也不需要再继续了。

State 3

如果我们在 State 1 中遇到 +,那么就会转移到这个 State 3 上来。我们先找出所有符合要求的 State 1 项吧。

State 1 的项:

[A → A· + B, $]
[A → A· + B, +]

把 · 后推得到:

[A → A + ·B, $]
[A → A + ·B, +]

好的,看到了非终结符前的 · 了吗?我们得求闭包了。先从 [A → A + ·B, $] 开始,找出所有 B → xxx 的产生式(注意 lookahead 是 $)。这会加入 [B → ·b, $]。再对 [A → A + ·B, +] 做同样的操作,加入 [B → ·b, +]。现在由于没有前面有 · 的非终结符,因此闭包就完成了。

闭包构造完成后,State 3 的项有这些:

[A → A + ·B, $]
[A → A + ·B, +]
[B → ·b, $]
[B → ·b, +]

最后看看从 State 3 能去哪里吧。没有以 · 结束的产生式,也就是不需要归约了。不过 B 和 b 前都有 ·,这也就意味着有两个转移状态。约定 B 转移到 State 4,b 转移到 State 5。

State 4

我们在 State 3 中遇上 B 时来到这里。列出 State 3 中对应的项:

[A → A + ·B, $]
[A → A + ·B, +]

那么对应的 State 4 项就是:

[A → A + B·, $]
[A → A + B·, +]

嗯,· 前没有非终结符了,这么说也就不用再求闭包了。不过,别忘了归约啊。可以看到我们需要应用的归约规则就只有 A → A + B 这一条。由于 · 前没有非终结符,所以这个状态不需要转移。

State 5

我们在 State 3 中遇上 b 时来到这里。列出 State 3 中对应的项:

[B → ·b, $]
[B → ·b, +]

于是得到对应的 State 5 项:

[B → b·, $]
[B → b·, +]

嗯,这个状态需要归约吗?需要。应用 B → b 规则即可。最后,它有对应的转移状态吗?· 前没有非终结符,所以也不需要转移。

结果

好了。现在该生成的状态都生成了,DFA 就构造完成了。根据我们的结果,填一下最后的 LR 转移表。

S → A
r0:A → A + B
r1:A → a
r2:B → b
状态 a b + $ A B
0 S2 1
1 S3 acc
2 r1 r1
3 S5 4
4 r0 r0
5 r2 r2
全部评论

相关推荐

Yushuu:你的确很厉害,但是有一个小问题:谁问你了?我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务