【编译原理与技术】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
全部评论

相关推荐

11-05 07:29
贵州大学 Java
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务