parsing - LL 解析器比 LR 解析器有什么优势？

Question

LL 解析器与 LR 解析器相比有哪些优势来保证它们在 today's parser generator tools 中的相对流行度？ ?

根据 Wikipedia , LR 解析似乎比 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”!)。

Answer 1

如果您想要一个解析树/森林并且不介意黑匣子，GLR 非常棒。它可以让你输入任何 CFG您希望通过详尽的测试在解析时检查歧义，而不是静态解决 LR/LALR 冲突。有人说这是一个很好的权衡。 Ira Baxter 的 DMS 工具或 Elkhound 具有免费的 C++ 语法，对此类问题很有用。 ANTLR对一大类语言应用程序也很有用，但使用自顶向下的方法，生成称为 LL(*) 的递归下降解析器，允许语义谓词。我将在这里不加证明地声明谓词允许您解析 CFG 之外的上下文相关语言。程序员喜欢在语法中插入 Action ，喜欢良好的错误处理，喜欢单步调试。 LL在这三个方面都很好。 LL 是我们手工做的，所以更容易理解。不信wikipedia nonsense about LR being better at handling errors .也就是说，如果您使用 ANTLR 进行大量回溯，LL(*) 的错误确实会更糟(PEG 有这个问题)。

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

GLR 是 O(n^3)最差的情况。 Packrat/PEG 是 O(n)最差的情况。 ANTLR 是 O(n^2)由于循环前瞻 DFA 但 O(n)在实践中。真的无所谓。 GLR 足够快。

ANTLR 是 安 其他 电话 工具 L 昂 R 认知不是反 LR，但我也喜欢那个 ;)

坦白说，和很多 80 年代的年轻程序员一样，我不了解 LALR，也不喜欢黑匣子(现在我挖掘了 GLR 引擎的美，但仍然更喜欢 LL)。我构建了一个基于 LL(k) 的商业编译器，并决定构建一个工具来生成我手工构建的内容。 ANTLR 并不适合所有人，像 C++ 这样的边缘情况用 GLR 可能会更好地处理，但很多人发现 ANTLR 适合他们的舒适区。自 2008 年 1 月以来，ANTLRWorks 中的 ANTLR 二进制 jar 和源 zip 的总下载量已达到 134,000 次(根据 Google Analytics)。见 our paper在 LL(*) 上有大量的经验数据。