什么是 LR(2) 解析器？它与 LR(1) 解析器有何不同？

Question

我熟悉 LR(1) 解析器，它们通常在传统编译器课程中教授。我知道存在 LR(2) 解析器，但我以前从未见过构建过的解析器。

LR(2) 解析器是如何构造的？它与 LR(1) 解析器有何不同？

Answer 1

在许多方面，LR(2) 解析器的工作方式类似于 LR(1) 解析器。它反向追踪最右边的派生，维护堆栈，在堆栈上执行移位和减少操作，具有由 LR 项集组成的状态等。 但是，有一些主要区别：

• LR(2) 解析器为每个 LR 项目维护两个前瞻标记，而不是像 LR(1) 中那样只维护一个前瞻标记。
• 移位如何工作的规则不同于 LR(1) 解析器的标准规则，并且需要一个额外的前瞻概念，称为点前瞻，LR(1) 解析器中不存在。
• LR(2) 解析器的动作表的宽度远大于 LR(1) 解析器的动作表的宽度，但与直觉相反，goto 表的宽度相同。

为了说明这是如何工作的，让我们举一个 LR(2) 语法的例子。（此语法源自@rici 对早先问题的出色回答中提到的语法）。

? RS | 电阻

? abT

? | | | | ?

为了为这个文法构建我们的 LR(2) 解析器，我们将像往常一样开始用 S' ? :

S' ? 秒

? RS | 电阻

? abT

? | | | | ?

现在，我们开始生成配置集。与 LR(1) 解析器一样，我们从产生式 S' ? S. 这在这里显示：

(1)
    S' -> .S  [$$]

请注意，这里的前瞻是 $$，表示“流结束”标记的两个副本。在传统的 LR(1)（或 SLR(1) 或 LALR(1)）解析器中，我们会先行查看 $，只是流结束标记的一个副本。

我们现在开始扩展这个配置集中的其他项目。因为我们有作品 S ? RS 和 S ? R，我们添加这些项目：

(1)
    S' -> .S  [$$]
    S  -> .R  [$$]  // New
    S  -> .RS [$$]  // New

现在，让我们开始追查接下来会发生什么。就像在 LR(1) 解析器中一样，由于这里的非终结符 R 之前有点，我们需要将它们展开。正如在 LR(1) 解析中一样，当我们这样做时，我们需要确定要使用的前瞻。我们将首先扩展该S -> .R [$$]项目，如下所示：

(1)
    S' -> .S   [$$]
    S  -> .R   [$$]
    S  -> .RS  [$$]
    R  -> .abT [$$]  // New

接下来，让我们扩展S -> .RS [$$]选项。这是一个有趣的案例。我们需要确定这里发现的 R 产生式的前瞻是什么。在 LR(1) 解析器中，这是通过查看产生式剩余部分的 FIRST 集找到的。在LR(2)解析器中，因为我们有两个lookahead的tokens，所以我们要查看FIRST ₂ set，这是FIRST set的泛化，列出了可以出现在产生式前面的长度为2的字符串，而不是可以出现在那里的长度为 1 的字符串。在我们的例子中，FIRST ₂ (S) = {ab}（你明白为什么吗？），所以我们有以下内容：

(1)
    S' -> .S   [$$]
    S  -> .R   [$$]
    S  -> .RS  [$$]
    R  -> .abT [$$]
    R  -> .abT [ab]  // New

至此，我们已经完成了第一个配置集的扩展。现在是时候考虑如果我们接下来看到不同的角色我们会怎么做。幸运的是，在这种情况下这很容易，因为此语法生成的任何字符串的第一个字符都必须是a. 所以让我们看看如果我们遇到一个会发生什么a：

(2)
    R  -> a.bT [$$]
    R  -> a.bT [ab]

目前看来还好。现在如果我们在b这里看到 a 会发生什么？这将带我们到这个地方：

(3)
    R  -> ab.T [$$]
    R  -> ab.T [ab]

