什么是 LR(2) 解析器？它与 LR(1) 解析器有何不同？
What is an LR(2) parser? How does it differ from an LR(1) parser?
我熟悉 LR(1) 解析器，通常在传统编译器课程中讲授。我知道存在 LR(2) 解析器，但我以前从未见过构造的解析器。
LR(2) 解析器是如何构建的？它与 LR(1) 解析器有何不同？
在许多方面，LR(2) 解析器的工作方式与 LR(1) 解析器类似。它反向追踪最右推导，维护堆栈，在堆栈上执行移位和减少操作，具有由 LR 项集组成的状态等。但是，有几个主要区别：
- LR(2) 解析器为每个 LR 项维护两个先行标记，而不是像 LR(1) 中那样仅保留一个先行标记。
- 移位工作的规则不同于 LR(1) 解析器的标准规则，并且需要一个额外的先行概念，称为 点先行 LR(1) 中不存在) 解析器。
- LR(2) 解析器的动作 table 的宽度比 LR(1) 解析器的宽度大得多，但违反直觉的是，goto table 的宽度相同.
为了激发其工作原理，让我们举一个 LR(2) 文法的例子。 （此语法源自 @rici's excellent answer to this earlier question 中提到的一种语法）。
S → RS | R
R → abT
T → aT | c | ε
要为此文法构建我们的 LR(2) 解析器，我们将像往常一样，首先使用 S' → S:
形式的产生式扩充文法
S' → S
S → RS | R
R → abT
T → aT | c | ε
现在，我们开始生成配置集。与 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) 解析器中，这是通过查看产生式剩余部分的第一组来找到的。在 LR(2) 解析器中，因为我们有两个先行标记，所以我们必须查看 FIRST2 set，这是泛化FIRST 集合的列表列出了可以出现在产生式前面的长度为 2 的字符串，而不是可以出现在那里的长度为 1 的字符串。在我们的例子中，FIRST2(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 会发生什么？那将把我们带到这个地方：
(3)
R -> ab.T [$$]
R -> ab.T [ab]
这里有两个 LR(2) 项在非终结符前有点，所以我们需要将它们展开。让我们首先为 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 -> . 有两个不同的 lookaheads）。我们这里也有一些轮班项目。所以我们不得不问 - 我们这里有 shift/reduce 冲突还是 reduce/reduce 冲突？
让我们从 reduce/reduce 冲突开始。与 LR(1) 解析中的情况一样，当有两个不同的归约项（末尾带点的项）具有相同的先行时，我们会遇到 reduce/reduce 冲突。在这里，我们有两个不同的 reduce 项，但它们有不同的 lookaheads。这意味着我们在 reduce/reduce 前线很好。
现在，有趣的案例。我们这里有 shift/reduce 冲突吗？这是与 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 来自项目前瞻的第一个字符。
同样，考虑班次项目T -> .aT [$$]。我们需要两个向前看的字符，我们可以很容易地看到其中一个（点后面的 a）。要获得第二个，我们必须看看 T 能够产生什么。 T 有三种产生式：一种用 ε 代替 T，一种用 aT 代替 T，一种用 c 代替 T。这意味着可以从 T 派生的任何字符串都以 a 或 c 开头，或者是空字符串。结果，项目 T -> .aT [$$] 告诉我们在看到 ac 或 aa（我们从 a 和 c 得到的）或 a$ 时移动（如果我们使用产生式 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 冲突，因为每个两个字符的先行告诉我们做一些不同的事情。
Looking past the dot to determine when to shift is new to LR(2) parsing that appears in LR(k > 1) parsing 但不是 LR(1) 解析。在 LR(1) 解析中，我们只需要查看点后的终端。在 LR(2) 解析中，由于我们需要更多的字符来确定要做什么，我们必须为每个班次项计算一个次要的 dot lookahead .具体来说，dot lookahead 的确定方式如下：
In a production A → α.tω [γ], where t is a terminal, the dot lookahead is the set of all strings of length 2 that can appear at the start of a string derivable from tωγ. Stated differently, a production A → α.tω [γ] has dot lookahead equal to FIRST2(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) 解析器。现在剩下要做的就是将其编码为一个动作并转到 table，就像我们为 LR(1) 解析器所做的那样。
如您所料，LR(2) 解析器的操作 table 与 LR(1) 解析器的操作 table 的不同之处在于它由以下提供的先行键控两个字符而不是一个字符。这意味着 LR(2) 解析器的操作 table 比 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 项目都会被标记为您实际要为哪个产品进行 reduction，但是，嗯，我懒得打出来了。
在 LR(1) 解析 table 中，您通常会将此 table 与“goto”table 结合使用，表示在看到每个符号后要去哪里。这是由于一个偶然的巧合。在 LR(1) 解析器中，前瞻的大小为 1，这恰好与 goto table 表示在看到下一个字符后应该过渡到的位置这一事实一致。在 LR(2) 解析器中，是否移动或减少的决定取决于前瞻的两个字符，但在读取输入的另一个字符后选择下一步去哪里仅取决于单个字符。也就是说，即使您有两个先行标记来决定是否执行操作，您一次也只能移动一个字符。这意味着 LR(2) 解析器的 goto table 看起来很像 LR(0) 或 LR(1) 解析器的 goto table，如下所示：
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 项使用两个先行标记。这意味着我们需要使用 FIRST2 集而不是 FIRST 集，并且在确定是平移还是减少时引入了一些新的复杂性。
- LR(2) 解析具有 点先行 。对于每个班次项目，我们使用 FIRST2 集来确定哪些字符可以合法地跟随我们所在位置的点，并在其中任何一个上班次。
- LR(2) 操作 table 由字符对而不是单个字符键入，但 goto table 仍然由字符键入。
有趣的是，一旦你知道如何构建 LR(2) 解析器，你就可以概括为任何 k ≥ 2 构建 LR(k) 解析器的想法。特别是，出现的所有“新惊喜”这些是您将看到的 k 值越来越大的相同值。
在实践中，LR(2) 解析器很少被使用，因为它们的动作 tables 的大小以及它们通常比 LR(1) 解析器具有更多状态的事实，因为增加了前瞻。但恕我直言，看看它们是如何工作的仍然是值得的。它让您了解 LR 解析如何更普遍地工作。
希望对您有所帮助！
非常感谢 @AProgrammer's answer on cs.stackexchange.com 关于点先行与项目先行的对比，这帮助我更好地了解了点先行的功能及其目的！
如果您想阅读有关 LR(k) 解析的原始论文，其中详细说明了 LR(k) 解析的完整规则，请查看“On the Translation of从左到右的语言”，作者：Don Knuth。
我熟悉 LR(1) 解析器，通常在传统编译器课程中讲授。我知道存在 LR(2) 解析器，但我以前从未见过构造的解析器。
LR(2) 解析器是如何构建的？它与 LR(1) 解析器有何不同？
在许多方面，LR(2) 解析器的工作方式与 LR(1) 解析器类似。它反向追踪最右推导，维护堆栈，在堆栈上执行移位和减少操作，具有由 LR 项集组成的状态等。但是，有几个主要区别：
- LR(2) 解析器为每个 LR 项维护两个先行标记，而不是像 LR(1) 中那样仅保留一个先行标记。
- 移位工作的规则不同于 LR(1) 解析器的标准规则，并且需要一个额外的先行概念，称为 点先行 LR(1) 中不存在) 解析器。
- LR(2) 解析器的动作 table 的宽度比 LR(1) 解析器的宽度大得多，但违反直觉的是，goto table 的宽度相同.
为了激发其工作原理，让我们举一个 LR(2) 文法的例子。 （此语法源自 @rici's excellent answer to this earlier question 中提到的一种语法）。
S → RS | R
R → abT
T → aT | c | ε
要为此文法构建我们的 LR(2) 解析器，我们将像往常一样，首先使用 S' → S:
形式的产生式扩充文法S' → S
S → RS | R
R → abT
T → aT | c | ε
现在，我们开始生成配置集。与 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) 解析器中，这是通过查看产生式剩余部分的第一组来找到的。在 LR(2) 解析器中，因为我们有两个先行标记，所以我们必须查看 FIRST2 set，这是泛化FIRST 集合的列表列出了可以出现在产生式前面的长度为 2 的字符串，而不是可以出现在那里的长度为 1 的字符串。在我们的例子中，FIRST2(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 会发生什么？那将把我们带到这个地方：
(3)
R -> ab.T [$$]
R -> ab.T [ab]
这里有两个 LR(2) 项在非终结符前有点，所以我们需要将它们展开。让我们首先为 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 -> . 有两个不同的 lookaheads）。我们这里也有一些轮班项目。所以我们不得不问 - 我们这里有 shift/reduce 冲突还是 reduce/reduce 冲突？
让我们从 reduce/reduce 冲突开始。与 LR(1) 解析中的情况一样，当有两个不同的归约项（末尾带点的项）具有相同的先行时，我们会遇到 reduce/reduce 冲突。在这里，我们有两个不同的 reduce 项，但它们有不同的 lookaheads。这意味着我们在 reduce/reduce 前线很好。
现在，有趣的案例。我们这里有 shift/reduce 冲突吗？这是与 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 来自项目前瞻的第一个字符。
同样，考虑班次项目T -> .aT [$$]。我们需要两个向前看的字符，我们可以很容易地看到其中一个（点后面的 a）。要获得第二个，我们必须看看 T 能够产生什么。 T 有三种产生式：一种用 ε 代替 T，一种用 aT 代替 T，一种用 c 代替 T。这意味着可以从 T 派生的任何字符串都以 a 或 c 开头，或者是空字符串。结果，项目 T -> .aT [$$] 告诉我们在看到 ac 或 aa（我们从 a 和 c 得到的）或 a$ 时移动（如果我们使用产生式 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 冲突，因为每个两个字符的先行告诉我们做一些不同的事情。
Looking past the dot to determine when to shift is new to LR(2) parsing that appears in LR(k > 1) parsing 但不是 LR(1) 解析。在 LR(1) 解析中，我们只需要查看点后的终端。在 LR(2) 解析中，由于我们需要更多的字符来确定要做什么，我们必须为每个班次项计算一个次要的 dot lookahead .具体来说，dot lookahead 的确定方式如下：
In a production A → α.tω [γ], where t is a terminal, the dot lookahead is the set of all strings of length 2 that can appear at the start of a string derivable from tωγ. Stated differently, a production A → α.tω [γ] has dot lookahead equal to FIRST2(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) 解析器。现在剩下要做的就是将其编码为一个动作并转到 table，就像我们为 LR(1) 解析器所做的那样。
如您所料，LR(2) 解析器的操作 table 与 LR(1) 解析器的操作 table 的不同之处在于它由以下提供的先行键控两个字符而不是一个字符。这意味着 LR(2) 解析器的操作 table 比 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 项目都会被标记为您实际要为哪个产品进行 reduction，但是，嗯，我懒得打出来了。
在 LR(1) 解析 table 中，您通常会将此 table 与“goto”table 结合使用，表示在看到每个符号后要去哪里。这是由于一个偶然的巧合。在 LR(1) 解析器中，前瞻的大小为 1，这恰好与 goto table 表示在看到下一个字符后应该过渡到的位置这一事实一致。在 LR(2) 解析器中，是否移动或减少的决定取决于前瞻的两个字符，但在读取输入的另一个字符后选择下一步去哪里仅取决于单个字符。也就是说，即使您有两个先行标记来决定是否执行操作，您一次也只能移动一个字符。这意味着 LR(2) 解析器的 goto table 看起来很像 LR(0) 或 LR(1) 解析器的 goto table，如下所示：
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 项使用两个先行标记。这意味着我们需要使用 FIRST2 集而不是 FIRST 集，并且在确定是平移还是减少时引入了一些新的复杂性。
- LR(2) 解析具有 点先行 。对于每个班次项目，我们使用 FIRST2 集来确定哪些字符可以合法地跟随我们所在位置的点，并在其中任何一个上班次。
- LR(2) 操作 table 由字符对而不是单个字符键入，但 goto table 仍然由字符键入。
有趣的是，一旦你知道如何构建 LR(2) 解析器，你就可以概括为任何 k ≥ 2 构建 LR(k) 解析器的想法。特别是，出现的所有“新惊喜”这些是您将看到的 k 值越来越大的相同值。
在实践中，LR(2) 解析器很少被使用，因为它们的动作 tables 的大小以及它们通常比 LR(1) 解析器具有更多状态的事实，因为增加了前瞻。但恕我直言，看看它们是如何工作的仍然是值得的。它让您了解 LR 解析如何更普遍地工作。
希望对您有所帮助！
非常感谢 @AProgrammer's answer on cs.stackexchange.com 关于点先行与项目先行的对比，这帮助我更好地了解了点先行的功能及其目的！
如果您想阅读有关 LR(k) 解析的原始论文，其中详细说明了 LR(k) 解析的完整规则，请查看“On the Translation of从左到右的语言”，作者：Don Knuth。