英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

自顶向下分析法

1 概述

自顶向下的分析算法通过追踪最左边的派生中的步骤来分析标记的输入字符串。这种算法被称为自顶向下，因为分析树的隐含遍历是预序遍历，因此从根到叶发生。自上而下的分析器有两种形式：回溯分析器和预测分析器。预测分析器尝试使用一个或多个前瞻标记来预测输入字符串中的下一个结构，而回溯分析器将尝试不同的可能性来分析输入，如果一种可能性失败，则在输入中备份任意数量。虽然回溯分析器比预测分析器更强大，但它们也慢得多，需要一般的指数时间，因此不适合实际的编译器。我们不会在这里研究回溯分析器。

我们在这里研究的两种自顶向下分析算法称为递归分析和LL（1）分析。递归下降分析是非常通用的，是手写分析器最合适的方法，因此我们首先学习。 LL（1）接下来研究分析;虽然它不再在实践中经常使用，但作为一个具有显式堆栈的简单方案是有用的，它可以作为更强大（而且更复杂）的自下而上算法的前奏。它还有助于形式化递归下降中出现的一些问题。 LL（1）分析方法的名称的含义如下。第一个“L”是指它从左到右处理输入（一些旧的分析器用于从右到左处理输入，但今天是不寻常的）。第二个“L”是指其输出字符串的最左边推导。括号中的数字1意味着它只使用一个输入符号来预测分析的方向。 （也可以使用前瞻性的k个符号进行LL（k）分析，但是先行的一个符号是最常见的情况）。

递归下降分析和LL（I）分析都需要一般来说称为First和Follow集合的前瞻集的计算。由于可以构造简单的自上而下的分析器，而不需要明确构建这些集合，因此我们会延迟对它们的讨论，直到基本算法被引入之后。然后，我们将使用自顶向下分析中的错误恢复方法的描述来结束本章。

2 通过递归下降进行自顶向下的分析

2.1 递归下降的基本方法

递归下降分析的想法非常简单。 我们将非终结符A的语法规则视为对A认可的程序的定义。A语法规则的右侧指定了此过程的代码结构：选择中的终端和非终结符序列对应于输入和对其他过程的调用的匹配，而选项对应于代码中的替代方案(case或者if语句) 。

作为第一个例子，考虑上一章表达式语法：

并考虑一个因素的语法规则。 识别因子的递归下降过程（以及我们将用相同名称调用）可以用伪代码写成如下形式：

在这个伪代码中，我们假设有一个标记变量，将当前的下一个标记保存在输入中（这样，这个例子使用了一个前瞻符号）。 我们还假设有一个匹配过程与当前的下一个标记与其参数匹配，如果成功则提前输入，如果没有，则声明错误。

目前我们没有指定在匹配和因素中调用的错误过程。 可以假定打印错误信息并退出。 请注意，在调用match（（）和match（number）因子中，expectedToken和token的变量已知是相同的。 但是，在调用match（））中，标记不能被认为是右括号，因此必须进行测试。 因子的代码还假定已经定义了可以调用的过程exp。 在表达式语法的递归下降分析器中，exp过程将调用项，术语过程将调用因子，因子过程将调用exp，因此所有这些过程必须能够彼此调用。 不幸的是，为表达式语法中的剩余规则编写递归下降过程并不像要素那样简单，需要使用EBNF，就像我们现在即将看到的。

2.2 重复和选择：使用EBNF

将第二个例子作为if语句的（简化）语法规则：

这可以翻译成程序：

在这个例子中，我们无法立即区分语法规则右侧的两个选项（它们都以标记if开始）。 相反，我们必须决定是否识别可选的else部分，直到我们在输入中看到标记“else”。 因此，if语句的代码更多地对应于EBNF

相较于BNF，其中方括号的EBNF转换成ifStmt代码中的一个测试。 事实上，EBNF符号被设计为紧密地反映递归分析器的实际代码，所以如果要使用递归下降，语法应该总是被转换成EBNF。 还要注意，即使这个语法是不明确的（参见前面的章节），一旦在输入中遇到它，写一个匹配每个“else”标记的分析器是很自然的事情。 这恰恰对应于最为嵌套的消歧规则。 现在考虑BNF中简单算术表达式的语法表达式的情况：

如果我们试图根据我们的计划将其转化为递归过程，那么我们可能尝试的第一件事就是调用exp，这将导致一个立即无限循环的循环。 尝试测试使用哪个选项（exp→exp addop term 或 exp→term）同样有问题，因为exp和term都可以以相同的标记（数字或左括号）开头。 解决方案是使用EBNF规则:

来代替。

