Ada*_*ter 31 parsing lalr parser-generator ll-grammar lr-grammar
LL解析器比LR解析器有什么优势可以保证它们在今天的解析器生成器工具中相对流行？
根据维基百科,LR解析似乎比LL更有优势:
LR解析可以处理比LL解析更大范围的语言,并且在错误报告方面也更好,即它在输入不尽快符合语法时检测语法错误.这与LL(k)(或甚至更糟的LL(*)解析器)形成对比,LL(k)可能由于回溯而将错误检测推迟到语法的不同分支,通常使错误难以在具有长公共前缀的分离上进行本地化. .
注意:这不是作业.当我发现Antlr是一个LL解析器生成器(尽管名字中有"LR")时,我感到很惊讶.
Ter*_*arr 31
如果你想要一个解析树/森林并且不介意黑盒子,那么GLR是很棒的.它允许您输入任何您想要的CFG,代价是通过详尽的测试来检查分析时的歧义,而不是静态地解决LR/LALR冲突.有人说这是一个很好的权衡.Ira Baxter的DMS工具或具有免费C++语法的Elkhound对这类问题很有用.ANTLR对于大类语言应用程序也很有用,但是使用自上而下的方法,生成称为LL(*)的递归下降解析器,允许语义谓词.我将在此处说明,谓词允许您解析超出CFG的上下文敏感语言.程序员喜欢将动作插入到语法中,例如良好的错误处理,以及单步调试.LL擅长三种.LL是我们手工操作的,因此更容易理解.不要相信维基百科关于LR更好地处理错误.也就是说,如果你使用ANTLR回溯很多,LL(*)(PEGs有这个问题)的错误确实更糟.
重新回溯.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是AN其他Ť OOL为大号 ANG ř ecognition不是反LR,但我喜欢一个太;)
坦率地说,就像80年代的很多年轻编码员一样,我不理解LALR并且不喜欢黑盒子(现在我挖掘了GLR引擎的美感但仍然喜欢LL).我构建了一个基于商业LL(k)的编译器,并决定构建一个工具来生成我手工构建的内容.ANTLR并不适合所有人,而像C++这样的边缘情况可能会更好地处理GLR,但很多人发现ANTLR适合他们的舒适区.自2008年1月以来,在ANTLRWorks中已经有134,000个ANTLR二进制jar下载量和源拉链总数(根据谷歌分析).请参阅我们关于LL(*)的论文,其中包含大量经验数据.
Ira*_*ter 12
如果你必须手动编码,递归下降(LL)是你可以现实地做的事情; 人们不能手工制作L(AL)R解析器.
鉴于现代解析器生成器将为您处理所有解析器构造,并且该空间不是一个问题,我更喜欢LR解析器,因为您不必与语法争用,以使它们对您的特定解析器生成器有效(没有"删除所有左递归"的愚蠢).
事实上,我更喜欢GLR解析器,它几乎可以用无上下文语法解析任何东西.没有左递归的担忧.没有转变/减少冲突的担忧.没有前瞻性的限制.
如果你想看到一个 GLR解析引擎可以处理的语言范围(包括着名的难以解析的LL/LALR语言,C++),你可以看看这里.