parsing - LL 算法分类问题

Question

我正在研究上下文无关语法，并且我陷入了第一步:了解自顶向下解析算法的结构。

我的问题围绕自上而下的解析器。我向我介绍了三种算法:

• 递归下降
• 预测性
• 预测递归下降

问题

但不明白如何将它们联系起来。所以请回答以下问题:

• 递归下降是基于回溯且效率低下吗？
• 预测解析是与其他两种算法完全不同的算法吗？
• 预测递归下降是一种特殊的递归下降算法，但没有回溯，这是真的吗？
• 预测算法使用解析表而递归下降不使用解析表，这是真的吗？预测递归下降算法是否使用预测解析表(某种增强解析表)？

还请回答这个问题:

• LL 解析器使用哪种算法？预测、预测递归下降还是递归下降？

谢谢

Answer 1

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

递归下降没有内置的效率保证。这取决于您编写的代码以及您要解决的问题是什么。 C 系列语言的 clang 解析器是递归的，可以回溯，并且被作者认为是解析 C 语言的正确方法。

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

考虑到递归下降和预测解析作为两种解析实现技术之间的对比，我想说递归解析器是一种使用递归函数(并隐式使用堆栈)实现解析器的方法，而预测解析在某种程度上是使用表和显式堆栈(但没有递归函数)来实现解析器。预测递归下降表明存在一个使用表和递归函数的解析器，这对我来说看起来很奇怪。最坏的情况是，预测递归下降解析器是一个不进行回溯的递归下降解析器(而不是预测解析器)，名字很丑。

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

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

http://en.wikipedia.org/wiki/LL_parser

http://en.wikipedia.org/wiki/Recursive_descent_parser

Are GCC and Clang parsers really handwritten?

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