18

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

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

提前感谢您的帮助！

（我看到这是一个很好的资源：LL 解析器比 LR 解析器有什么优势？，但如果有一些例子会更好。）

4

2 回答 2

17

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

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

于 2012-08-29T04:41:21.653 回答
13

我看到 LL 解析器的最大优势是它们很容易理解和实现！您可以使用与语法非常匹配的代码手动编写递归下降解析器。

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

  • LR解析器只能使用合成属性；他们不能传递继承的属性。
  • LR 语法中的动作会导致语法不确定性，但在 LL 中不会。

但是，您会发现 LL(*) 也非常强大。

于 2012-08-29T04:38:17.150 回答