问LL算法的分类学问题

EN

递归下降允许您实现一定范围的正式解析器。例如，它允许开发LL(k)解析器。在LL的情况下，递归下降不需要回溯，也就是说，考虑到LL的性质，解析器不会意识到它遗漏了一些解析规则。另一方面，递归下降还允许您实现使用回溯的解析器。因此，您可以使用回溯或不使用，并且可以使用递归下降来收集一系列解析器家族。

递归下降没有内置的效率保证。这取决于您的代码和您正在解决的问题。C语言族的clang解析器是递归的，进行回溯，作者认为它是解析C语言的正确方法。

我不确定关于预测解析的术语，wikipedia建议它是一个递归下降解析器，不能回溯，就像上面的例子一样，但是这种情况被称为预测递归下降解析器更有意义。有一些课堂讲义表明，预测解析器不隐式地使用堆栈来保存解析器状态。例如，在这种情况下，预测解析器使用显式托管堆栈，可能是由具有解析规则的表驱动的。

鉴于递归下降和预测解析作为两种解析实现技术之间的对比，我认为递归解析器是一种使用递归函数(并隐式使用堆栈)实现解析器的方法，而预测解析是一种使用表和显式堆栈实现解析器(但不使用递归函数)的方法。预测递归下降表明存在一个使用表和递归函数的解析器，这在我看来很奇怪。最糟糕的情况是，预测递归下降解析器是一个递归下降解析器(而不是一个预测解析器)，它没有回溯，有一个丑陋的名字。

概念性LL解析器既可以转换为递归下降解析器(即一组递归函数)，它不会执行任何回溯，因为LL不需要它，也可以转换到预测解析器(即while循环+堆栈+表)。

学习递归下降解析器的最佳方法是执行万花筒语言教程：http://llvm.org/docs/tutorial/LangImpl2.html

parser

parser

Are GCC and Clang parsers really handwritten?

http://www.cs.purdue.edu/homes/xyzhang/spring09/notes/ll.pdf

预测解析器是以多种形式出现的一个通用的解析器家族(LL和LR解析器是比较突出的例子)。预测解析器通常通过使用解析当前状态的一些知识来“预测”要使用哪些产品(或应用哪些简化)。例如，在LL解析中，解析器试图根据当前的非终端和接下来的几个输入字符来预测要应用的产品。在LR解析中，预测是根据输入的下一个终端和解析器的当前配置，在特定的时间点执行哪些缩减(如果有的话)。

许多(但不是所有)预测解析器都是表驱动的。LR解析器通常使用表来实现，就像一些LL解析器一样，尽管情况并不总是这样。许多LL解析器是使用递归下降实现的，而许多LR解析器是使用递归上升实现的。

递归下降解析通常是指自上而下的解析算法，通过对每个终端和非终端具有不同的递归函数来猜测要使用的结果。它们通常基于语法使用一定量的回溯，而在左递归语法上通常失败。通常，手写LL解析器是使用递归下降编写的，没有回溯，这是可能的，因为语法是专门构造的，不需要任何回溯。这是预测递归下降。

通过回溯，递归下降可能会非常低效率。通常，您不会在需要这样回溯的语法上使用递归下降。

希望这能有所帮助！