LL解析器相对于LR解析器有哪些优势?

38
LL解析器在今天的解析器生成工具中相对流行的原因是什么优势?
根据维基百科,LR分析似乎比LL分析有优势:
LR分析可以处理比LL分析更广泛的语言,并且在错误报告方面也更好,即当输入不符合语法时,它尽可能早地检测到语法错误。这与LL(k)(甚至更糟的是LL(*)解析器)形成对比,后者可能由于回溯而将错误检测推迟到语法的另一个分支中,通常使得跨越具有长公共前缀的分歧的错误更难以定位。
注意:这不是作业。当我发现Antlr是一个LL解析器生成器(尽管其名称中有“LR”!)时,我感到惊讶。

谈到解析器(而不是语法):LL(*)可以用简单的递归下降方法编写。在我的书中,这是+1。 - user166390
@pst:没错,我只是希望“因为它们更容易实现”不是主要优势。 :) - Adam Paynter
3
请注意,ANTLR中的“LR”仅代表“语言识别”,与其接受的语法类别无关。 - Jerry Coffin
4
实际上,在Terrence Parr的心中,它代表“Anti-LR”。我记得他接受采访时承认这个内涵不是偶然的。他说自己创建ANTLR的原因是因为他觉得过于强调LR解析是一个很大的错误,而且他已经厌烦了告诉每个人LR很糟糕却没有人听他的话,所以他决定创建世界上最好的解析器生成器,摧毁所有其他的生成器,只留下LL…或者类似的东西。 - Jörg W Mittag
@Jörg:真的吗?哇,那肯定是雄心勃勃的!听起来Terrence肯定有话要说!也许我应该给他发封电子邮件,征求他的意见... - Adam Paynter
1
@Jörg:我刚给他发了电子邮件,邀请他参加这个讨论。他可能很忙,但也许他还会加入进来! - Adam Paynter
7个回答

36

如果你需要一个解析树/森林并且不介意黑匣子,那么GLR是很好的选择。它允许你输入任何你想要的CFG,但代价是在解析时通过详尽的测试检查歧义,而不是静态地解决LR/LALR冲突。有人说这是一个好的权衡。Ira Baxter的DMS工具或者有免费C++语法的Elkhound对于这类问题也是有用的。ANTLR也适用于大量的语言应用,但采用自顶向下的方法,生成递归下降解析器称为LL(*),允许语义谓词。我在这里声明没有证据表明谓词允许您解析超越CFG的上下文敏感语言。程序员喜欢在语法中插入操作,如良好的错误处理,并喜欢单步调试。LL在这三个方面都很好。 LL是我们手动处理的,因此更容易理解。不要相信维基百科关于LR处理错误更好的胡说八道。话虽如此,如果你在ANTLR中反复回溯,LL(*)的错误确实比较严重(PEG也有这个问题)。

重新回溯。GLR也像PEG、ANTLR和其他非确定性策略一样进行推测(即回溯)。在任何非确定性LR状态下,GLR“分叉”子解析器以尝试任何可行路径。无论如何,LL对于错误处理具有良好的上下文。在LR知道它正在匹配表达式时,LL知道它是赋值或IF条件中的表达式;LR知道它可能在任何一个位置但不确定——这种不确定性是它获得力量的地方。

GLR的最坏情况是O(n^3)。packrat/PEG的最坏情况是O(n)。ANTLR的最坏情况是O(n^2),由于循环前瞻DFA而在实践中为O(n)。其实并不重要。GLR足够快。

ANTLRANother Tool for Lang Recognition,而不是反-LR,但我也喜欢那个 ;)

坦白地说,像80年代许多年轻的编程人员一样,我不理解LALR并且不喜欢黑盒子(现在我深深地理解GLR引擎的美妙之处,但仍然更喜欢LL)。我构建了一个基于商业LL(k)的编译器,并决定构建一个工具来生成我手动构建的内容。ANTLR并不适合所有人,像C++这样的边缘情况可能更适合使用GLR,但很多人发现ANTLR适合他们的舒适区。自2008年1月以来,ANTLR的二进制jar文件已经被下载了134,000次,包括在ANTLRWorks中和源代码zip文件总计(根据Google Analytics)。请参见我们的论文,其中包含大量实证数据关于LL(*)。


