parsing - LALR 与 LL 解析器

Question

我一直在使用 lex/yacc，现在我正在尝试切换到 ANTLR。主要问题是 ANTLR 是一个 LL(*) 解析器，而 yacc 是 LALR。我习惯于自下而上地思考，我并不完全知道 LL 语法的优势是什么。人们说现在 LL 语法更容易理解并且更受欢迎。但似乎 LR 解析器更强大，例如LL 解析器无法处理左递归，尽管似乎有一些解决方法。

所以问题是 LL 语法相对于 LALR 的优势是什么？如果有人能给我一些例子，我将不胜感激。指向有用文章的链接也很棒。

提前感谢您的帮助!

(我看到这是一个很好的资源:What advantages do LL parsers have over LR parsers?，但如果有一些例子会更好。)

Answer 1

LR 解析器严格来说比 LL 解析器更强大，此外，LALR 解析器可以像 LL 解析器一样在 O(n) 中运行。所以你不会发现 LL 比 LR 有任何功能优势。

因此，LL 的唯一优点是 LR 状态机相当复杂且难以理解，并且 LR 解析器本身并不是特别直观。另一方面，自动生成的 LL 解析器代码非常容易理解和调试。