根据维基百科,LR分析似乎比LL分析有优势:
LR分析可以处理比LL分析更广泛的语言,并且在错误报告方面也更好,即当输入不符合语法时,它尽可能早地检测到语法错误。这与LL(k)(甚至更糟的是LL(*)解析器)形成对比,后者可能由于回溯而将错误检测推迟到语法的另一个分支中,通常使得跨越具有长公共前缀的分歧的错误更难以定位。
注意:这不是作业。当我发现Antlr是一个LL解析器生成器(尽管其名称中有“LR”!)时,我感到惊讶。
如果你需要一个解析树/森林并且不介意黑匣子,那么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足够快。
ANTLR是ANother 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(*)。
if
语句中)。感谢您的答案,它确实展示了 LL 解析器的一些优点! - Adam Payntere : 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最高性能和/或最佳错误消息。
并手动编写递归下降解析器来实现它。
对于一个现实的编程语言语法,通常需要数个人月的工作才能打败自动生成的解析器。
然而:
LL解析器在很大程度上不受欢迎,因为缺乏左递归使得表达许多标准编程语言结构变得笨拙。
因此,他的结论是处理左递归非常出色的LR解析是正确的选择。
关于这个问题的更详细评论,我推荐劳伦斯·特拉特(Laurence Tratt)的优秀文章“哪种解析方法?”
我所熟悉的唯一优点就是你可以轻松地手工编写LL解析器。而手工编写LR解析器要困难得多(通常会使用解析器生成器)。
一个想到的原因是,在LL范式中,更容易处理需要任意回溯(咳咳,C++)的语言。