回溯法和非回溯法有什么区别？

带回溯的自顶向下分析

在带回溯的自顶向下分析中，解析器将尝试多种规则或产生式，通过在推导的每一步回溯来发现与输入字符串的匹配。因此，如果使用的产生式没有给出所需的输入字符串，或者它与所需的字符串不匹配，则可以撤消该移位。

不带回溯的自顶向下分析

由于回溯看起来更强大，我们可以选择不同的备选方案。但是回溯在解析中不能轻易应用或实现。不带回溯的自顶向下分析有两种类型，如下所示：

递归下降分析器

实现一组递归过程来处理输入而不回溯的自顶向下分析器称为递归下降分析器，而解析称为递归下降解析。如果用一种有效执行过程调用的语言编写，则递归过程可以简单地编写并且足够有效。

语法中每个非终结符都有一个过程。它可以考虑一个全局变量前瞻，保存当前的输入标记，并且一个过程匹配（预期标记）是识别解析过程中下一个标记并推进输入流指针的动作，使得前瞻指向要解析的下一个标记。Match() 有效地调用词法分析器来获取下一个标记。

预测分析器

预测分析器也称为非递归预测分析。预测分析器是一种执行递归下降分析的有效方法，它显式地处理激活记录的堆栈。预测分析器具有输入、堆栈、分析表和输出。输入包括要解析的字符串，后跟 $，即右端标记。

堆栈包含一系列语法符号，前面是 $，即堆栈底部标记。最初，堆栈包含语法开始符号，前面是 $。分析表是一个二维数组 M[A, a]，其中 'A' 是一个非终结符，'a' 是一个终结符或符号 $。

让我们看看带回溯的自顶向下分析和不带回溯的自顶向下分析之间的比较

带回溯的自顶向下分析	不带回溯的自顶向下分析
解析器可以按任意顺序尝试所有备选方案，直到成功解析字符串。	解析器必须在每一步选择正确的备选方案。
回溯需要大量时间，即指数时间来执行解析。	它花费更少的时间。
语法可以有左递归。	在进行解析之前将删除左递归。
撤消操作时会有很多开销。	它可以运行更少的开销。
在回溯时，一旦插入的信息将从符号表中删除。	信息不会被删除。
可能难以找到实际发生错误的位置。	可以很容易地找到错误的位置。

Ginni

更新时间： 2021-11-01

2K+ 浏览量

完成课程获得认证