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

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

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

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

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

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