parsing - LALR 和 LR 解析有什么区别？

Question

这个问题在这里已经有了答案:





What is the difference between LR, SLR, and LALR parsers?

(8 个回答)


2年前关闭。




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

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

Answer 1

在高层次上，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) 解析器就会出现问题。当解析器处于产生式已完成的状态时，会出现一种类型的冲突，即移位/减少冲突，但该产生式冲突的前瞻符号也被该状态中的另一个未完成的产生式使用。这意味着解析器无法判断是否执行归约。第二种类型的冲突是归约/归约冲突，解析器知道它必须进行归约，但可能进行两次或多次归约，但它不知道该做什么。

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

LR(k) 解析器的问题在于，随着 k 变大，状态数会呈指数增长。 LR(k) 解析器中的 Lookahead 是通过在解析器中构建越来越多的状态来处理的，以对应于产生式和 Lookahead 的不同组合，因此随着可能的 Lookahead 数量的增加，状态的数量也会增加。因此，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) 解析器开始，然后将具有相同“核心”(产生式及其位置的集合)的所有状态组合在一起，然后将所有前瞻信息聚合在一起来形成。这导致解析器具有与 LR(0) 解析器相同数量的状态，但保留了一些关于前瞻的信息以帮助避免 LR 冲突。

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 方法。大多数编译器教科书中提供了有关如何构造这些配置集的更多详细信息。您也可以查看 the lecture notes from a compilers course I taught in Summer 2012 ，涵盖了上述所有解析方法和其他一些解析方法。

希望这可以帮助!