表示重复的大括号可以转换为循环的代码，如下所示：

类似地，EBNF规则为：

用代码表示：

这里我们将非终止的addop和mulop作为单独的过程消除，因为它们唯一的功能是匹配运算符：

我们在exp和term内进行匹配来取代。

这个代码产生的一个问题是，是否仍然可以维护大括号（和原始BNF中显式的）隐含的左组合。 例如，假设我们要为我们的语法的简单整数算术写一个递归下降计算器。 我们可以通过在循环循环中执行操作来确保操作保持关联（我们假设分析过程是返回整数结果的函数）：

对term也是一样。

这种将EBNF中的语法规则转化为代码的方法相当强大。 但是，有一些陷阱，在安排代码中的操作时必须小心。 其中一个例子是对于exp的前一个伪代码，其中操作的匹配必须在对term的重复调用之前发生（否则术语将看到一个操作作为其第一个标记，这将产生一个错误）。实际上，保持全局标记变量的以下协议必须严格遵守：在分析开始之前必须设置标记，并且在成功测试标记之后必须调用getToken（或其等价物）（我们把它放入在伪代码中的匹配程序中）。

在构建语法树期间调度动作时，也必须同样谨慎。 我们看到，通过执行循环执行计算，可以保持具有重复性的EBNF中的左组合性以进行计算。 然而，这不再对应于分析或语法树的自顶向下的结构。 实际上，如果我们用语法树来考虑表达式3 4 5

代表3和4之和的节点必须先创建（或处理）节点（节点与它的和表示为5）。 将其转换为实际的语法树构造，我们对exp过程有以下伪代码：

或者简单点：

在这段代码中，我们使用了一个新的函数makeOpNode，它接收一个操作符，作为参数，返回一个新构造的语法树节点。 我们还通过写入leftChild（t）：= p或rightChild（t）：= p来指示语法树p作为语法树t的左或右子节点分配。 使用此伪代码，exp过程确实构造了语法树，而不是分析树。 这是因为对exp的调用并不总是构造一个新的树节点; 如果没有运算符，那么只需将从初始调用接收到的树返回给自己的值即可。术语和因子的相应伪代码。 相比之下，if语句的语法树可以通过递归下降分析器以严格自顶向下的方式构建：

在允许程序员调整动作调度的情况下，递归下降分析的灵活性使其成为手工生成分析器的首选方法。

2.3 进一步的决策问题

我们描述的递归下降方法是非常有力的，但仍然是特别的。 使用小巧精心设计的语言（如C语言），这些方法足以构建一个完整的分析器。 我们应该意识到，在复杂的情况下可能需要更加正式的方法。 可能会出现几个问题。首先，将原来以BNF编写的语法转换成EBNF形式可能是不利的。在下一节中研究了使用EBNF的替代方案，其中构建了基本上等同于EBNF的变换BNF。其次，制定一个测试来区分两个或多个语法规则选项

A→alpha; | beta; | ...

决定何时使用选择A→alpha;，何时使用选择A→beta;，如果alpha;和beta;两者都以非终结点开始。 这样的决策问题需要计算第一组alpha;和beta;：可以合法地开始每个字符串的标记集合。 稍后我们正式确定这个计算的细节。最后，编写一个ε产生式的代码

表一：分析自动分析器的动作

可能有必要知道什么标记可以合法地在非终止的A之后，因为这样的标记表明A可能适当地消失在分析的这一点上。 该集合称为A的跟随集合。此集合的计算也在后面进行确定。

3 LL（1）分析法

3.1 LL（1）分析的基本方法

LL（l）分析使用显式堆栈而不是递归调用来执行分析。 以标准方式表示此堆栈是有帮助的，因此LL（1）分析器的动作可以快速方便地可视化。 在这个介绍性讨论中，我们使用生成平行括号的字符串的非常简单的语法：

表1显示了给定此语法的自上而下的分析器和string（）的操作。 在这个表中有四列。 第一列列出了以后参考的步骤。 第二列显示分析堆栈的内容，堆栈的底部在左边，堆栈的顶部在右边。我们用一个美元符号标记堆栈的底部。因此，在顶部包含非终端S的堆栈显示为：

$S

并且附加的堆栈项将被推到右边。 表1的第三列显示了输入。输入符号从左到右列出。 美元符号用于标记输入的结尾（这对应于扫描仪生成的EOF标记）。该表的第四列给出了分析器采取的动作的简要说明，这将更改堆栈和（可能的）输入，如表的下一行所示。

通过将起始符号推入堆栈开始，自顶向下的分析器开始。 如果在一系列操作之后，堆栈和输入变为空，它接受输入字符串。 因此，成功的自顶向下分析的一般原理是:

