LR（0）和SLRparsing有什么区别？
我正在编写我的编译器概念，但是我有点困惑…谷歌search没有给我一个明确的答案。
单反和LR（0）parsing器是同一个吗？ 如果不是，有什么区别？
LR（0）和SLR（1）parsing器都是自下而上的定向预测parsing器 。 这意味着
- parsing器试图反向应用产生，以减lessinput句子回到开始符号（ 自下而上 ）
- parsing器从左到右扫描input（ 定向 ）
- parsing器试图预测应用什么减less，而不必看到所有的input（ 预测 ）
LR（0）和SLR（1）都是移位/归约parsing器 ，这意味着他们通过将inputstream放置在堆栈上来处理inputstream的标记，并且在每个点上移动标记，方法是将标记推入堆栈或者减less在堆栈顶端的terminal和非terminal的序列回到一些非终结符号。 可以看出，任何语法都可以使用shift / reduce分析器自下而上地进行分析，但是该分析器可能不是确定性的 。 也就是说，parsing器可能不得不“猜测”是否应用转换或缩减，并且可能最终不得不回溯到意识到它做出了错误的select。 无论您构build的确定性移位/缩减parsing器多么强大，它将永远无法parsing所有语法。
当使用确定性移位/归约parsing器来parsing无法处理的语法时，会导致移位/减less冲突或减less/减less冲突 ，parsing器可能会进入一个状态，在该状态下无法确定要采取的操作。 在shift / reduce冲突中，它不能判断是否应该向堆栈中添加另一个符号，或者在堆栈的顶部符号上执行一些缩减操作。 在reduce / reduce冲突中，parsing器知道它需要用一些非终结符replace堆栈的顶部符号，但是它不能说明使用什么简化。
我很抱歉，如果这是一个冗长的说明，但我们需要这个能够解决LR（0）和SLR（1）parsing之间的区别。 LR（0）parsing器是一个移位/归约parsing器，它使用零标记的前瞻来确定要采取的操作（因此为0）。 这意味着在parsing器的任何configuration中，parsing器都必须有一个明确的动作来select – 要么移动特定的符号，要么应用特定的缩减。 如果有两个或更多的select，parsing器失败，我们说这个语法不是LR（0）。
回想一下，两个可能的LR冲突是转移/减less和减less/减less。 在这两种情况下，至less有两个LR（0）自动机可以采取的动作，并且不能告诉他们使用哪一个。 由于至less有一个冲突行为是减less的，所以合理的攻击行为是试图让parsing器在执行特定的缩减时更加小心。 更具体地说，让我们假设parsing器允许查看下一个input标记以确定它是否应该移位或减less。 如果我们只允许parsing器在“有意义”的情况下减less（对于“有意义”的一些定义），那么我们可以通过使自动机专门select移位或减less特定步骤。
在SLR（1）（简化的LR（1））中，parsing器在决定是否应该移位或缩小时，可以查看前瞻符号。 特别是，当parsing器想要尝试减lessA→wforms（对于非终结符A和stringw）时，它会查看下一个input符号。 如果该标记在某些派生中可能合法出现在非终结符A之后，那么parsing器将会减less。 否则，它不会。 这里的直觉是，在某些情况下，尝试减less是没有意义的，因为考虑到目前为止我们已经看到的令牌以及即将到来的令牌，减less总是没有可能是正确的。
LR（0）和SLR（1）之间的唯一区别是这种额外的能力来帮助决定在发生冲突时要采取的行动。 因此，任何可以由LR（0）parsing器parsing的语法都可以由SLR（1）parsing器parsing。 但是，SLR（1）parsing器可以parsing大于LR（0）的语法。
在实践中，SLR（1）仍然是一个相当薄弱的parsing方法。 更常见的是，您将看到正在使用的LALR（1）（“Lookahead LR（1）”）parsing器。 他们也试图解决LR（0）parsing器中的冲突，但是他们用来解决冲突的规则比单反中使用的规则要精确得多，因此，大量的语法是LALR（1）比单反（1）。 为了更具体一些，SLR（1）parsing器试图通过查看语法结构来解决冲突，以获得关于何时移位以及何时减less的更多信息。 LALR（1）语法分析器同时查看语法和LR（0）语法分析器，以获取有关何时移位和何时移位的更具体的信息。 因为LALR（1）可以查看LR（0）parsing器的结构，所以它可以更准确地确定何时某些冲突是虚假的。 Linux实用程序yacc和bison默认生成LALR（1）parsing器。
历史上，LALR（1）parsing器通常是通过依赖于更强大的LR（1）parsing器的不同方法构build的，因此您经常会看到LALR（1）这样描述。 为了理解这个，我们需要谈谈LR（1）parsing器。 在一个LR（0）parsing器中，parsing器通过跟踪它可能在生产中的位置来工作。 一旦发现它已经达到了生产的终点，它就知道要尽量减less。 然而，parsing器可能无法分辨出它是在一个生产的最后，还是在另一个生产的中间，这导致了转换/减less冲突，或者它已经达到了两个不同生产中的哪一个（减less/减less冲突）。 在LR（0）中，这立即导致冲突，parsing器失败。 在SLR（1）或LALR（1）中，parsing器然后基于下一个前瞻符号来做出移位或缩小的决定。
在LR（1）parsing器中，parsing器在运行时跟踪附加信息。 除了跟踪parsing器认为正在使用的生产外，它还跟踪在生产完成后可能出现的令牌。 因为parsing器在每个步骤都跟踪这些信息，而不仅仅是当它需要做出决定的时候，LR（1）parsing器比LR（0），SLR（1）或者LALR（1）parsing器到目前为止我们已经讨论过。 LR（1）是一种非常强大的parsing技术，可以用一些棘手的math表示， 任何移位/缩小parsing器可以确定性地parsing任何语言，都有一些可以用LR（1）自动机parsing的语法。 （注意，这并不意味着所有可以被确定性地分析的语法都是LR（1）;这只是说可以被确定性地parsing的语言有一些LR（1）语法）。 然而，这种能力是有代价的，一个生成的LR（1）parsing器可能需要太多的信息来操作，因此在实践中不可能被使用。 例如，一个真正的编程语言的LR（1）parsing器可能需要几十到几百兆字节的附加信息才能正确运行。 由于这个原因，LR（1）在实际中通常不会被使用，而像LALR（1）或SLR（1）这样的较弱的parsing器被用来代替。
最近，名为GLR（0）（“广义LR（0）”）的新分析algorithm已经获得了普及。 GLR（0）parsing器不是试图解决LR（0）parsing器中出现的冲突，而是通过并行地尝试所有可能的选项来工作。 使用一些聪明的技巧，这可以使很多语法非常有效地运行。 而且，GLR（0）完全可以parsing任何上下文无关的语法 ，甚至可以parsing任何k的LR（k）parsing器无法parsing的语法。 其他parsing器也可以这样做（例如，Earleyparsing器或CYKparsing器），尽pipeGLR（0）在实践中往往更快。
如果你有兴趣学习更多，今年夏天我教了一门介绍性的编译器课程，花了不到两周的时间讨论parsing技术。 如果您想对LR（0），SLR（1）以及其他一些强大的parsing技术进行更严格的介绍，您可以享受我的演讲幻灯片和关于parsing的作业分配。 所有的课程资料都可以在我的个人网站上find 。
希望这可以帮助！
这是我所学到的。 通常，LR（0）parsing器可能具有不明确性，也就是说，为了创buildparsing器，表格的一个框可以有多个值（或），以便更好地expression：parsing器导致具有相同input的两个最终状态。 所以创buildSLRparsing器来消除这种歧义。 为了构造它，find所有导致goto状态的生产，在左边find生产符号的跟随，只包括后面存在的goto状态。 这意味着你不包括使用原始语法不可能的生产（因为状态不在下面的集合中）
