algorithm - LR(0) 和 SLR 解析有什么区别？

Question

我正在研究我的编译器概念，但是我有点困惑......
谷歌搜索让我无处获得明确的答案。

SLR 和 LR(0) 解析器是一回事吗？如果不是，有什么区别？

Answer 1

LR(0) 和 SLR(1) 解析器都是自底向上的、定向的、预测的解析器。这意味着

解析器尝试反向应用产生式以将输入句子减少回开始符号(自下而上)

解析器从左到右(定向)扫描输入

解析器尝试预测要应用的缩减量，而不必看到所有输入(预测)

LR(0) 和 SLR(1) 都是 移位/减少解析器 ，这意味着它们通过将输入流的标记放在堆栈上来处理它们，并且在每个点 换挡将 token 压入堆栈或 减少堆栈顶部的一些终结符和非终结符序列回到某个非终结符符号。可以证明任何语法都可以使用 shift/reduce 解析器自底向上解析，但该解析器可能不是确定性的。也就是说，解析器可能不得不“猜测”是应用移位还是归约，并且可能最终不得不回溯以意识到它做出了错误的选择。无论您构建的确定性移位/归约解析器多么强大，它都永远无法解析所有语法。

当确定性移位/归约解析器用于解析它无法处理的语法时，会导致 转移/减少冲突 或 减少/减少冲突 ，解析器可能会进入一种状态，在这种状态下它无法判断要采取什么操作。在移位/归约冲突中，它无法判断是否应该向堆栈添加另一个符号或对堆栈的顶部符号执行一些归约。在reduce/reduce 冲突中，解析器知道它需要用一些非终结符替换堆栈的顶部符号，但它无法确定使用什么reduce。

如果这是一个冗长的说明，我深表歉意，但我们需要它来解决 LR(0) 和 SLR(1) 解析之间的差异。 LR(0) 解析器是一种移位/归约解析器，它使用前瞻的零标记来确定要采取的操作(因此为 0)。这意味着在解析器的任何配置中，解析器必须有一个明确的 Action 可供选择 - 要么移动特定符号，要么应用特定归约。如果有两个或多个选择，解析器失败，我们说文法不是 LR(0)。

回想一下，两种可能的 LR 冲突是 shift/reduce 和 reduce/reduce。在这两种情况下，LR(0) 自动机至少可以采取两个 Action ，但它无法分辨要使用哪个 Action 。由于至少有一个冲突操作是归约，合理的攻击方式是尝试让解析器在执行特定归约时更加小心。更具体地说，让我们假设允许解析器查看输入的下一个标记以确定它是应该移位还是减少。如果我们只允许解析器在它“有意义”时减少它(对于“有意义”的某些定义)，那么我们可以通过让自动机专门选择在一个具体步骤。

在 SLR(1) ("Simplified LR(1)") 中，解析器在决定是否应该移位或减少时可以查看前瞻的一个标记。特别是，当解析器想要尝试减少 A → w 形式的某些东西(对于非终结符 A 和字符串 w)时，它会查看输入的下一个标记。如果该标记可以合法地出现在某些派生中的非终结符 A 之后，解析器就会减少。否则，它不会。这里的直觉是，在某些情况下，尝试减少是没有意义的，因为考虑到我们迄今为止看到的 token 和即将到来的 token ，减少是不可能正确的。

LR(0) 和 SLR(1) 之间的唯一区别是这种额外的能力，可以帮助决定在发生冲突时采取什么行动。因此，任何可以由 LR(0) 解析器解析的语法都可以由 SLR(1) 解析器解析。但是，与 LR(0) 相比，SLR(1) 解析器可以解析更多的语法。

但在实践中，SLR(1) 仍然是一种相当弱的解析方法。更常见的是，您会看到正在使用 LALR(1) ("Lookahead LR(1)") 解析器。它们也通过尝试解决 LR(0) 解析器中的冲突来工作，但是它们用于解决冲突的规则比 SLR(1) 中使用的规则要精确得多，因此更多的语法是 LALR(1)比单反(1)。更具体地说，SLR(1) 解析器尝试通过查看语法结构来了解有关何时移位和何时减少的更多信息来解决冲突。 LALR(1) 解析器同时查看语法和 LR(0) 解析器，以获取有关何时移位和何时减少的更具体信息。因为 LALR(1) 可以查看 LR(0) 解析器的结构，所以它可以更准确地识别某些冲突何时是虚假的。 Linux 实用程序 yacc和 bison ，默认情况下，生成 LALR(1) 解析器。

从历史上看，LALR(1) 解析器通常是通过依赖于更强大的 LR(1) 解析器的不同方法构建的，因此您经常会看到 LALR(1) 是这样描述的。要理解这一点，我们需要谈谈 LR(1) 解析器。在 LR(0) 解析器中，解析器通过跟踪它可能在生产过程中的位置来工作。一旦发现它已经达到生产的终点，它就会知道尝试减少。但是，解析器可能无法判断它是在一个产生式的末尾还是另一个产生式的中间，这会导致移位/减少冲突，或者它已经到达了两个不同产生式中的哪一个(减少/减少冲突)。在 LR(0) 中，这会立即导致冲突并且解析器失败。在 SLR(1) 或 LALR(1) 中，解析器然后根据前瞻的下一个标记做出移动或减少的决定。

在 LR(1) 解析器中，解析器在运行时会跟踪附加信息。除了跟踪解析器认为正在使用的产品之外，它还跟踪该产品完成后可能出现的 token 。因为解析器在每一步都跟踪这些信息，而不仅仅是在需要做出决定的时候，LR(1) 解析器比 LR(0)、SLR(1) 或到目前为止我们已经讨论过的 LALR(1) 解析器。 LR(1) 是一种非常强大的解析技术，它可以使用一些棘手的数学来证明，任何语言都可以被 确定性地解析。任何 shift/reduce 解析器有一些可以用 LR(1) 自动机解析的语法。 (请注意，这并不意味着所有 文法 可以被确定性地解析都是 LR(1)；这只是说明一种可以被确定性地解析的语言具有一些 LR(1) 文法)。然而，这种能力是有代价的，生成的 LR(1) 解析器可能需要太多的信息来运行，以至于它不可能在实践中使用。例如，用于实际编程语言的 LR(1) 解析器可能需要数十到数百兆字节的附加信息才能正确运行。出于这个原因，LR(1) 在实践中通常不使用，而是使用较弱的解析器，如 LALR(1) 或 SLR(1)。

最近，一种称为 GLR(0)(“Generalized LR(0)”)的新解析算法开始流行。 GLR(0) 解析器不是尝试解决出现在 LR(0) 解析器中的冲突，而是通过并行尝试所有可能的选项来工作。使用一些巧妙的技巧，可以使许多语法非常有效地运行。此外，GLR(0) 可以解析任何上下文无关文法，即使是 LR(k) 解析器无法解析任何 k 的文法。其他解析器也可以这样做(例如，Earley 解析器或 CYK 解析器)，尽管 GLR(0) 在实践中往往更快。

如果您有兴趣了解更多信息，今年夏天我教授了一门介绍性的编译器类(class)，并花了不到两周的时间谈论解析技术。如果您想更严格地介绍 LR(0)、SLR(1) 和许多其他强大的解析技术，您可能会喜欢我关于解析的讲座幻灯片和家庭作业。所有类(class)资料均可使用 here on my personal site .

希望这有帮助!