这里有两个 LR(2) 项在非终结符之前有点，因此我们需要将它们展开。让我们从扩展这些 for 开始R -> ab.T [$$]，给出以下内容：

(3)
    R  -> ab.T [$$]
    R  -> ab.T [ab]
    T  -> .aT  [$$]  // New
    T  -> .c   [$$]  // New
    T  -> .    [$$]  // New

接下来，我们将扩大生产R -> ab.T [ab]：

(3)
    R  -> ab.T [$$]
    R  -> ab.T [ab]
    T  -> .aT  [$$]
    T  -> .c   [$$]
    T  -> .    [$$]
    T  -> .aT  [ab] // New
    T  -> .c   [ab] // New
    T  -> .    [ab] // New

这填写了这个配置集。这是我们第一次发现一些完整的reduce 项（这里T -> .有两个不同的前瞻）。我们这里也有一些轮班项目。所以我们不得不问 - 我们这里有转移/减少冲突还是减少/减少冲突？

让我们从减少/减少冲突开始。与 LR(1) 解析的情况一样，当有两个不同的缩减项（末尾带有点的项）具有相同的前瞻时，我们会遇到缩减/缩减冲突。在这里，我们有两个不同的减少项，但它们有不同的前瞻。这意味着我们在减少/减少方面很好。

现在，有趣的案例。我们这里有任何转变/减少冲突吗？这是与 LR(1) 解析有所不同的地方。与 LR(1) 解析中的情况一样，我们查看集合中的所有移位项（终端前带有点的项）和集合中的所有归约项（末尾带有点的项）。我们正在查看是否存在任何冲突：

    T  -> .aT  [$$] // Shift
    T  -> .c   [$$] // Shift
    T  -> .    [$$] // Reduce
    T  -> .aT  [ab] // Shift
    T  -> .c   [ab] // Shift
    T  -> .    [ab] // Reduce

不过，问题是这里的 shift/reduce 冲突是什么样的。在 LR(2) 解析器中，我们有两个前瞻标记，我们基于这些标记来决定是移动还是减少。在减少项的情况下，很容易看出前瞻的两个标记将导致我们减少 - 括号中的两个字符前瞻。另一方面，考虑班次项目T -> .c [ab]。我们将在其中转移的两个字符的前瞻是什么？在 LR(1) 解析器的情况下，我们只会说“哦，点在 之前c，所以我们移到 上c”，但这还不够。相反，我们会说与这个转移项目相关的前瞻是ca，c来自生产本身和a来自项目的第一个字符'

类似地，考虑 shift item T -> .aT [$$]。我们需要两个前瞻字符，我们可以很容易地看到其中一个（a点之后）。为了得到第二个，我们必须看看什么T是能够生产的。T有三种产生式：一种用?代替T，一种用aT代替T，一种用c代替T。这意味着可以从 T 派生的任何字符串以a或开头c，或者是空字符串。结果，T -> .aT [$$]当看到acor aa（我们从 a 和 ca$得到什么）或 on （如果我们使用产生式 T 得到什么？正常前瞻中的 $ 字符。

更一般地，遵循相同的一般程序——使用点后面的终结符、项的先行集合中的终结符，以及可以出现在可从未来的非终结符派生的任何字符串前面的字符——我们可以计算我们用来确定何时转移的两个字符的前瞻。特别是，我们留下了这个：

(3)
    R  -> ab.T [$$]
    R  -> ab.T [ab]
    T  -> .aT  [$$] // Shift  on aa, ac, a$
    T  -> .c   [$$] // Shift  on c$
    T  -> .    [$$] // Reduce on $$
    T  -> .aT  [ab] // Shift  on aa, ac
    T  -> .c   [ab] // Shift  on ca
    T  -> .    [ab] // Reduce on ab

幸运的是，这里没有 shift/reduce 冲突，因为每个两个字符的前瞻告诉我们做一些不同的事情。

