回溯和非回溯有什么区别？
自上而下的回溯分析
在 Top-Down Parsing with Backtracking 中，Parser 将尝试多个规则或产生式，通过在推导的每一步进行回溯来发现输入字符串的匹配项。因此，如果使用的产生式没有根据需要提供输入字符串，或者它与所需的字符串不匹配，那么它可以撤消该移位。
自上而下的解析，无需回溯
由于回溯看起来更强大，我们可以通过它选择不同的替代方案。但是在解析中不能那么容易地应用或实现回溯。有两种没有回溯的自顶向下解析，如下所示 -
递归下降解析器
预测解析器
递归下降解析器
实现一组递归过程来处理输入而不回溯的自顶向下解析器被称为递归下降解析器，解析被称为递归下降解析。如果以有效执行过程调用的语言编写，递归过程可以简单地编写并且充分有效。
文法中的每个非终结符都有一个过程。可以考虑一个全局变量lookahead，持有当前输入的token和一个过程匹配（Expected Token）是解析过程中识别下一个token并推进输入流指针的动作，使得lookahead指向下一个要处理的token解析。Match() 实际上是调用词法分析器以获取下一个标记。
预测解析器
预测解析器也称为非递归预测解析。预测解析器是一种通过显式处理活动记录堆栈来执行递归下降解析的有效方法。预测解析器具有输入、堆栈、解析表和输出。输入包括要解析的字符串，后跟 $，即右端标记。
堆栈包括一系列语法符号，前面是 $，堆栈底部标记。最初，堆栈包含以 $开头的语法的起始符号。解析表是一个二维数组M[A, a]，其中'A'是一个非终结符，'a'是一个终结符或符号$。
让我们看看有回溯的自顶向下解析和没有回溯的自顶向下解析之间的比较
| 自上而下的回溯分析 | 自上而下的解析，无需回溯 |
|---|---|
| The parser can try all alternatives in any order till it successfully parses the string. | 解析器必须在每一步选择正确的替代方案。 |
| Backtracking takes a lot of time, i.e., exponential time to perform the parsing. | 它需要更少的时间。 |
| A Grammar can have left recursion. | 在进行解析之前，左递归将被删除。 |
| A lot of overhead will be there while undoing things. | 它可以运行更少的开销。 |
| Information, once inserted, will be removed from the symbol table while backtracking. | 信息不会被删除。 |
| It can be difficult to find where actually error has occurred. | 可以很容易地找到错误的位置。 |
以上是 回溯和非回溯有什么区别？ 的全部内容， 来源链接： utcz.com/z/360748.html
