9.3 分析方法简介

从上一节可以看出，对于一个给定的语法 G ，从中推导出一个任意的句子是比较简单和直接的，但需要推导出指定的句子（或者说给定一个句子、要分析出它是怎么从起始符号开始推导得到的）就没那么简单了，这就是语法分析的任务。分析可以采用 自顶向下分析 或 自底向上分析 两种方法，以下先简单介绍这两种方法的思路，之后在下一章和下下一章分别详细介绍它们的具体实现步骤。

（1）自顶向下分析

自顶向下分析就是从起始符号开始，不断的挑选出合适的产生式，将中间句子中的非终结符的展开，最终展开到给定的句子。

以上一节第二个语法为例：

S –> AB
A –> aA | ε
B –> b | bB

假设要分析的句子为： aaab ，首先从起始符号 S 开始。

第 1 步，起始符号只有一个产生式： S -> AB ，所以只能选择这个产生式，用这个产生式的右边代替 S ，于是得到一个中间句子 AB ，将选择的产生式和得到中间句子（working-string）写成列表的形式，如下：

第 2 步，从 AB 开始，首先展开 A ， A 有两个产生式： A -> aA, A -> ε ，我们对比一下最终句子 aaab 和 目前得到的中间句子 AB ，发现只能选择 A -> aA ，否则将无法推导出 aaab 。因此选择这个产生式，将其右边替换掉中间句子 AB 中的 A ，于是得到中间句子 aAB ：

继续尝试展开 aAB 中的 A ，再次对比发现，还是只能选择产生式 A -> aA ，得到：

再次应用产生式 A -> aA ，得到：

到了这里，可以发现只能使用 A -> ε （否则无法得到 aaab ），应用此产生式后得到：

第 3 步，从 aaaB 开始，按上面同样的原则尝试展开 B ，最终得到：

（2）自底向上分析

自底向上分析的顺序和自顶向下分析的顺序刚好相反，从给定的句子开始，不断的挑选出合适的产生式，将中间句子中的子串折叠为非终结符，最终折叠到起始符号。

还是以上一节第二个语法为例，分析的句子还是： aaab 。但先将这个语法改写一下：

S –> AB
A –> Aa | ε
B –> b | bB

首先从最终句子 aaab 开始。从左边第一个字符 a 开始，对比语法中的所有产生式，发现没有一个产生式的右边可以完全匹配。但经过仔细观察和思考发现：可以尝试在 aaab 的最前面插入一个空句子 ε ，接下来可以应用 A -> ε ，之后再应用 A -> Aa， … 。因此先插入空句子，得到中间句子 εaaab ，如下：

此时，中间句子的最左边 ε 可以和 A -> ε 匹配了，因此，我们应用这个产生式，将 ε 折叠为 A ，得到 Aaaab ：

再观察中间句子 Aaaab ，发现它的最前面的 Aa 可以和 A -> Aa 匹配上，且只能和这个产生式匹配上，因此应用此产生式，将 Aa 折叠为 A ，得到 Aaab ：

按以上原则，一步一步的将中间句子的子串折叠为非终结符，最终折叠到起始符号 S ，过程如下：

（3）分析流程图

两种分析方法的分析流程见下面两个图：图9.6 自顶向下分析法流程图图9.7 自底向上分析法流程图

（4）分析过程的回溯和歧义

上面的例子其实是一个精心挑选出来的例子，在推导的过程中，每一步都只有唯一的一个产生式可以应用，即每一步都可以排除掉其他所有的产生式。但在实际分析时，在中间过程中可能会遇到：

1. 所有产生式都不可应用
2. 有多个产生式可以应用

两种情况。

对于第二种情况，需要采用回溯，先试探性的选择一个产生式应用，若一直推导至最终句子（或起始符号），则表明此产生式是可用的，若推导下去遇到第一种情况，则回溯到此处，选择另一个产生式。如果此处所有产生式都尝试过了全部都遇到第一种情况，则表明最终句子不符合语法结构。如果此处有多条产生式可以推导至最终句子（或起始符号），则表明语法有歧义。

回溯分析一般都非常慢，因此一般通过精心构造语法来避免回溯。

（5） 分析的局部性约束

上面的例子中，我们可以看到整个句子 aaab ，所以在挑选产生式时可以利用整个句子的信息，在实际编译过程中，实际的句子（源程序）是一个很长的符号流，分析的每一步中其实只能看到刚刚读入的一到两个符号，后面很长的一串符号都没读入进来，都看不到，因此只能利用目前已有的信息来进行判断，这就是分析的局部性约束。

（6） 左递归和右递归

左递归（left recursive） 是指形如 A -> A u 这样的规则，右递归（left recursive） 则是指形如 A -> u A 这样的规则。

为避免回溯，不宜将自顶向下分析法应用于含左递归的语法 ，这是由此方法的分析顺序决定的。

第 9 章完