1
我当然欣赏逐行调试的能力!我也很欣赏“上下文”的概念(即,知道被解析的表达式包含在一个 if 语句中)。感谢您的答案,它确实展示了 LL 解析器的一些优点! - Adam Paynter
3
所有人:我同意ANTLR和大多数解析器生成器确实适用于构建“适度”语法的解析器。当语法变得“棘手”时就会出现区别。如果您控制语法并可以更改它以消除棘手的情况,那么任何解析器生成器都可以使用。如果您不能,则解析器生成器的强度真的很重要。在任一情况下,支持工具的工程真正有帮助。尽管我偏向于GLR(它们在实践中也是O(n)!),但我将首先承认Terence在使ANTLR有效方面做得相当不错。 - Ira Baxter
2
@Ira:我只是想说GLR是一个黑盒子,因为它可以工作但不透明。另一个极端是递归下降解析器(由ANTLR生成),它不是一个黑盒子,因为它是程序员手工构建的,可以进行单步调试。实际上,这并不完全正确。LL(*)允许循环DFA向前扫描,我为那些决策生成状态机(黑盒),但那只是针对替代产生预测而不是解析。 - Terence Parr
通常的技巧是尝试从错误点之后的标记构建树,然后寻找一个标记插入/删除,使解析器能够填补间隙。(我们只使用下一个标记,因为我们在推动错误恢复方面并不活跃)。即使对于不一致的状态,这也非常有效。大多数状态都不一致,因此只有一个合理的继续。如果存在多个可能的下一个解析,为什么LL解析器没有相同的问题?即使您切换了解析技术,本地语言歧义也不会消失。 - Ira Baxter
2
一则更新。即将到来的 OOPSLA '14 论文,关于自适应 LL()、ALL(),可以处理任何语法,唯一的例外是没有间接左递归。处理 e : e '*' e | INT ; 规则文件 http://www.antlr.org/papers/allstar-techreport.pdf ALL(*) 是我对解析的最终见解。25 年后,我终于破解了它。拿出 C11 规范,包括左递归,尽管在不调整语法的情况下,解析速度缓慢。Java 语法解析器有 12,920 个文件,3.6M 行,大小为 123M 的 Java 库,在 <6 秒内完成。请参阅论文中的工具对比。GLR 工具需要对数刻度或单独的图表。 - Terence Parr
显示剩余5条评论

12
如果你必须手动编写一个解析器,那么递归下降(LL)是一种你可以实现的方法;人们无法手工制作L(AL)R解析器。

考虑到现代解析器生成器将为您处理所有解析器构建工作,而空间并不是太大的问题,我更喜欢LR解析器,因为您不必与语法斗争,使它们对于特定的解析器生成器有效(没有“删除所有左递归”之类的傻事)。

事实上,我更喜欢GLR解析器,它几乎可以解析任何上下文无关文法。没有左递归的烦恼。没有移位/规约冲突的烦恼。没有前瞻限制。

如果您想看到一个 GLR解析引擎可以处理的语言范围(包括使用LL/LALR语言难以解析的著名的C++),您可以看这里


