LL和recursion下降parsing器之间的区别？
最近我正在试图自学自己的parsing器（语言/上下文无关文法）是如何工作的，大部分似乎是有意义的，除了一件事情。 我将注意力集中在LL（k）语法 ，其中两种主要algorithm似乎是LL语法分析器 （使用堆栈/分析表）和recursion下降语法分析器 （简单地使用recursion）。
就我所见，recursion下降algorithm适用于所有LL（k）语法，可能更多，而LLparsing器适用于所有LL（k）语法。 然而，recursion下降parsing器显然要比LLparsing器更简单（就像一个LLparsing器比LRparsing器一样简单）。
所以我的问题是，使用任何一种algorithm时可能遇到的优点/问题是什么？ 为什么有人会selectrecursion下降的LL，因为它在同一组语法上工作，而且更难实现？
LL通常比recursion下降更有效的parsing技术。 事实上，在最坏的情况下，一个天真的recursion下降parsing器实际上是O（k ^ n） （其中n是input大小）。 一些技术，比如memoization （产生一个Packratparsing器）可以改善这个以及扩展parsing器接受的语法类，但总是有一个空间折衷。 LL分析器（就我所知）总是线性时间。
另一方面，你的直觉是正确的：recursion下降parsing器可以处理比LL更大的语法类。 recursion下降可以处理任何LL（*）（也就是无限的前瞻）语法以及一小组模糊的语法。 这是因为recursion下降实际上是PEG的直接编码实现，或者是parsing器expression式语法 。 具体来说，析取运算符（ a | b ）是不可交换的，这意味着a | b a | b不等于b | a b | a 。 recursion下降parsing器将按顺序尝试每个select。 所以如果a匹配的input，它将成功，即使b 将匹配input。 这就允许经典的“最长匹配”模糊，像悬摆else问题，只需通过正确sorting来解决。
综上所述，有可能使用recursion下降来实现一个LL（k）parsing器，以便它以线性时间运行。 这通过基本内联预测集来完成，以便每个parsing例程在恒定时间内确定给定input的适当生产。 不幸的是，这样的技术消除了整个语法类别的处理。 一旦我们进入预测分析， else悬而未决的问题就不再容易解决了。
至于为什么selectLL而不是recursion下降，这主要是一个效率和可维护性的问题。 recursion下降parsing器明显易于实现，但是它们通常难以维护，因为它们表示的语法不存在于任何声明式表单中。 大多数不重要的parsing器用例都使用parsing器生成器，如ANTLR或Bison。 有了这样的工具，如果algorithm是直接编码的recursion下降或表驱动LL（k），真的没有关系。
作为一个感兴趣的问题，也值得研究recursion上升 ，这是一种直接按recursion下降方式编码的parsingalgorithm，但能够处理任何LALR语法。 我还将深入parsing器组合器 ，这是一个组合recursion下降parsing器的function方式。
