2

I am working on Context Free Grammars and I am stuck into the first step: understanding how Top-Down parsing algorithms are structured.

My problem revolves around top-down parsers. And I have three algorithms that were introduced to me:

  • Recursive Descent
  • Predictive
  • Predictive Recursive Descent

Questions

But do not understand how to relate them. So please answer the following questions:

  • Is it true that Recursive Descent is based on backtracking and inefficient?
  • Is it true that Predictive parsing is a completely different algorithm from the other two?
  • Is it true that Predictive Recursive Descent is a particular kind of recursive descent algorithm but without backtracking?
  • Is it true that Predictive algorithms use parse-tables and Recursive Descent do not? Is it true that Predictive Recursive Descent algorithms use a predictive parse table (sort of enhanced parse table)?

Also please answer this question:

  • Which algorithm LL parsers use? Predictive, Predictive Recursive Descent or Recursive Descent?

Thank you

4

2 回答 2

4

递归下降允许您实现一定范围的形式解析器。例如，它允许开发 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

GCC 和 Clang 解析器真的是手写的吗？

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

于 2013-12-23T20:03:54.497 回答
3

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

许多（但不是全部）预测解析器是表驱动的。LR 解析器通常使用表来实现，一些 LL 解析器也是如此，尽管情况并非总是如此。许多 LL 解析器是使用递归下降实现的，许多 LR 解析器是使用递归上升实现的。

递归下降解析通常是指自上而下的解析算法，该算法通过为每个终端和非终端具有不同的递归函数来猜测要使用哪些产生式。他们通常根据语法使用一定数量的回溯，并且通常在左递归语法上失败。通常，手写的 LL 解析器是使用没有回溯的递归下降编写的，这是可能的，因为语法是专门构造为不需要任何回溯的。这是预测递归下降。

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

希望这可以帮助！

于 2013-12-23T20:56:17.170 回答