2
LALR的存在是因为对于许多实际语法,可以得到比LR更小的表。虽然在实践中没有人这样做,但你当然可以定义LALR(3)语法的概念。GLR的原因是你可以停止考虑K。 - Ira Baxter
2
@Adam:维基百科网站上的参考资料是必读的,但很难找到“免费”的;我在多年前获得了印刷版。Adrian Johnstone似乎正在做大量关于高级GLR解析的工作,例如:http://portal.acm.org/citation.cfm?id=1149674。如果你是ACM会员,这是免费的。他的网站http://www.cs.rhul.ac.uk/research/languages/publications/aj_publications.html可能具有可自由访问的文档。 - Ira Baxter
我真的希望这不会让人感到敌对——这是一个诚实的问题——在实践中,什么时候左递归是有用/必要的?我的意思并不是说它没有用处/必要性,只是我从来没有看到过任何左递归的用途,不能用“*”或“+”量词替换。我相信有有效的用途,但我不熟悉其中任何一个。 - Matt Fenwick
*或+不是标准的BNF规则。它们在许多扩展BNF规则中是标准的。如果您的解析器生成器没有这些功能,则需要左递归或右递归。如果您拥有它们,则对应于左递归或右递归。如果您从语法生成解析器,通常EBNF基本上会被简化为BNF(对于LR类解析器来说肯定如此),并且您希望使用左递归,因为它使解析器更有效;对于这样的解析器,使用右递归,您必须拥有与列表长度一样深的堆栈。... - Ira Baxter
2
自上而下实现的解析器可以将 Kleene 运算符从逻辑右递归转换为循环操作。但是人们仍然可以以复杂的方式编写涉及左递归的规则;我手头没有例子,但我很高兴知道我不必担心如何编写语法规则。如果您查看人们对自上而下解析器(即使是带有 Kleene 星号符号的解析器)的抱怨,几乎总是会发现他们试图找到一种方法来摆脱某些不方便的左递归。为什么要担心呢? - Ira Baxter
显示剩余11条评论

3
从个人经验来看(我在各种情况下都使用过这两种方法),最实用的区别是,使用LL(k)可以更容易地定义语法(因为它是自顶向下的),而不必担心LR解析器经常出现的许多可能的reduce-reduce或shift-reduce冲突。唯一需要关注的是左递归,必须转换为右递归。
另一个问题是,自顶向下的方法通常意味着更高的复杂度(无论是空间还是时间方面),因为它在解析时必须存储整个树,并且直到消除歧义之前,它可能会增长很多。

只是为了我理解...你的意思是LL解析器避免了通常在LR解析器中发现的冲突,这是最实用的区别。这是否仅适用于将其前瞻限制为较小数量(例如,LR(1)或LALR(1))的LR解析器?我认为LR(k)解析器没有那么多冲突... - Adam Paynter

1
根据劳伦斯·特拉特(Laurence Tratt)的说法,LL解析器有一个小但重要的领域,即如果您需要:

最高性能和/或最佳错误消息。

并手动编写递归下降解析器来实现它。

对于一个现实的编程语言语法,通常需要数个人月的工作才能打败自动生成的解析器。

然而:

LL解析器在很大程度上不受欢迎,因为缺乏左递归使得表达许多标准编程语言结构变得笨拙。

因此,他的结论是处理左递归非常出色的LR解析是正确的选择。

关于这个问题的更详细评论,我推荐劳伦斯·特拉特(Laurence Tratt)的优秀文章“哪种解析方法?”


1

我所熟悉的唯一优点就是你可以轻松地手工编写LL解析器。而手工编写LR解析器要困难得多(通常会使用解析器生成器)。


2
当你拥有这样的生成器时,生成它们是非常容易的。 - Ira Baxter

1

0

一个想到的原因是,在LL范式中,更容易处理需要任意回溯(咳咳,C++)的语言。


Cough C++不需要任意回溯。GLR解析器可以很好地完成这项工作。请查看我的答案。 - Ira Baxter
我的意思是,由于声明/表达式的歧义,C++对于任何有限的k都不是LL(k)或LR(k)。 - zwol
1
在纯粹的意义上解析C++(而不是GCC在解析时解决类型的hack),需要解析器也能够捕捉到模棱两可的解析。LL/LR解析器无法做到这一点,但GLR解析器可以。您可以使用符号表信息稍后解决歧义,从而使解析与名称和类型解析分离,从而获得更清晰的解析器。 - Ira Baxter
@Zack和@Ira:多么有趣的对话! - Adam Paynter
我不太懂理论,但我曾经在C++的GCC和EDG前端工作过,并且我认为避免您描述的“解析期间解决类型”技巧是不切实际的。当然,这两个前端都是手工编写的递归下降分析器,具有回溯功能,所以也许这只是实现技术的结果。是否有人为C ++编写了完整的GLR分析器? - zwol
1
@Zack:请看我的回答。点击链接。是的。我们完全避免了那个黑客攻击。我们使用它来修改大规模的C++系统。 - Ira Baxter

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接