什么是编译器设计中无回溯的自顶向下分析？

有两种无回溯的自顶向下分析方法，如下所示：

  • 递归下降分析器

  • 预测分析器

递归下降分析器

递归下降分析器是一种自顶向下分析器，它实现一组递归过程来处理输入而无需回溯。如果用一种有效执行过程调用的语言编写，则递归过程易于编写且效率足够高。

语法中的每个非终结符都有一个对应的过程。它可以考虑一个全局变量“展望”（lookahead），它影响当前输入标记，而过程`match(预期标记)`的作用是识别解析过程中的下一个标记并推进输入流指针，使得“展望”指向下一个要解析的标记。`match()`实际上是对词法分析器的调用，以获取下一个标记。

预测分析器

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

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

分析器由执行以下操作的程序控制：程序确定栈顶符号X和当前输入符号‘a’。这两个符号决定了分析器的动作。

有三种可能性：

  • 如果X = a = $，则分析器终止并声明解析成功。
  • 如果X = a ≠ $，则分析器将X从栈中弹出，并将输入指针推进到下一个输入符号。
  • 如果X是非终结符，则程序查阅分析表M中的M[X, a]项。此项将是语法的X-产生式或错误项。如果M[X, a] = [X→ UVW]，则分析器将栈顶的X替换为UVW（U位于顶部）。作为输出，语法执行与此产生式相关的语义动作，目前可以假设它只是打印所使用的产生式。如果M[X, a] = error，则分析器调用错误恢复例程。

更新于：2021年10月30日

1K+ 次浏览

启动你的职业生涯

完成课程获得认证

开始学习
广告