越过点来确定何时移动是 LR(2) 解析的新内容，它出现在 LR(k > 1) 解析中，而不是 LR(1) 解析中。在 LR(1) 解析中，我们只需要查看点之后的终端。在 LR(2) 解析中，由于我们需要更多字符来确定要执行的操作，因此我们必须为每个移位项计算二次点前瞻。具体来说，dot lookahead 确定如下：

在生产 A ? ?.t? [?]，其中 t 是终端，点先行是所有长度为 2 的字符串的集合，这些字符串可以出现在可从 t?? 派生的字符串的开头。换句话说，生产 A ? ?.t? [?] 的点前瞻等于 FIRST ₂ (t??)。

考虑到所有这些，我们可以构建完整的 LR(2) 解析器并描述与每个状态相关的操作。整个 LR(2) 解析器如下所示：

(1)
    S' -> .S   [$$]  // Go to 10
    S  -> .R   [$$]  // Go to 8
    S  -> .RS  [$$]  // Go to 8
    R  -> .abT [$$]  // Shift  on ab, go to (2)
    R  -> .abT [ab]  // Shift  on ab, go to (2)

(2)
    R  -> a.bT [$$]  // Shift  on ba, bc, b$, go to (3)
    R  -> a.bT [ab]  // Shift  on ba, bc,     go to (3)

(3)
    R  -> ab.T [$$] // Go to 7
    R  -> ab.T [ab] // Go to 7
    T  -> .aT  [$$] // Shift  on aa, ac, a$, go to (4)
    T  -> .c   [$$] // Shift  on c$,         go to (5)
    T  -> .    [$$] // Reduce on $$
    T  -> .aT  [ab] // Shift  on aa, ac,     go to (4)
    T  -> .c   [ab] // Shift  on ca,         go to (5)
    T  -> .    [ab] // Reduce on ab

(4)
    T  -> a.T  [$$] // Go to 6
    T  -> a.T  [ab] // Go to 6
    T  -> .    [$$] // Reduce on $$
    T  -> .aT  [$$] // Shift  on aa, ac, a$, go to (4)
    T  -> .c   [$$] // Shift  on c$,         go to (5)
    T  -> .    [ab] // Reduce on ab
    T  -> .aT  [ab] // Shift  on aa, ac,     go to (4)
    T  -> .c   [ab] // Shift  on ca,         go to (5)

(5)
    T  -> c.   [$$] // Reduce on $$
    T  -> c.   [ab] // Reduce on ab

(6)
    T  -> aT.  [$$] // Reduce on $$ 
    T  -> aT.  [ab] // Reduce on ab

(7)
    R  -> abT. [$$] // Reduce on $$
    R  -> abT. [ab] // Reduce on ab

(8)
    S  -> R.   [$$] // Reduce on $$
    S  -> R.S  [$$] // Go to 9
    S  -> .RS  [$$] // Go to 8
    S  -> .R   [$$] // Go to 8
    R  -> .abT [$$] // Shift  on ab, go to (2)
    R  -> .abT [ab] // Shift  on ab, go to (2)

(9)
    S  -> RS.  [$$] // Reduce on $$

(10)
    S' -> S.   [$$] // Accept on $$

所以现在我们有了这个语法的 LR(2) 解析器。现在剩下要做的就是将其编码为一个动作和跳转表，就像我们为 LR(1) 解析器所做的那样。

如您所料，LR(2) 解析器的动作表与 LR(1) 解析器的动作表的不同之处在于它由两个字符而不是一个字符给出的前瞻键控。这意味着 LR(2) 解析器的动作表将比 LR(1) 解析器大得多。这是这里的样子：

 state | aa | ab | ac | a$ | ba | bb | bc | b$ | ca | cb | cc | c$ | $$ 
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   1   |    | S  |    |    |    |    |    |    |    |    |    |    |
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   2   |    |    |    |    | S  |    | S  | S  |    |    |    |    |
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   3   | S  | R  | S  | S  |    |    |    |    | S  |    |    | S  | R
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   4   | S  | R  | S  | S  |    |    |    |    | S  |    |    | S  | R
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   5   |    | R  |    |    |    |    |    |    |    |    |    |    | R
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   6   |    | R  |    |    |    |    |    |    |    |    |    |    | R
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   7   |    | R  |    |    |    |    |    |    |    |    |    |    | R
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   8   |    | S  |    |    |    |    |    |    |    |    |    |    | R
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   9   |    |    |    |    |    |    |    |    |    |    |    |    | R
 ------+----+----+----+----+----+----+----+----+----+----+----+----+----
   10  |    |    |    |    |    |    |    |    |    |    |    |    | A

