LALR和LR解析有什么区别？

Question

LALR和LR解析有什么区别？

parsingcompiler-constructioncontext-free-grammarlalrlr-grammar

42

我了解LR和LALR都是自下而上的语法分析算法，但它们之间有什么区别呢？

LR(0)、LALR(1)和LR(1)语法分析有什么差异？我该如何判断一个语法是否为LR(0)、LALR(1)或LR(1)？

- AAB

3个回答

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)状态机，并在构建过程中合并兼容状态。

- user1524750

0

一个好的 LALR(1) 解析器的解析算法有两个不同之处：(1) 它应该具有移位-规约操作，这将状态数减少约30％并使解析器更快，(2) 当检测到语法错误时，它必须执行一次或多次规约，这使得错误恢复更加复杂。

一个标准 LR(1) 解析器的解析算法 (1) 没有移位-规约操作，(2) 在检测到语法错误时不进行任何规约，这使得错误恢复更简单。

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

- user1524750

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

从高层次来看，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)解析器中的向前看由构建更多状态来处理，以对应不同的产生式和向前看的组合，因此随着可能的向前看数量的增加，状态数也会增加。因此，LR(1)解析器通常太大而无法实际使用，而LR(2)或更高的解析器在实践中几乎不被使用。LALR(1)是在LR(0)分析器的空间效率和LR(1)分析器的表达能力之间做出的妥协。有几种方式来理解LALR(1)分析器。最初，LALR(1)分析器被规定为将LR(1)自动机转换为更小的自动机的转换。虽然LR(1)分析器可能比LR(0)自动机多出许多状态，但唯一的区别在于LR(1)分析器可能在LR(0)自动机的任何特定状态中有多个副本，每个副本都带有不同的展望信息。通过从LR(1)分析器开始，将具有相同“核心”（产生式及其位置集）的所有状态组合在一起，然后聚合所有展望信息，可以形成LALR(1)分析器。这样就得到了一个与LR(0)分析器具有相同状态数的分析器，但保留了一些展望信息以帮助避免LR冲突。

另一种LALR(1)文法的看法使用“LALR-by-SLR”方法。可以通过从语法的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年夏季教授的编译器课程的讲义，其中涵盖了上述所有解析方法以及其他一些方法。

希望这可以帮到你！