39

我知道 LR 和 LALR 都是自下而上的解析算法，但两者有什么区别？

LR(0)、LALR(1) 和 LR(1) 解析有什么区别？如何判断语法是 LR(0)、LALR(1) 还是 LR(1)？

4

3 回答 3

68

在高层次上，LR(0)、LALR(1) 和 LR(1) 之间的区别如下：

  • LALR(1) 解析器是 LR(0) 解析器的“升级”版本，它跟踪更精确的信息以消除语法歧义。LR(1) 解析器是一个比 LALR(1) 解析器更强大的解析器，它可以跟踪更精确的信息。

  • LALR(1) 解析器是比 LR(0) 解析器大的常数因子，LR(1) 解析器通常比 LALR(1) 解析器大指数倍。

  • 任何可以用 LR(0) 解析器解析的文法都可以用 LALR(1) 解析器解析，任何可以用 LALR(1) 解析器解析的文法都可以用 LR(1) 解析器解析。有些文法是 LALR(1) 但不是 LR(0) 和 LR(1) 但不是 LALR(1)。

更正式地说，LR(k) 解析器是一个自底向上的解析器，它通过维护一堆终端和非终端来工作。解析器由有限自动机控制，该有限自动机根据解析器的当前状态和输入的下一个 k 令牌确定是将新令牌转移到堆栈上还是通过反向应用产生式来减少堆栈的顶部符号.

为了跟踪足够的信息来确定是移位还是减少，LR(k) 解析器使每个状态对应于一个“配置集”，即一组用以下信息注释的产生式：

  • 到目前为止已经看到了多少生产，以及
  • 生产完成后可以期待什么令牌（前瞻）

这些信息中的第一个用于确定解析器是否可能需要进行归约 - 如果当前状态下的所有产品都没有完成，则没有理由进行归约。这些信息中的第二条在进行归约时用于确定是否应该执行归约。在决定是否减少时，LR(k) 解析器会查看输入流的下 k 个标记。如果它们与前瞻标记匹配，则解析器将减少，否则解析器什么也不做。

当解析器在给定状态下应该做什么发生冲突时，LR(k) 解析器就会出现问题。当解析器处于产生式已完成的状态时，会出现一种类型的冲突，即移位/减少冲突，但该产生式冲突的前瞻符号也被该状态中的另一个未完成的产生式使用。这意味着解析器无法判断是否执行归约。第二种类型的冲突是reduce/reduce 冲突，解析器知道它必须进行归约，但可能有两个或更多归约，但它不知道该做什么。

直观地说，随着 k 变得越来越大，解析器拥有越来越多的精确信息来确定何时移动和何时减少。例如，如果一个文法不是 LR(0)，则解析器可能处于根本没有给定前瞻的状态，它无法确定是移位还是归约。但是，该语法可能仍然是 LR(1)，因为给定一个额外的前瞻标记，它可能能够识别出它应该肯定地转移而不是减少或肯定地减少而不是转移。

LR(k) 解析器的问题在于，随着 k 变大，状态的数量会呈指数增长。LR(k) 解析器中的前瞻是通过在解析器中构建越来越多的状态来处理的，以对应于产生式和前瞻的不同组合，因此随着可能的前瞻数量的增加，状态的数量也会增加。因此，LR(1) 解析器通常太大而无法实用，而 LR(2) 或更大的解析器在实践中几乎闻所未闻。

LALR(1) 是作为 LR(0) 解析器的空间效率和 LR(1) 解析器的表达能力之间的折衷而发明的。有几种方法可以考虑什么是 LALR(1) 解析器。最初，LALR(1) 解析器被指定为将 LR(1) 自动机转换为更小的自动机的转换。尽管 LR(1) 解析器可能比 LR(0) 自动机具有更多的状态，但唯一的区别是 LR(1) 解析器可能在 LR(0) 自动机中具有任何特定状态的多个副本，每个副本都用注释不同的前瞻信息。LALR(1) 解析器可以通过从 LR(1) 解析器开始，然后将具有相同“核心”的所有状态（产生式及其位置的集合）组合在一起，然后将所有前瞻信息聚合在一起来形成。

LALR(1) 语法的另一种观点使用“LALR-by-SLR”方法。LALR(1) 解析器可以通过从语法的 LR(0) 解析器开始构建，然后为该语言创建一个新的语法，该语法用关于它们对应的 LR(0) 解析器中的哪些状态的信息来注释非终结符。然后可以使用关于该语法中非终结符的 FOLLOW 集的信息来计算 LR(0) 解析器中的前瞻。

最终结果是

  • LR(0) 解析器很小，但不是很有表现力。
  • 由于前瞻信息，LALR(1) 解析器稍大，但非常具有表现力。
  • LR(1) 解析器非常庞大，但极具表现力。

至于您的第二个问题-您如何确定语法是 LR(1) 还是 LALR(1)-标准方法是尝试为 LR(1) 解析器和 LALR(1) 解析器构建解析自动机并检查为冲突。要构建 LR(1) 解析器，您需要构建 LR(1) 配置集，然后检查这些配置集是否存在移位/归约冲突或归约/归约冲突。要构建 LALR(1) 解析器，您可以构建 LR(1) 解析器，然后压缩具有相同核心的配置集，也可以使用基于 LR(0) 解析器的 LALR-by-SLR 方法。大多数编译器教科书中都提供了有关如何构造这些配置集的更多详细信息。您还可以查看我在 2012 年夏季教授的编译器课程的讲义，其中涵盖了上述所有解析方法和其他一些解析方法。

希望这可以帮助！

于 2013-10-29T16:37:00.783 回答
1

一个好的 LALR(1) 解析器的解析算法在两个方面是不同的：(1) 它应该有 shift-reduce 动作，这可以减少大约 30% 的状态数量并使解析器更快，以及 (2) 它必须在检测到语法错误时做一个或多个归约，这使得错误恢复更加复杂。

规范 LR(1) 解析器的解析算法 (1) 没有移位归约动作，并且 (2) 在检测到语法错误时不进行任何归约，这使得错误恢复更简单。

还有另一种情况，称为最小 LR(1)，它使用与 LALR(1) 相同的解析算法和错误恢复算法。Minimal LR(1) 解析器提供 LR(1) 的强大功能，并且它们的大小几乎与 LALR(1) 一样小。LRSTAR解析器生成器为 C++ 程序员创建最小的 LR(1) 解析器。

于 2017-03-20T22:36:03.757 回答
1

LR(0)、SLR(1)、LALR(1) 解析器都具有相同数量的状态。如果语法需要，最小的 LR(1) 解析器将有更多的状态，以避免减少-减少冲突。

规范 LR(1) 解析器将有更多的状态，对于中型或大型计算机语言来说太多了。

SLR(1) 解析器生成器构建一个 LR(0) 状态机并通过检查语法（可能报告错误冲突）来确定 k=1 前瞻。

LALR(1) 解析器生成器构建一个 LR(0) 状态机并通过检查 LR(0) 状态机（非常复杂）来确定 k=1 前瞻。

规范 LR(1) 解析器生成器构建 LR(1) 状态机。

最小 LR(1) 解析器生成器构建 LR(1) 状态机并在构建过程中合并兼容状态。

于 2017-03-20T22:47:24.293 回答