Pra*_*rav 101 compiler-construction algorithm grammar parsing
LR,SLR和LALR解析器之间的实际区别是什么？我知道SLR和LALR是LR解析器的类型,但就解析表而言,它们的实际区别是什么？
以及如何显示语法是LR,SLR还是LALR？对于LL语法,我们只需要显示解析表的任何单元格都不应包含多个生产规则.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个令牌前瞻,两个都是表驱动的!它们有何不同？
Ira*_*ter 59
SLR,LALR和LR解析器都可以使用完全相同的表驱动机制来实现.
从根本上说,解析算法收集下一个输入令牌T,并查询当前状态S(以及相关的前瞻,GOTO和缩减表)以决定做什么:
那么,如果他们都使用相同的机器,那有什么意义呢？
SLR中声称的价值在于其实施的简单性; 您不必扫描可能的减少检查前瞻集,因为最多只有一个,如果没有SHIFT退出状态,这是唯一可行的操作.哪种减少适用于特定于状态,因此SLR解析机器不必寻找它.在实践中,L(AL)R解析器处理一个有用的更大的语言集,除了作为学术练习之外,没有人实现SLR是如此少的额外工作.
LALR和LR之间的区别与表生成器有关.LR解析器生成器跟踪特定状态及其精确前瞻集的所有可能的减少; 你最终得到的状态是每个减少与其左上下文中的精确前瞻集相关联.这往往会构建相当大的状态集.如果用于缩减的GOTO表和lookhead集兼容且不冲突,则LALR解析器生成器愿意组合状态; 这会产生相当少数量的状态,代价是无法区分LR可以区分的某些符号序列.因此,LR解析器可以解析比LALR解析器更大的语言集,但是具有更大的解析器表.在实践中,人们可以找到足够接近目标语言的LALR语法,状态机的大小值得优化;
所以:这三个都使用相同的机器.SLR是"简单的",因为你可以忽略一小部分机器,但它不值得麻烦.LR解析了更广泛的语言,但状态表往往相当大.这使得LALR成为实用的选择.
说完这一切之后,值得了解GLR解析器可以解析任何上下文无关语言,使用更复杂的机器但完全相同的表(包括LALR使用的较小版本).这意味着GLR比LR,LALR和SLR更强大; 几乎如果你能写一个标准的BNF语法,GLR会根据它进行解析.机器的不同之处在于,当GOTO表和/或超前集之间存在冲突时,GLR愿意尝试多次解析.(GLR如何有效地做到这一点纯粹是天才[不是我的]但不适合这篇SO帖子).
对我来说这是一个非常有用的事实.我构建程序分析器和代码转换器和解析器是必要的,但"无趣"; 有趣的工作是你用解析的结果做的事情,因此重点是做后解析工作.使用GLR意味着我可以相对容易地构建工作语法,而不是使用语法来进入LALR可用形式.在尝试处理像C++或Fortran这样的非学术语言时,这很重要,因为你需要成千上万的规则才能很好地处理整个语言,并且你不想花费你的生命来试图破解语法规则满足LALR(甚至LR)的限制.
作为一个着名的例子,C++被认为是非常难以解析...由做LALR解析的人.使用C++参考手册后面提供的规则,使用GLR机制解析C++很简单.(我有一个这样的解析器,它不仅处理vanilla C++,而且还处理各种供应商方言.这只能在实践中实现,因为我们使用的是GLR解析器,恕我直言).
[编辑2011年11月:我们扩展了解析器以处理所有C++ 11.GLR让事情变得更容易.编辑2014年8月:现在处理所有的C++ 17.没有什么破坏或变得更糟,GLR仍然是猫的喵喵.
Dav*_*ble 18
LALR解析器合并LR语法中的类似状态以生成与等效SLR语法完全相同的解析器状态表,其通常比纯LR解析表小一个数量级.但是,对于过于复杂而不能成为LALR的LR语法,这些合并状态会导致解析器冲突,或者生成不完全识别原始LR语法的解析器.
顺便说一下,我在这里的 MLR(k)解析表算法中提到了一些相关的东西.
附录
简短的回答是LALR解析表较小,但解析器机制是相同的.如果生成所有LR状态,则给定的LALR语法将产生更大的解析表,具有许多冗余(接近相同)状态.
LALR表较小,因为类似(冗余)状态被合并在一起,有效地丢弃了单独状态编码的上下文/先行信息.优点是您可以为相同的语法获得更小的解析表.
缺点是并非所有LR语法都可以编码为LALR表,因为更复杂的语法具有更复杂的前瞻,导致两个或更多个状态而不是单个合并状态.
主要区别在于,生成LR表的算法在状态到状态的转换之间传递更多信息,而LALR算法则没有.因此,LALR算法无法判断给定的合并状态是否应该真正保留为两个或多个单独的状态.
Pau*_*ann 12
又一个答案(YAA).
SLR(1),LALR(1)和LR(1)的解析算法与Ira Baxter所说的相同,
但是,由于解析器生成算法,解析器表可能不同.
SLR解析器生成器创建LR(0)状态机并根据语法(FIRST和FOLLOW集)计算前瞻.这是一种简化的方法,可以报告LR(0)状态机中实际不存在的冲突.
LALR解析器生成器创建LR(0)状态机并计算LR(0)状态机的预测(通过终端转换).这是一种正确的方法,但偶尔会报告LR(1)状态机中不存在的冲突.
Canonical LR解析器生成器计算LR(1)状态机,并且前瞻已经是LR(1)状态机的一部分.这些解析器表可能非常大.
最小LR解析器生成器计算LR(1)状态机,但在该过程期间合并兼容状态,然后计算来自最小LR(1)状态机的预测.这些解析器表与LALR解析器表的大小相同或略大,从而提供最佳解决方案.
LRSTAR 9.1可以在C++中生成最小LR(1)和LR(*)解析器.请参阅此图,其中显示了LR解析器之间的差异.
[完全披露:LRSTAR是我的产品]
使用 SLR 与 LR 生成的解析器表之间的基本区别在于，reduce 操作基于 SLR 表的 Follows 集。这可能过于严格，最终导致移位-归约冲突。
另一方面，LR 解析器仅基于实际上可以遵循被减少的非终端的终端集来进行减少决策。这组终端通常是此类非终端的 Follows 集的真子集，因此与移位操作发生冲突的可能性较小。
由于这个原因，LR 解析器更加强大。然而，LR 解析表可能非常大。
LALR 解析器从构建 LR 解析表的想法开始，但以一种显着减小表大小的方式组合生成的状态。缺点是，对于某些语法，LR 表可能会避免一些冲突，而这些冲突的可能性很小。
LALR 解析器的功能稍弱于 LR 解析器，但仍然比 SLR 解析器更强大。由于这个原因，YACC 和其他此类解析器生成器倾向于使用 LALR。
PS 为简洁起见，上面的 SLR、LALR 和 LR 实际上意味着 SLR(1)、LALR(1) 和 LR(1)，因此隐含了一个令牌前瞻。
假设没有前瞻的解析器很乐意为你的语法解析字符串.
使用您给出的示例它会遇到一个字符串dc,它会做什么？它是否会减少它S,因为dc这个语法产生的有效字符串是什么？或者也许我们试图解析,bdc因为即使这是一个可接受的字符串？
作为人类,我们知道答案很简单,我们只需要记住我们是否刚解析过b.但电脑是愚蠢的:)
由于SLR(1)解析器具有超过LR(0)的额外功率来执行前瞻,我们知道任何数量的前瞻都无法告诉我们在这种情况下该做什么; 相反,我们需要回顾过去.因此,规范的LR解析器来拯救.它记得过去的背景.
它记住这种情况的方式是它自我规范,每当它遇到一个时b,就会开始走上阅读的道路bdc,作为一种可能性.因此,当它看到d它知道它是否已经走了一条路.因此,CLR(1)解析器可以执行SLR(1)解析器无法做到的事情!
但是现在,因为我们必须定义这么多路径,所以机器的状态变得非常大!
因此,我们合并相同的路径,但正如预期的那样,它可能会引起混乱的问题.但是,我们愿意以降低规模为代价承担风险.
这是你的LALR(1)解析器.
现在该怎么做算法.
当您绘制上述语言的配置集时,您将在两种状态下看到shift-reduce冲突.要删除它们,您可能需要考虑一个SLR(1),它会根据后续内容做出决定,但您会发现它仍然无法做到.因此,您可以再次绘制配置集,但这次有一个限制,即无论何时计算闭包,添加的其他产品必须具有严格的跟随.请参阅任何教科书,了解应遵循的内容.