logo标签列表

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

algorithmparsinglr-grammar
6
我熟悉LR(1)解析器，它通常在传统的编译器课程中教授。我知道存在LR(2)解析器，但我从未见过其中一个构造过。
如何构建LR(2)解析器？它与LR(1)解析器有何不同？
1个回答
13
在许多方面，LR（2）解析器的工作方式与LR（1）解析器类似。它以相反的顺序跟踪右侧派生，维护堆栈，在堆栈上执行移位和规约操作，具有由LR项集组成的状态等。然而，有几个主要区别：
  • LR（2）解析器为每个LR项维护两个前瞻标记，而不是像LR（1）中那样只维护一个前瞻标记。
  • 移位操作的规则与LR（1）解析器的标准规则不同，并且需要额外的前瞻概念，称为“点前瞻”，在LR（1）解析器中不存在。
  • 对于LR（2）解析器，动作表的宽度比LR（1）解析器大得多，尽管违反直觉，但goto表的宽度相同。

为了说明这是如何工作的，让我们以LR（2）语法的示例为例。（此语法源自@rici对此先前问题的出色答案。）

S → RS | R

R → abT

T → aT | c | ε

为了为此语法构建LR（2）解析器，我们将像往常一样通过增加形式为S' → S的产生式来扩充语法：

S' → S

S → RS | R

R → abT

T → aT | c | ε

现在，我们开始生成配置集。我们从S' → S开始，就像LR（1）解析器一样。如下所示：

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

注意这里的前瞻符是$$，表示两个“流结束”标记的副本。在传统的LR（1）（或SLR（1），或LALR（1））解析器中，我们会在此处具有$的前瞻，即单个流结束标记的副本，因为在这些解析器中，令牌流以单个$标记结尾。但现在我们处于LR（2）Land中，我们有两个前瞻令牌，因此我们的令牌流将附带两个流结束标记。
我们现在开始扩展此配置集中的其他项。由于我们有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）解析器中，因为我们有两个前瞻标记，所以我们必须查看FIRST2集合，它是FIRST集合的泛化，列出了可以出现在产生式开头的长度为两个的字符串，而不是长度为一个的字符串。在我们的例子中，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

这填满了这个配置集。 这是我们第一次发现一些完整的减少项目（这里，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

问题是这里的移位/规约冲突是什么样子。在LR(2)解析器中，我们有两个令牌的前瞻，基于这两个令牌，我们决定是移位还是规约。对于规约项，很容易看出哪两个令牌的前瞻会导致我们进行规约——它们位于括号中的两个字符。另一方面，考虑移位项T -> .c [ab]。我们需要移位的两个字符的前瞻是什么？在LR(1)解析器的情况下，我们只需说“哦，点在c之前，所以我们在c上移位”，但这在这里是不够的。相反，我们会说与此移位项相关联的前瞻是ca，其中c来自产生式本身，a来自项的前瞻的第一个字符。
类似地，考虑移位项T -> .aT [$$]。我们需要两个字符的前瞻，我们可以很容易地看到其中一个（点后面的a）。要获得第二个，我们必须查看T能够生成的内容。T有三个产生式：一个将T替换为ε，一个将T替换为aT，一个将T替换为c。这意味着可以从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

幸运的是，这里没有移位/归约冲突，因为每个两个字符的前瞻都告诉我们要做不同的事情。

在LR(k > 1)分析中出现的向前查看点来确定何时进行移位是LR(2)分析中的新内容，但在LR(1)分析中没有。在LR(1)分析中，我们只需要查看点后面的终端符号。在LR(2)分析中，由于需要更多字符来确定要做什么，我们必须为每个移位项计算一个二级点前瞻。具体而言，点前瞻如下确定：

对于产生式A → α.tω [γ]，其中t是终端符号，在tωγ可推导出字符串的开头处可以出现长度为2的所有字符串的集合就是点前瞻。换句话说，产生式A → α.tω [γ]的点前瞻等于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)解析器。现在要做的就是将其编码为动作和转移表，沿用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

正如您所看到的，这里的每个条目只是说明是要移位还是归约。在实践中，每个归约项都会标记为实际进行归约的产生式，但是，呃，我懒得打出来。

在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项使用两个令牌的前瞻。这意味着我们需要使用FIRST2集而不是FIRST集，并且在确定是移位还是规约时引入了一些新的复杂性。
  • LR（2）解析具有点前瞻。对于每个移位项，我们使用FIRST2集来确定可以从当前点后面合法跟随的字符，并在任何一个字符上移位。
  • LR（2）动作表按字符对而不是单个字符进行键控，但goto表仍然按字符进行键控。

有趣的是，一旦你知道如何构建LR（2）解析器，你就可以推广这个想法，为任何k≥2构建LR（k）解析器。特别是，所有出现在此处的“新惊喜”都是您将看到的更大值的k的相同惊喜。

实际上，由于动作表的大小以及它们通常比LR（1）解析器具有更多状态，因此很少使用LR（2）解析器。但是，我认为了解它们的工作原理仍然是值得的。这让您对LR解析的工作方式有了更普遍的了解。

希望这有所帮助！

非常感谢@AProgrammer在cs.stackexchange.com上的答案，关于点先行符和项先行符的区别，这帮助我更好地理解了点先行符的功能和目的！

如果您想阅读有关LR(k)分析的原始论文，其中详细规定了LR(k)分析的全部规则，请查看唐纳德·克努斯（Don Knuth）的《从左到右翻译语言》。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接