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?，但带有一些例子会更好。）

- K J

Answer 1

LR解析器比LL解析器更强大，而且LALR解析器可以像LL解析器一样以O(n)的速度运行。因此，你不会在LL解析器中找到任何功能上的优势。

因此，LL唯一的优点是LR状态机要复杂得多，难以理解，而LR解析器本身也不太直观。另一方面，自动生成的LL解析器代码非常易于理解和调试。

- Puppy

---

感谢您的意见，DeadMG。 - K J

Answer 2

我认为LL分析器最大的优势在于它们非常易于理解和实现！您可以手写递归下降解析器，代码与语法非常相似。

LR通常被认为更强大，而且速度更快，但我知道有一些权衡：

LR解析器只能使用合成属性；不能传递继承属性。

LR语法中的操作可能导致语法不确定性，但LL不会。

然而，您会发现LL(*)也非常强大。

- Austin Henley

---

如果有人把解析器生成器交给你，根据定义它所做的事情是“易于实现”的。在这种情况下，您选择最容易处理最大类语言的解析器生成器，以最小化您的工作量。从这个角度来看，我认为LR胜过LL。GLR胜过LR。 - Ira Baxter

我同意，但是尽管如此，LL（左向右扫描）仍然很容易实现。我指出LR（右向左扫描）通常需要使用工具。我觉得很有趣的是你可以手写递归下降解析器，代码和文法紧密配合。 - Austin Henley

是的，这很有趣，构建解析器的人应该了解它们。随着语法规则变得越来越复杂，强制将其转换为LL形式会很不方便，而在某个（相当小的）点上，LR的便利性胜过了你脑海中概念上的简单性。如果你不是在构建解析器生成器，那么理解LR是相当容易的，并且并不像没有很多这样的工具。 - Ira Baxter

当然，你是编译器专家，你说得对。 - Austin Henley

感谢Ira和Austin的回答。我同意Ira的观点，我更喜欢LR而不是LL，但Austin关于继承属性和动作的观点也很有帮助。 :) - K J

从版本4开始，ANTLR可以处理直接左递归。 - Weltraumschaf