文章目录
  1. 1. 造表
    1. 1.1. State 0
    2. 1.2. State 1
    3. 1.3. State 2
    4. 1.4. State 3
    5. 1.5. State 4
    6. 1.6. State 5
  2. 2. 结果

要高效地执行 LR(1) 语法分析,就需要根据语法产生式,构建一个 LR 分析表。下面就是通过基本的语法,构建 LR(1) 分析表的一个例子,操作思路做到了尽可能细致。希望读了之后,妈妈就不用操心我不会造表啦。

以这个文法为例:

A → A + B
A → a
B → b

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

S → A

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

造表

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

  • 它从哪里来?
  • 它的闭包是什么?
  • 它需要归约吗?
  • 它需要转移吗?

就能得到正确的结果。这样看起来还是有些抽象,希望下面的演示能帮助理解吧。

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 能去哪里吧。没有以 · 结束的产生式,也就是不需要归约了。不过 Bb 前都有 ·,这也就意味着有两个转移状态。约定 B 转移到 State 4b 转移到 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 转移表。

结果

sN 代表移入,实际上就是移入新符号并进入状态 N。
rN 代表归约。这里把 N 与产生式的关系约定如下:

  1. S → A
  2. A → A + B
  3. A → a
  4. B → b

goto N 代表转移,也就是转移到状态 N。

a b + $ A B
0 s2 goto 1
1 s3 r1
2 r3 r3
3 s5 goto 4
4 r2 r2
5 r4 r4

然后就可以用上面这张表,执行 LR(1) 语法分析啦。

文章目录
  1. 1. 造表
    1. 1.1. State 0
    2. 1.2. State 1
    3. 1.3. State 2
    4. 1.4. State 3
    5. 1.5. State 4
    6. 1.6. State 5
  2. 2. 结果