与LR解析器相比，LL解析器有什么优势? [英] What advantages do LL parsers have over LR parsers?

问题描述

与今天的解析器生成器工具相比，LL解析器相对于LR解析器具有什么优势，以保证其在今天的解析器生成工具中的相对流行?

What advantages do LL parsers have over LR parsers to warrant their relative popularity in today's parser generator tools?

根据维基百科，LR解析似乎比LL具有优势:

According to Wikipedia, LR parsing appears to have advantages over LL:

LR解析比LL解析可以处理更大范围的语言，并且在错误报告方面也更好，即，当输入不尽快符合语法时，它可以检测语法错误.这与LL(k)(或更糟糕的是，LL(*)解析器)形成对比，后者可能由于回溯而将错误检测推迟到语法的不同分支，这通常会使错误更难以定位在具有较长公共前缀的析取词之间

LR parsing can handle a larger range of languages than LL parsing, and is also better at error reporting, i.e. it detects syntactic errors when the input does not conform to the grammar as soon as possible. This is in contrast to an LL(k) (or even worse, an LL(*) parser) which may defer error detection to a different branch of the grammar due to backtracking, often making errors harder to localize across disjunctions with long common prefixes.

注意:这不是家庭作业.当我发现Antlr是LL解析器生成器(尽管名称中带有"LR"！)时，我感到非常惊讶.

Note: This is not homework. I was just surprised when I found out that Antlr is an LL parser generator (despite having "LR" in its name!).

推荐答案

如果您想解析树/林并且不介意黑匣子，则GLR非常有用.它可以让您输入您想要的任何 CFG 通过详尽的测试在解析时检查歧义的成本，而不是静态地解决LR/LALR冲突.有人说这是一个很好的权衡. Ira Baxter的DMS工具或Elkhound(具有免费的C ++语法)对于此类问题很有用. ANTLR 对于大量的语言应用程序也很有用，但使用自顶向下的方法，生成递归下降解析器称为LL(*)的允许语义谓词.在此我将不作任何证明，指出谓词可让您解析CFG以外的上下文相关语言.程序员喜欢将动作插入语法中，例如良好的错误处理，并且喜欢单步调试. LL在这三个方面都很擅长. LL是我们手工完成的，因此更容易理解.不要相信维基百科关于LR能够更好地处理错误的废话.就是说，如果您大量使用ANTLR进行回溯，LL(*)的错误确实会更加严重(PEG存在此问题).

GLR is great if you want a parse tree/forest and don't mind black boxes. It lets you type in whatever CFG you want at the cost of checking for ambiguities at parse time via exhaustive testing, instead of resolving LR/LALR conflicts statically. Some say that's a good trade-off. Ira Baxter's DMS tool or Elkhound, which has a free C++ grammar, are useful for this class of problem. ANTLR is useful for a large class of language applications too, but uses a top-down approach, generating recursive descent parsers called LL(*) that allow semantic predicates. I will state without proof here that predicates allow you to parse context-sensitive languages beyond CFGs. Programmers like to insert actions into grammars, like good error handling, and like to single-step debug. LL is good at all three. LL is what we do by hand so it's easier to understand. Don't believe the wikipedia nonsense about LR being better at handling errors. That said, if you backtrack a lot with ANTLR, errors are indeed worse with LL(*) (PEGs have this problem).

重新回溯.就像PEG，ANTLR和其他任何不确定性策略一样，GLR也进行推测(即回溯).在任何不确定的LR状态下，GLR都会分叉"子解析器以尝试任何可行的路径.无论如何，LL为错误处理提供了良好的环境. LR知道它与表达式匹配时，LL知道它是赋值或IF-条件表达式； LR知道可能会出现这种情况，但不确定-不确定性是它获得动力的地方.

Re backtracking. GLR speculates (i.e. backtracks) too, just like PEGs, ANTLR, and any other non-deterministic strategy. At any non-deterministic LR state, GLR "forks" sub-parsers to try out any viable path. Anyway, LL has good context for error handling. Where LR knows it's matching an expression, LL knows it's an expression in an assignment or IF-conditional; LR knows it could be in either but isn't sure - and that uncertainty is where it gets its power.

GLR是O(n^3)最坏的情况. packrat/PEG是最坏的情况.由于循环先行DFA，ANTLR为O(n^2)，但实际上为O(n).真的没关系. GLR足够快.

GLR is O(n^3) worst case. packrat/PEG is O(n) worst case. ANTLR's are O(n^2) due to cyclic lookahead DFA but O(n) in practice. Doesn't matter really. GLR is fast enough.

ANTLR 是 L ang R 识别的 AN 其他 T 抗LR，但我也喜欢那个；)

ANTLR is ANother Tool for Lang Recognition not anti-LR, but I like that one too ;)

坦率地说，就像许多80年代的年轻编码员一样，我不理解LALR，也不喜欢黑匣子(现在我挖掘了GLR引擎的魅力，但仍然更喜欢LL).我构建了一个基于LL(k)的商业编译器，并决定构建一个工具来生成我手工构建的内容. ANTLR并非适合所有人，并且使用CLR可能会更好地处理C ++之类的极端情况，但是许多人发现ANTLR可以满足他们的舒适要求.自2008年1月以来，在ANTLRWorks中已经有134,000次ANTLR二进制jar的下载，并且源zip总计(根据Google Analytics(分析)).参见我们关于LL(*)的论文，其中包含大量经验数据.

Frankly, like a lot of young coders in 80s, I didn't understand LALR and didn't like black boxes (now I dig the beauty of the GLR engine but still prefer LL). I built a commercial LL(k) based compiler and decided to build a tool to generate what I had built by hand. ANTLR isn't for everyone and edge cases like C++ might be better handled with GLR but a lot of people find ANTLR fits into their comfort zone. Since Jan 2008, there have been 134,000 downloads of ANTLR's binary jar, within ANTLRWorks, and source zips total (according to Google Analytics). See our paper on LL(*) with lots of empirical data.

这篇关于与LR解析器相比，LL解析器有什么优势?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！