在我们的例子中，起始符号是S，输入的字符串是（）。 通过在非法终结语法规则（BNF）中的一个选项替换堆栈顶端的非终结符来分析自上而下的分析器。 它是为了在分析堆栈的顶部生成当前的输入标记，它与输入标记匹配，并可以从堆栈和输入中丢弃它。这两个动作：

1. 使用语法规则选择A→alpha;，通过字符串alpha;替换堆栈顶部的非终结符A

2. 将堆栈顶部的标记与下一个输入标记匹配

是自上而下的分析器中的两个基本操作。 第一个动作可以称为生成; 我们通过写入替换中使用的BNF选择（其左侧必须是当前在堆栈顶部的非终结符）来表示此操作。 第二个动作与堆栈顶部的标记与输入中的下一个标记相匹配（并通过弹出堆栈并提前输入来抛出）; 我们通过写字匹配来表示这个动作。 重要的是要注意，在生成动作中，必须将来自BNF的替换字符串alpha;反向推送到堆栈上（因为这样可确保字符串alpha;以从左到右的顺序到达堆栈的顶部）。

例如，在表1的分析的步骤1中，堆栈和输入是

并且我们用于替换堆栈顶部的S的规则是S→（S）S，使得字符串S）S（被推到堆栈上以获得

现在我们已经在堆栈的顶部生成了下一个输入终端，即左括号，我们执行匹配操作来获得以下情况：

表1中的生成动作列表精确地对应于string（）的最左边推导中的步骤：

这是自顶向下分析的特征。如果我们要在分析进行时构造分析树，我们可以添加节点构造动作，因为每个非终结符或终端被推到堆栈上。 因此，分析树的根节点（对应于开始符号）在分析开始时构造。 并且在表1的步骤2中，当S被(S)S替代时，四个替换符号中的每一个的节点被构造为符号被推到堆栈上并且被连接作为子节点被代替的S的节点 在栈上 为了使这个有效，我们必须修改堆栈以包含指向这些构造的节点的指针，而不是仅仅是非终端或终端本身。此外，我们将看到如何修改此过程以产生语法树而不是分析树的构造。

3.2 LL（1）分析表和算法

使用刚才描述的分析方法，当非终结符A位于分析堆栈的顶端时，必须根据当前输入标记作出决定，当代替A时，选择使用A的那种语法规则。 相比之下，当标记位于堆栈顶部时，由于它与当前输入标记相同，并且匹配发生。否则发生错误，因此无需进行任何决定。我们可以通过构造LL（l）分析表来表达可能的选择。 这样一个表本质上是一个由非终端和终端索引的二维数组，包含在适当的分析步骤（包括$表示输入的结尾）中使用的产生式。 我们称这个表M [N，T]。 这里N是语法的非终结符，T是终端或标记的集合（为了方便起见，我们抑制$必须添加到T的事实），M可以被认为是“移动”表。 我们假设表M [N，T]开始，其所有条目为空。 任何在构建后保持为空的条目都表示在分析过程中可能发生的错误。析堆栈的顶部时，必须根据当前输入标记作出决定，当代替A时，则选择使用A语法规则。 相比之下，当标记位于堆栈顶部时，由于它与当前输入标记相同，并且发生匹配，或者不发生错误，则发生错误。

我们根据以下规则向此表添加产生式

1.如果是产生式，并且有一个派生，其中a是标记，则将添加到表条目M [A，a]。

2.如果是产生式，并且有派生和，其中S是开始符号，a是标记（或$），然后添加到表项M [A，a]。

这些规则背后的想法如下。在规则1中，给定输入中的标记a，如果alpha;可以产生一个匹配，我们希望选择规则。在规则2中，如果A导出空字符串（通过），如果a是导出后可以合法地在A之后的标记，则我们要选择使A消失。 请注意，规则2的特殊情况是当a =ε时。

这些规则是直接实施的，在下一节中，我们将开发这样做的算法，涉及到已经提到的First集和Follow集。 然而，在极其简单的情况下，这些规则可以手工执行。

表2：if语句的LL（1）分析表

将第一个例子作为前一小节中使用的平衡括号的语法。 有一个非终端（S），三个标记（左括号，右括号和$），以及两个产生式。 由于S只有一个非空产生式，即S→（S）S，所以从S导出的每个字符串都必须是空的，或以左括号开头，而这个产生式由于S =rArr;（S）S被添加到条目M，规则2适用于alpha;=ε，beta;=（，A = S，a =），以及 gamma;= S $，所以将S→ε加

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[138818]，资料为PDF文档或Word文档，PDF文档可免费转换为Word