LR（0）和SLR解析之间有什么区别？

LR（0）和SLR解析之间有什么区别？

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

• 解析器尝试反向应用产生式运算，以将输入语句还原为起始符号（ 自下而上 ）
• 解析器从左到右（ 方向 ）扫描输入
• 解析器尝试预测要应用的减少量，而不必看到所有输入（ 预测性 ）

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

当使用确定性的移位/归约解析器解析它无法处理的语法时，会导致 移位/归纳冲突 或 归约/归约冲突
，解析器可能会进入无法告知要采取何种 *** 作的状态。在移位/减少冲突中，它无法确定是应向堆栈中添加另一个符号还是对堆栈的顶部符号进行某种缩减。在reduce /
reduce冲突中，解析器知道它需要用一些非终结符替换堆栈的顶部符号，但是它无法确定要使用哪种缩减。

对于这是一个冗长的阐述，我深表歉意，但是我们需要这样做才能解决LR（0）和SLR（1）解析之间的差异。LR（0）解析器是一种移位/缩减解析器，它使用零提前标记来确定要采取的 *** 作（因此为0）。这意味着在解析器的任何配置中，解析器都必须有明确的 *** 作可供选择-
移位特定符号或应用特定归约。如果有两个或多个选择，解析器将失败，我们说该语法不是LR（0）。

回想一下，两个可能的LR冲突是平移/减少和减少/减少。在这两种情况下，LR（0）自动机至少可以执行两个动作，并且无法区分要使用哪个动作。由于冲突 *** 作中至少有一个是还原 *** 作，因此合理的攻击方法是尝试使解析器在执行特定还原 *** 作时更加小心。更具体地说，让我们假设允许解析器查看输入的下一个标记，以确定它是应该移位还是应减少。如果我们仅允许解析器在“有意义”的情况下进行缩减（对于“有意义”的某种定义），那么我们也许可以通过让自动机专门选择在其中移动或缩减来消除冲突。特定步骤。

在SLR（1）（“简化的LR（1）”）中，允许解析器在确定是否应移动或缩小时查看先行标记。特别是，当解析器想要尝试简化形式A→w（对于非终结符A和字符串w）时，它将查看输入的下一个标记。如果在某些派生中该令牌可以合法地出现在非终结符A之后，则解析器将减少。否则，它不会。直觉是，在某些情况下尝试减少是没有意义的，因为鉴于我们到目前为止已经看到的令牌以及即将到来的令牌，减少的方法永远不可能是正确的。

LR（0）和SLR（1）之间的唯一区别是，这种额外的功能可以帮助您确定在发生冲突时应采取的 *** 作。因此，可以由SLR（1）解析器解析任何可以由LR（0）解析器解析的语法。但是，SLR（1）解析器比LR（0）可以解析更多的语法。

但是，实际上，SLR（1）仍然是一种较弱的解析方法。更常见的是，您会看到正在使用LALR（1）（“ Lookahead
LR（1）”）解析器。它们也通过尝试解决LR（0）解析器中的冲突而起作用，但是用于解决冲突的规则比SLR（1）中使用的规则精确得多，因此LALR（1）的语法数量要大得多。比SLR（1）大。更具体地说，SLR（1）解析器尝试通过查看语法的结构来解决冲突，以了解有关何时转移和何时减少的更多信息。LALR（1）解析器同时查看语法和LR（0）解析器，以获取有关何时转移和何时减少的更具体的信息。因为LALR（1）可以查看LR（0）解析器的结构，所以它可以更精确地标识某些冲突是虚假的。

yacc

和

bison

，默认情况下，产生LALR（1）解析器。

从历史上看，LALR（1）解析器通常通过依赖于功能更强大的LR（1）解析器的另一种方法构造，因此您经常会看到LALR（1）以此方式进行描述。为了理解这一点，我们需要谈论LR（1）解析器。在LR（0）解析器中，解析器通过跟踪生产环境中的位置来工作。一旦发现它已经达到生产的极限，它便知道要减少。但是，解析器可能无法分辨它是在一个生产的末尾还是在另一个生产的中间，这会导致移位/减少冲突，或者它已经到达了两个不同生产中的哪个（减少/减少冲突）。在LR（0）中，这立即导致冲突，并且解析器失败。在SLR（1）或LALR（1）中，

在LR（1）解析器中，解析器在运行时会跟踪其他信息。除了跟踪解析器认为正在使用的生产之外，它还跟踪生产完成后可能出现的令牌。因为解析器在每个步骤（不仅是在需要做出决定时）都会跟踪此信息，所以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）往往会更快。

如果您有兴趣了解更多信息，今年夏天，我教了一个入门性的编译器课程，并花了不到两周的时间讨论解析技术。如果您想对LR（0），SLR（1）以及更多其他强大的解析技术进行更严格的介绍，您可能会喜欢我的演讲幻灯片和有关解析的家庭作业。所有课程材料都可以
在我的个人网站上找到 。

希望这可以帮助！