LR，SLR和LALRparsing器有什么区别？
LR，SLR和LALRparsing器的实际区别是什么？ 我知道SLR和LALR是LRparsing器的types，但是就parsing表而言，实际的差异是什么？
以及如何显示语法是LR，SLR还是LALR？ 对于LL语法，我们只需要显示parsing表中的任何单元格都不应包含多个生产规则。 任何类似LALR，SLR和LR的规则？
例如，我们如何显示语法
S --> Aa | bAc | dc | bda A --> d 是LALR（1）而不是SLR（1）？
编辑（ybungalobill） ：我没有得到一个令人满意的答案是什么LALR和LR之间的差异。 所以LALR的表格尺寸较小，但它只能识别LR语法的一个子集。 请有人详细说明LALR和LR之间的区别吗？ LALR（1）和LR（1）就足够答案。 他们两个使用1令牌前瞻，并都是表驱动！ 他们有什么不同？
SLR，LALR和LRparsing器都可以使用完全相同的表驱动机器来实现。
从根本上讲，parsingalgorithm收集下一个input标记T，并查阅当前状态S（和相关的预测，GOTO和还原表）来决定做什么：
- SHIFT：如果当前表对T令牌表示为SHIFT，则将该对（S，T）压入分析堆栈，根据GOTO表针对当前令牌（例如GOTO（T） ），则取出另一个input令牌T'，并重复该过程
- 减less：每个州有可能在该州发生0,1或多个可能的减排。 如果parsing器是LR或LALR，则会根据先行集检查该标记是否为所有有效的状态减less。 如果令牌匹配语法规则G = R1 R2 … Rn的缩减预测集合，则会发生堆栈减less和移位：调用G的语义操作，堆栈被popupn（从Rn）次，对（ S，G）被压入堆栈，新的状态S'被设置为GOTO（G），并且该循环以相同的标记T重复。如果parsing器是SLRparsing器，则对于状态，因此可以盲目地完成简化操作，而无需查看哪个简化适用。 单反parsing器知道是否有减less是有用的; 这很容易判断每个状态是否明确地logging了与之相关的减less的数量，并且无论如何，这个数量在L（AL）R版本中是需要的。
- 错误：如果SHIFT和REDUCE都不可能，则声明语法错误。
那么，如果他们都使用相同的机器，那有什么意义呢？
单反的价值在于其实施简单， 您不必扫描可能的缩减检查先行集，因为最多只有一个，如果没有SHIFT从状态退出，这是唯一可行的操作。 SLR语法分析机制不需要专门针对状态进行修改。 在实践中，L（AL）Rparsing器处理一大堆有用的语言，除了作为学术练习之外，没有人实施单反。
LALR和LR的区别在于表生成器 。 LRparsing器生成器跟踪特定状态及其精确预测集的所有可能的减less; 你最终会得到一些状态，每个状态的减less都与它的左上下文中的确切的前瞻关联。 这倾向于build立相当大的国家集合。 如果GOTO表和lookhead集合的缩减是兼容的并且不冲突的话，LALRparsing器生成器愿意组合状态。 这产生相当小的状态数量，以不能区分LR可以区分的某些符号序列的代价。 因此，LRparsing器可以parsing比LALRparsing器更大的一组语言，但是具有非常大的parsing器表。 在实践中，人们可以find与目标语言相近的LALR语法，以使状态机的大小值得优化; LRparsing器会更好的地方是通过parsing器外部的特别检查来处理的。
所以：所有三个使用相同的机器。 单反是“容易的”，因为你可以忽略一小部分的机器，但它是不值得的麻烦。 LRparsing更广泛的语言，但状态表往往是相当大的。 这使得LALR成为实际的select。
说完这一切，值得一提的是GLRparsing器可以parsing任何上下文无关的语言，使用更复杂的机制， 但是完全相同的表 （包括LALR使用的较小版本）。 这意味着GLR比LR，LALR和SLR严格得多; 如果你可以编写一个标准的BNF语法，那么GLR将根据它进行parsing。 机制的不同之处在于，当GOTO表和/或前瞻集之间存在冲突时，GLR愿意尝试多个分析。 （GLR如何有效地做到这一点纯粹是天才（不是我的），但不适合这个SO职位）。
对我来说这是一个非常有用的事实。 我build立程序分析器和代码转换器和parsing器是必要的，但“无趣”; 有趣的工作是你对parsing结果做什么，所以重点是做parsing后的工作。 使用GLR意味着我可以比较容易地构build工作语法，而不是通过语法来进入LALR可用的forms。 当试图处理诸如C ++或Fortran等非学术语言时，这非常重要，在那里你需要数千条规则来处理整个语言，而且你不希望花费一生的时间来试图破解语法规则符合LALR（甚至LR）的局限性。
作为一个有名的例子，C ++被认为是非常难以parsing的……通过LALRparsing的人。 使用C ++参考手册后面提供的规则，C ++可以直接使用GLR机制进行parsing。 （我正好有这样一个parsing器，它不仅处理香草C ++，而且还处理各种厂商方言，这只是在实践中可能的，因为我们正在使用一个GLRparsing器，恕我直言）。
[编辑2011年11月：我们已经扩展了我们的parsing器来处理所有的C ++ 11。 GLR让这件事更容易做到。]
LALRparsing器合并LR语法中的相似状态以产生与等效的SLR语法完全相同大小的语法分析器状态表，其通常比纯LR语法分析表小一个数量级。 但是，对于太复杂而不能成为LALR的LR语法，这些合并状态会导致语法分析器冲突，或者产生一个不能完全识别原始LR语法的分析器。
顺便说一下，我在这里提到我的MLR（k）parsing表algorithm中的一些事情。
附录
简短的回答是，LALRparsing表更小，但parsing器机制是相同的。 一个给定的LALR语法将产生更大的parsing表，如果所有的LR状态都被生成，并具有大量的冗余（近似）状态。
LALR表更小，因为相似（冗余）状态合并在一起，有效地丢弃了单独状态编码的上下文/前瞻信息。 好处是你可以为同样的语法获得更小的parsing表。
缺点是不是所有的LR语法都可以被编码为LALR表，因为更复杂的语法具有更复杂的lookahead，导致两个或更多的状态，而不是一个单一的合并状态。
主要区别在于生成LR表格的algorithm在从状态到状态的转换之间携带更多的信息，而LALRalgorithm则不支持。 所以LALRalgorithm不能分辨一个给定的合并状态是否应该作为两个或多个独立的状态。
又一个答案（YAA）。
SLR（1），LALR（1）和LR（1）的parsingalgorithm与Ira Baxter所说的相同，
然而，由于parsing器生成algorithm，parsing器表可能不同。
SLRparsing器生成器创build一个LR（0）状态机，并从语法（FIRST和FOLLOW集）计算前瞻。 这是一种简化的方法，可能会报告LR（0）状态机中不存在的冲突。
LALRparsing器生成器创build一个LR（0）状态机，并从LR（0）状态机（通过terminal转换）计算前瞻。 这是一个正确的方法，但偶尔会报告在LR（1）状态机中不存在的冲突。
Canonical LRparsing器生成器计算一个LR（1）状态机，并且前瞻已经是LR（1）状态机的一部分。 这些parsing器表可能非常大。
最小LR分析器生成器计算一个LR（1）状态机，但在过程中合并兼容状态，然后从最小LR（1）状态机计算前瞻。 这些parsing器表与LALRparsing器表具有相同的大小或稍大，给出了最佳的解决scheme。
LRSTAR 8.0可以在C ++中生成LALR（1），Minimal LR（1）和LR（k）parsing器。
SLR与LR生成的parsing器表之间的基本区别在于，reduce操作基于SLR表的Follows集。 这可能是过度的限制，最终导致减less冲突。
另一方面，LR语法分析器只能减less实际上跟随非terminal的terminal集合减less的决策。 这组terminal通常是这样的非terminal的跟随集合的适当子集，因此与换档动作相冲突的可能性较小。
LRparsing器因为这个原因更加强大。 然而，LRparsing表可能非常大。
LALRparsing器以构buildLRparsing表的想法开始，但将生成的状态组合在一起，从而导致表的大小显着减less。 不利的一面是，一些LR表可能避免了一些语法冲突的机会。
LALRparsing器的function稍弱于LRparsing器，但仍比SLRparsing器更强大。 YACC和其他这样的parsing器生成器倾向于使用LALR。
PS为简单起见，以上SLR，LALR和LR实际上意味着SLR（1），LALR（1）和LR（1），所以暗示了一个令牌前瞻。
SLRparsing器识别由LALR（1）parsing器可识别的语法的适当子集，其继而识别LR（1）parsing器可识别的语法的适当子集。
其中的每一个都是作为一个状态机来构造的，每个状态代表语法的一些生成规则（在每个状态中的位置），因为它parsinginput。
不是SLR的LALR（1）语法的Dragon Book例子是这样的：
S → L = R | R L → * R | id R → L
这是这个语法的状态之一：
S → L•= R R → L•
•表示parsing器在每个可能产品中的位置。 它不知道它实际上在生产哪个产品，直到它结束并试图减less。
在这里，parsing器可以移位an =或者减lessR → L 。
SLR（又名LR（0））parsing器将通过检查下一个input符号是否在R的后续集合 （即语法中可能跟随R的所有terminal的集合）中来确定它是否可以减less。 由于=也在这个集合中，所以SLRparsing器遇到移位 – 缩减冲突。
然而，LALR（1）parsing器将使用可以遵循这个特定生产 R的所有terminal的集合，其仅仅是$ （即，input的结束）。 因此，没有冲突。
正如前面的评论者所指出的，LALR（1）parsing器具有与SLRparsing器相同的状态数量。 先行传播algorithm被用于从相应的LR（1）状态开始对SLR状态产生的预见（lookahead）。 由此产生的LALR（1）parsing器可以引入LR（1）parsing器中不存在的reduce-reduce冲突，但不能引入shift-reduce冲突。
在你的例子中 ，下面的LALR（1）状态导致SLR实现中的移位 – 缩减冲突：
S → bd•a / $ A → d• / c
L之后的符号是LALR（1）parsing器中每个生产的后续设置。 在单反中， （ A ）包括a ，也可以移动。
假设一个没有前瞻的parsing器可以愉快地为你的语法parsingstring。
使用你给出的例子，它会遇到一个stringdc ，它是做什么的？ 它是否将它减less到S ，因为dc是由这个语法生成的有效string？ 或者，也许我们试图parsingbdc因为即使这是一个可以接受的string？
作为人类，我们知道答案很简单，我们只需要记住，如果我们刚刚parsingb或不。 但电脑是愚蠢的:)
由于SLR（1）语法分析器比LR（0）具有更强的执行前瞻性的function，因此我们知道任何数量的lookahead都不能告诉我们在这种情况下做什么。 相反，我们需要回顾过去。 因此，规范LR分析器来救援。 它记得过去的情况。
它记住这个背景的方式是它自我约束，每当它遇到一个b ，它就开始走在阅读bdc的道路上，作为一种可能性。 所以当它看到一个d它知道它是否已经走了一条路。 因此，CLR（1）parsing器可以做SLR（1）parsing器不能做的事情！
但现在，由于我们必须定义这么多path，机器的状态变得非常大！
所以我们把相同的path合并起来，但是正如所期望的那样，它可能会引起混乱的问题。 但是，我们愿意以减小规模为代价来承担风险。
这是你的LALR（1）parsing器。
现在如何algorithm。
当您绘制上述语言的configuration集时，您将看到两种状态下的移位 – 缩减冲突。 要删除它们，你可能需要考虑一个单反（1），这个单反需要做出决定，但是你会发现它仍然不能。 因此，您可以再次绘制configuration集，但是这一次有一个限制，即每当计算闭包时，所添加的附加产品都必须严格遵循。 请参阅任何教科书关于这些应该是什么。
一个简单的答案是所有LR（0）语法都是LALR（1）语法。 与LR（1）相比，LALR（1）在相关的DFA中具有更多的状态（几乎是双重状态），这就是LALR（1）语法比LR（1）语法需要更多时间显示错误的主要原因。 关于这两个语法的另一个重要的事情是，在LR（1）语法中，我们不能find转换/减less或减less/减less冲突。但是在LALR（1）中存在减less/减less冲突的可能性。