如您所见，这里的每个条目只是说明是移动还是减少。在实践中，每个reduce 项都会被标记为您实际为哪个产品进行了reduce，但是，嗯，我懒得把它打出来。

在 LR(1) 解析表中，您通常会将这个表与“goto”表结合起来，说明在看到每个符号后要去哪里。这是由于一个偶然的巧合。在 LR(1) 解析器中，前瞻的大小为 1，这恰好与 goto 表说明您在看到下一个字符后应该转换到的位置这一事实一致。在 LR(2) 解析器中，是否进行移位或减少的决定取决于前瞻的两个字符，但在读取输入的另一个字符后选择下一步的位置仅取决于单个字符。也就是说，即使您有两个前瞻标记来决定是否执行，您一次只能移动一个字符。这意味着 LR(2) 解析器的 goto 表看起来很像 LR(0) 或 LR(1) 解析器的 goto 表，如下所示：

 state |  a  |  b  |  c  |  $  |  S  |  R  |  T
-------+-----+-----+-----+-----+-----+-----+-----
   1   |  2  |     |     |     |  10 |  8  |
-------+-----+-----+-----+-----+-----+-----+-----
   2   |     |  3  |     |     |     |     |
-------+-----+-----+-----+-----+-----+-----+-----
   3   |  4  |     |  5  |     |     |     |  7
-------+-----+-----+-----+-----+-----+-----+-----
   4   |  4  |     |  5  |     |     |     |  6
-------+-----+-----+-----+-----+-----+-----+-----
   5   |     |     |     |     |     |     |
-------+-----+-----+-----+-----+-----+-----+-----
   6   |     |     |     |     |     |     |
-------+-----+-----+-----+-----+-----+-----+-----
   7   |     |     |     |     |     |     |
-------+-----+-----+-----+-----+-----+-----+-----
   8   |  2  |     |     |     |  9  |  8  |
-------+-----+-----+-----+-----+-----+-----+-----
   9   |     |     |     |     |     |     |
-------+-----+-----+-----+-----+-----+-----+-----
   10  |     |     |     |     |     |     |

所以，总结一下：

• LR(2) 解析器为每个 LR 项使用两个前瞻标记。这意味着我们需要使用 FIRST ₂集而不是 FIRST 集，并且在确定是移动还是减少时引入了一些新的复杂性。
• LR(2) 解析有dot lookahead。对于每个移位项目，我们使用 FIRST ₂集来确定哪些字符可以合法地跟随我们所在的点，并在其中任何一个上移位。
• LR(2) 操作表以字符对而不是单个字符为键，但转到表仍以字符为键。

有趣的是，一旦您知道如何构建 LR(2) 解析器，您就可以概括为任何 k 构建 LR(k) 解析器的想法？2. 特别是，这里出现的所有“新惊喜”与您将在 k 值越来越大时看到的相同。

在实践中，LR(2) 解析器很少使用，因为它们的动作表的大小以及由于增加的前瞻，它们通常比 LR(1) 解析器具有更多的状态这一事实。但恕我直言，看看它们如何工作仍然是值得的。它让您更普遍地了解 LR 解析是如何工作的。

希望这可以帮助！

_{非常感谢@AProgrammer 在 cs.stackexchange.com 上关于 dot lookaheads 与 item lookaheads的回答，这帮助我更好地了解了 dot lookaheads 的功能及其目的是什么！}

_{如果您想阅读有关 LR(k) 解析的原始论文，其中详细说明了 LR(k) 解析的完整规则，请查看 Don Knuth 的“从左到右的语言翻译”。}