一个LL和递归下降分析器之间的区别是什么？(Difference between an LL and

我最近正在试图教我自己解析器（用于语言/上下文无关文法）是如何工作的，而且大部分似乎是决策意识，除了一两件事。我注重我的注意，尤其是在LL（k）的语法 ，为其两个主要算法似乎是LL解析器 （使用堆栈/解析表）和递归下降解析器 （只需使用递归）。

据我所看到的，递归下降算法适用于所有的LL（k）的语法和可能更多，而一个LL解析器适用于所有的LL（k）的语法。递归下降解析器显然比一个LL解析器然而实现，（只是作为一个LL一个比一个LR一个简单的）要简单得多。

所以我的问题是，有什么优点/问题无论使用的算法时，一个可能遇到的？为什么会一个接过了LL递归下降，因为它可以在同一套语法，是麻烦来实现？

LL通常比递归下降更有效的分析技术。事实上，幼稚递归下降语法分析器实际上是O（K ^ n）（其中n是输入大小）在最坏的情况下。一些技术，诸如记忆化（这产生Packrat解析器）可以改善这个问题，以及扩展的类被解析器接受语法，但总是有一个空间折衷。 LL解析器（据我所知）总是线性的时间。

在另一面，你在你的直觉，递归下降解析器可以处理更大的类文法比LL是正确的。递归下降可以处理任何语法是LL（*）（即，无限先行）以及一个小的组暧昧语法。这是因为递归下降实际上是PEG的直接编码实现，或者解析器表达式语法（一个或多个）。具体而言，析取操作者（ a | b ）是不可交换的，这意味着a | b a | b不等于b | a b | a 。递归下降分析器将试图以每个替代。所以，如果a输入相匹配，它会succede即使b 会匹配的输入。这让像悬空经典的“最长匹配”含糊else问题通过正确排序析取简单地处理。

与所有的所述，能够实现使用递归下降的LL（k）的解析器，使得其以线性时间运行。这是通过基本上内联，使得每个解析例程确定在恒定时间给定的输入相应的生产的预测套来完成。不幸的是，这种技术消除了从所处理的整个类文法。一旦我们进入预测分析，像晃来晃去的问题else不再有解如此轻而易举。

至于为什么会LL在递归下降的选择，这主要是效率和可维护性的问题。递归下降解析器明显更容易实现，但他们通常是难以维持，因为他们所代表的语法不以任何声明的形式存在。最不平凡的解析器使用情况采用解析器生成如ANTLR或野牛。利用这些工具，它真的并不重要，如果该算法是直接编码的递归下降或表驱动LL（K）。

由于利益的问题，这也是值得探讨递归上升，这是递归下降的时装后直接编码的分析算法，但是能够处理任何LALR语法。我还要深入到解析器组合，这是构成递归下降解析器在一起的功能方式。