This question already has answers here:
What is the difference between LR, SLR, and LALR parsers?
(8个答案)
去年关闭。
我了解LR和LALR都是自底向上的解析算法，但是两者之间有什么区别？
LR(0)，LALR(1)和LR(1)解析之间有什么区别？如何判断语法是LR(0)，LALR(1)还是LR(1)？ LALR(1)解析器是LR(0)解析器的“升级”版本，可跟踪更精确的信息以消除语法歧义。与LALR(1)解析器相比，LR(1)解析器是一种功能更强大的解析器，它可以跟踪更精确的信息。 LALR(1)解析器的常量因子大于LR(0)解析器，而LR(1)解析器通常以指数形式大于LALR(1)解析器。 可以使用LR(1)解析器解析任何语法，可以使用LALR(1)解析器解析任何语法，可以使用LR(1)解析器解析任何语法。有些语法是LALR(1)，但不是LR(0)和LR(1)，但不是LALR(1)。
更正式地说，LR(k)解析器是一种自底向上的解析器，它通过维护终端和非终端的堆栈来工作。解析器由有限自动机控制，该自动机根据解析器的当前状态和输入的下k个 token ，通过将乘积取反来将新 token 移入堆栈还是减少堆栈的顶部符号。
为了跟踪足够的信息来确定是否要移位或减小，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)自动机中任何特定状态的多个副本，每个副本都带有注释。不同的前瞻信息。 LALR(1)解析器可以通过从LR(1)解析器开始，然后将具有相同“核心”的所有状态(生产集及其位置)组合在一起，然后将所有前瞻信息汇总在一起来形成。这将导致一个解析器具有与LR(0)解析器相同的状态数，但是保留一些有关超前信息的信息，以帮助避免LR冲突。
LALR(1)语法的另一 View 使用“LALR-by-SLR”方法。可以通过从用于语法的LR(0)解析器开始，然后为该语言创建一个新语法来构造LALR(1)解析器，该语言用关于它们对应的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方法进行语言编写。大多数编译器教科书中提供了有关如何构造这些配置集的更多详细信息。您还可以 checkout the lecture notes from a compilers course I taught in Summer 2012，它涵盖了上述所有解析方法以及其他一些解析方法。
希望这可以帮助!
(8个答案)
去年关闭。
我了解LR和LALR都是自底向上的解析算法，但是两者之间有什么区别？
LR(0)，LALR(1)和LR(1)解析之间有什么区别？如何判断语法是LR(0)，LALR(1)还是LR(1)？
最佳答案
在较高级别上，LR(0)，LALR(1)和LR(1)之间的差异如下:
更正式地说，LR(k)解析器是一种自底向上的解析器，它通过维护终端和非终端的堆栈来工作。解析器由有限自动机控制，该自动机根据解析器的当前状态和输入的下k个 token ，通过将乘积取反来将新 token 移入堆栈还是减少堆栈的顶部符号。
为了跟踪足够的信息来确定是否要移位或减小，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)自动机中任何特定状态的多个副本，每个副本都带有注释。不同的前瞻信息。 LALR(1)解析器可以通过从LR(1)解析器开始，然后将具有相同“核心”的所有状态(生产集及其位置)组合在一起，然后将所有前瞻信息汇总在一起来形成。这将导致一个解析器具有与LR(0)解析器相同的状态数，但是保留一些有关超前信息的信息，以帮助避免LR冲突。
LALR(1)语法的另一 View 使用“LALR-by-SLR”方法。可以通过从用于语法的LR(0)解析器开始，然后为该语言创建一个新语法来构造LALR(1)解析器，该语言用关于它们对应的LR(0)解析器中的哪些状态的信息来注释非终结符。然后可以使用该语法中有关非终结符的FOLLOW集的信息来计算LR(0)解析器中的先行。
最终结果是
至于第二个问题-如何确定语法是LR(1)还是LALR(1)-标准方法是尝试为LR(1)解析器和LALR(1)解析器构建解析自动机并检查冲突。要构建LR(1)解析器，请构建LR(1)配置集，然后检查这些配置集中是否有移位/减少冲突或减少/减少冲突。要构造LALR(1)解析器，您可以构建LR(1)解析器，然后压缩具有相同内核的配置集，也可以使用基于LR(0)解析器的LALR-by-SLR方法进行语言编写。大多数编译器教科书中提供了有关如何构造这些配置集的更多详细信息。您还可以 checkout the lecture notes from a compilers course I taught in Summer 2012，它涵盖了上述所有解析方法以及其他一些解析方法。
希望这可以帮助!
关于parsing - LALR和LR解析之间有什么区别？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19663564/
10-12 13:53