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冲突的可能性。