什么是自顶向下分析？

在自顶向下分析中，语法树是从上到下生成的，即从根到叶，并展开直到生成所有叶节点。

它生成以语法起始符为根的语法树。它从语法的起始符开始推导，并在每一步执行最左推导。

自顶向下分析的缺点

  • 自顶向下分析试图为输入字符串ω识别最左推导，这类似于为从根开始的输入字符串ω生成语法树，并按预定义顺序生成节点。

  • 自顶向下分析遵循输入字符串ω的最左推导而不是最右推导的原因是，解析器从左到右逐个符号/标记扫描输入字符串ω。最左推导按从左到右的顺序生成语法树的叶节点，这与输入扫描顺序相连接。

  • 在自顶向下分析中，由语法的多个产生式（已预测）生成的每个终结符都与字符串标记指向的输入字符串符号连接。如果匹配成功，解析器可以继续。如果发生不匹配，则预测是错误的。

  • 在此阶段，必须拒绝之前的预测。导致终结符不匹配的预测被拒绝，并且字符串标记（指针）重置到做出拒绝产生式时的先前位置。这称为回溯。

  • 回溯是自顶向下分析的主要缺点。

自顶向下分析的类型

自顶向下分析有两种类型，如下所示：

  • 带回溯的自顶向下分析

在回溯中，解析器可以对输入进行重复扫描。如果通过应用一个产生式规则无法获得所需的输入字符串，则可以在每一步应用另一个产生式规则以获得所需的字符串。

  • 不带回溯的自顶向下分析

一旦应用了产生式规则，就不能撤消。

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

**递归下降分析器** - 一种实现一组递归过程以在不回溯的情况下处理输入的自顶向下分析器称为递归下降分析器，分析称为递归下降分析。

更新于：2021年10月29日

11K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告