parsing - LL 和递归下降解析器之间的区别？

Question

我最近试图自学解析器(用于语言/上下文无关语法)如何工作，除了一件事之外，大多数内容似乎都是有意义的。我特别关注 LL(k) 语法，其中两个主要算法似乎是 LL parser (使用堆栈/解析表)和 Recursive Descent parser (简单地使用递归)。

据我所知，递归下降算法适用于所有 LL(k) 语法，甚至可能更多，而 LL 解析器适用于所有 LL(k) 语法。然而，递归下降解析器的实现显然比 LL 解析器简单得多(就像 LL 解析器比 LR 解析器简单一样)。

所以我的问题是，使用这两种算法时可能会遇到哪些优点/问题？为什么人们会选择 LL 而不是递归下降，因为它适用于同一组语法并且实现起来更棘手？

Answer 1

LL 通常是比递归下降更有效的解析技术。事实上，在最坏的情况下，一个简单的递归下降解析器实际上将是 O(k^n) (其中 n 是输入大小)。一些技术，例如内存(产生 Packrat 解析器)可以改进这一点，并扩展解析器接受的语法类，但总是存在空间权衡。 LL 解析器(据我所知)始终是线性时间。

另一方面，您的直觉是正确的，即递归下降解析器可以处理比 LL 更大的语法类。递归下降可以处理任何 LL(*) 语法(即无限前瞻)以及一小组模糊语法。这是因为递归下降实际上是 PEG 的直接编码实现，或 Parser Expression Grammar(s) 。具体来说，析取运算符 (a | b) 不可交换，这意味着 a | b b 不等于 b |一个。递归下降解析器将按顺序尝试每个替代方案。因此，如果 a 与输入匹配，即使 b 与输入匹配，它也会成功。这使得经典的“最长匹配”歧义(例如悬空 else 问题)只需通过正确排序析取即可得到处理。

综上所述，使用递归下降实现 LL(k) 解析器是可能的，这样它就能以线性时间运行。这是通过本质上内联预测集来完成的，以便每个解析例程在恒定时间内确定给定输入的适当产生式。不幸的是，这种技术消除了对整个语法类的处理。一旦我们进入预测解析，像悬挂 else 这样的问题就不再那么容易解决了。

至于为什么选择LL而不是递归下降，主要是效率和可维护性的问题。递归下降解析器明显更容易实现，但它们通常更难维护，因为它们表示的语法不以任何声明形式存在。大多数重要的解析器用例都会使用解析器生成器，例如 ANTLR 或 Bison。有了这样的工具，算法是直接编码的递归下降还是表驱动的 LL(k) 并不重要。

出于兴趣，也值得研究一下recursive-ascent ，这是一种按照递归下降方式直接编码的解析算法，但能够处理任何 LALR 语法。我还会深入研究 parser combinators ，这是一种将递归下降解析器组合在一起的函数方式。