编译原理 4：语法分析

前面在编译原理 1：绪论中我们介绍：

• 词法分析的任务是从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型，而后将识别出的单词转换成统一的机内表示——词法单元（token）的形式

上一章在编译原理 3：词法分析中，我们介绍了词法分析是如何实现的。具体来说：

• 我们首先介绍了正则表达式和正则定义。通过正则表达式和正则定义，我们定义了程序中各类token的模式，例如：标识符的模式、无符号数的模式……

  

• 但是正则表达式和正则定义人类很容易理解，但是不方便写出让计算机接受的算法。因此，我们接着介绍了有穷自动机。

  • 有穷自动机分为两种：非确定性有穷自动机（NFA）和确定性有穷自动机（DFA）
    • 非确定性有穷自动机方便人类理解。我们可以很简单的从正则表达式构建对应的（即识别相同token）的非确定性有穷自动机
    • 确定性有穷自动机方便机器的算法实现。给定一个DFA，我们可以很轻松的就写出对应的算法实现。
  • 我们有指定的算法（即子集描述法）将NFA转换为DFA。

• 接着，我们利用正则表达式和不确定性有穷自动机的转换关系，通过各种token的正则表达式构建出识别各类token的NFA

• 然后，利用子集描述法，利用识别各类token的NFA构建识别各类token的DFA

• 最后，我们使用各类编程语言将识别各类token的DFA实现，得到词法分析程序

词法分析程序以程序源代码作为输入，而后输出是token流

1. 语法分析概述

A. 语法分析的任务

在词法分析之后，我们得到了源程序的token流。而接下来的语法分析，我们的任务就是从token流中，根据给定的文法，去识别各个短语，而后构建出源程序的语法分析树。

如果输入token序列的各个token都自左至右的站在语法分析树的叶子结点，那么输入的token流就是该语言的一个句子。

同样，和词法分析类似，我们接下来首先从理论上对语法分析进行介绍，最后一步步引导到语法分析的算法实现。

B. 语法分析的分类

语法分析的最终目的就是构建语法分析树，因此根据语法分析时构建语法分析树的方式不同，可以将语法分析分为两类：

• 自顶向下的语法分析：从顶部的根节点向底部的叶节点方向构建语法分析树
• 自底向上的语法分析：从底部的叶节点向顶部的根节点方向构建语法分析树

而由于目前大多数编译器中进行语法分析的分析器采用的都是自顶向下的语法分析，因此我们就主要介绍自顶向下的语法分析。

2. 自顶向下的语法分析

A. 自顶向下的语法分析等价于推导

我们不加证明的给出如下的论断：

• 自顶向下的语法分析等价于从文法开始符号$S$推导出词串$w$的过程

1) 举例

我们举一个例子来验证这一论断的正确性。

给定如下的文法：

假设我们输入如下的单词串（假设已经经过词法分析得到了token流）：

现在我们要针对这单词串构建语法分析树：

首先从开始符号开始构建语法分析树

然后对分析树的根节点运用产生式1：$E\rightarrow E + E$

然后对最右侧的子节点运用产生式3：$E\rightarrow (E)$

接着，在对中间的子节点运用产生式1：$E\rightarrow E + E$

然后，对左侧的子节点运用产生式4：$E\rightarrow \mathrm{id}$

接下来，我们对根节点的左子节点运用产生式4：$E\rightarrow \mathrm{id}$

最后，在对剩余的右子节点运用产生式4：$E\rightarrow \mathrm{id}$

至此，我们就已经完成了输入的token流的语法分析，构建出了语法分析树。

通过上面的例子我们知道了语法分析过程中我们构建自顶向下去构建语法分析树，其实就等价于从语法开始符号去推导得到输入的句子。所以后面，从开始符号推导得到句子就等价于构建输入token流语法分析树

2) 语法分析的问题

我们发现，在每一步推导中，都需要做两个选择：

• 选择一：替换当前句型中的哪个非终结符
• 选择二：用该非终结符的哪个候选式进行替换

因此，对于自顶向下的语法分析，我们需要解决的就是这样问题，即：

• 决定替换哪个非终结符
• 决定使用哪个产生式替换

B. 最左推导 Left-most Derivation

最左推导（Left-most Derivation）指的是，在每次选择非终结符进行替换的时候，总是选择每个句型的最左非终结符进行替换，使用符号$\Rightarrow_{lm}$表示

例如对于上面的例子，我们从开始符号开始进行最左推导：

注意，如何选择合适的产生式我们后面再进行介绍，这里我们关注的是每次选择哪个非终结符进行替换（红色标出）

和最左推导相反的规约过程，称为最右规约

我们定义：如果开始符号经过$n$步最左推导得到一个句型$\alpha$，则称$\alpha$是当前文法的最左句型（Left-sentential Form）

C. 最右推导 Right-most Derivation

和最左推导类似，最右推导（Right-most Derivation）指的是，在每次选择非终结符进行替换的时候，总是选择每个句型的最右非终结符进行替换，使用符号$\Rightarrow_{rm}$表示

类似的，和最右推导相反的规约过程，称为最左规约

注意，由于在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导

D. 最左推导和最右推导的唯一性

我们在自顶向下构建分析树的时候，哪怕最后生成得到的分析的叶子结点在表示相同的句子，但是由于每一次使用产生式展开选择的节点可能不同，因此最后得到的分析树可能是不同。

但是，我们自顶向下构建分析树的时候，最左推导和最右推导得到的分析树是唯一的（假设相同节点的产生式是相同的）

E. 自顶向下的语法分析采用最左推导

由于现实中工业生产的分析器（例如gcc、clang……）都是自左向右的扫描输入串，因此在构建语法树的时候，也是按照最左推导的方式去构建的。

即：

• 选择终结符时：每次总是选择每个句型的最左非终结符进行替换
• 选择产生式时：根据输入流中的下一个终结符，选择最左非终结符的一个候选式

F. 自顶向下语法分析举例

我们接下来看一个自顶向下语法分析的例子：

给定输入：

注意，和token流一同输入的，还有一个token指针，这个token指针后续会随着分析树构建的过程不断移动

接下来，我们开始构建分析树。

因为是自顶向下的语法分析，因此我们从文法的开始符号$E$开始（即从开始符号$E$开始推导）：

注意，和前面一样，我们这里略去如何选择使用哪个产生式，而关注于选择哪个非终结符进行展开

最左侧的非终结符就是开始符号$E$

最左侧的非终结符是$T$

最左侧的非终结符是$F$。这里注意：产生式5都是简写形式的产生式，实际上产生式5有两个两个候选式：

• $F\rightarrow (E)$
• $F\rightarrow \mathrm{id}$

我们后面再介绍如何选择产生式/候选式，这里我们只关注与选择哪个非终结符。这里我们用产生式5的第二个候选式

注意，这个时候由于第一个终结符id和表达式的第一个终结符匹配上了，因此token指针向右移动一个token，指向+

然后，最左侧的非终结符是$T’$，但是由于不存在将$T’$转换为$+$的产生式，因此选择产生式4，将$T’$转换为空串$\varepsilon$

继续构建语法树，最左侧的非终结符是$E’$，因为当前token指针指向的token是$+$，因此使用产生式2的第一个候选式

此时，产生了一个非终结符$+$，并且该非终结符和token指针指向的token匹配了，因此token指针向右移动一位

继续构建语法树，此时最左侧的非终结符是$T$

没有产生终结符，继续展开最左侧非终结符$F$。产生式5有两个候选式，这里选择第二个候选式

此时产生了一个终结符$\mathrm{id}$，并且和当前token指针指向的token匹配了，因此token指针向右移动一位

由于没有终结符了，所以继续构建语法树。此时最左侧非终结符是$T’$

由于产生了一个终结符$*$，并且和当前token指针指向的token匹配了，因此token指针向右移动一位

然后最左侧的非终结符是$F$。产生式5有两个候选式，这里选择第二个候选式

由于产生了一个终结符$\mathrm{id}$，并且和当前token指针指向的token匹配了，因此token指针向右移动一位

最后，剩下的$T’$和$E’$就依次展开就好，展开的时候选择用空串展开。

最后，由于输入的串恰好自左至右的站在语法树的叶子结点上，因此输入的句子是该文法定义的语言的一个句子

G. 递归下降分析

我们上面介绍了自顶向下的语法分析，接下来我们介绍计算机中是如何用算法去实现自顶向下语法分析的

自顶向下语法分析的算法实现称为：递归下降分析（Recursive-Descent Parsing）。

具体而言：

• 递归向下分析由一组过程组成，每个过程对应一个非终结符。例如对应非终结符A的过程：

  • 首先通过产生式选择算法（后面会详细介绍）选择出$A$的产生式$A\rightarrow X_1X_2…X_k$
  • 然后针对产生式右边的所有符号循环判断：
    • 如果符号是非终结符，那么递归调用对应的过程$X_i()$（可以看到就是树的深度遍历）
    • 如果符号是非终结符，且对应当前的符号，那么读入下一个符号。即token指针右移
    • 此外报错，即选择出来的产生式是错误的

  

• 递归向下分析从文法开始符号$S$对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析

但是递归向下分析实际在效率上其实是存在问题的，例如：

• 假设现在针对非终结符$A$调用对应的过程

• $A$有多个产生式：

  $$\begin{aligned} P_1:\ A&\rightarrow aBC\\ P_2:\ A&\rightarrow aDE\\ P_3:\ A&\rightarrow a \end{aligned}$$

• 那么在遍历产生式的时候，前两个产生式因为都用到了别的非终结符，所以实际上会递归的调用非终结符$B$和$C$的产生式。

• 假设在最后构成的语法树中，使用到的正确的产生式是$P_3$，那么就意味着前两次向下递归调用$B$和$C$的产生式实在浪费时间

因此，向下递归分析最大的问题就是：

因此，在语法分析过程中需要回溯的分析器称为不确定的分析器。而通过一些手段，例如下面要介绍的预测分析，我们是可以在一定程度上解决这个问题的

H. 预测分析

预测分析是递归下降分析技术的一个特例，即：

• 在输入的符号串中向前看固定个数（通常是一个）符号来选择正确的$A\rightarrow$产生式

预测分析通过在选择产生式的时候向前几个符号，从而选择最佳的产生式，因此预测分析不需要回溯，是一种确定性的分析方法。

此外，某些文法具有特殊性，针对这些文法，我们可以：

• 构造出向前看$k$个输入符号的预测分析器，因此我们有时候也将这类文法称为$LL(k)$文法类

这么讲比较抽象，尤其是还没有例子。不过别担心，我们后面会详细介绍的

3. 文法转换

我们上面介绍了自顶向下语法分析是如何选择替换哪个非终结符的，那么还剩的最后一个问题就是确定使用哪个产生式替换非终结符。因此，我们接下来讲解的内容，就是去解决剩下的第二个问题的。

在此之前，我们需要表数学形式的文法表达为计算机可以接受的算法。同时针对一些文法，可能存在问题，不能直接转换为算法，因此还需要我们去进行特殊处理。

这一节就先介绍这些内容。

A. 问题一：冗余计算

我们上面介绍了自顶向下语法分析的算法实现：递归下降分析。我们也提到了递归下降分析存在的回溯问题，从而导致分析器在运行的时候效率低。

但是我们只是简单的提了一下，没有正式地举例介绍，我们这里正式地介绍自顶向下语法分析中的回溯问题

假设给定如下的文法和输入：

我们现在开始自顶向下的语法分析，即从开始符号$S$开始分析。

但是这个时候，对于符号$S$，他有两个$A\rightarrow$类型的产生式：

• $S\rightarrow aAd$
• $S\rightarrow aBe$

那么我们此时不知道到底选哪个产生式。假设使用遍历的方式选择产生式，那么如果第一个产生式不是最终能够得到句子的产生式，那么此后的向下展开都白费了。

因此：

而在具有公共前缀的情况下，回溯会造成大量的冗余计算

B. 问题二：无限循环

加上我们给定如下的文法：

而后给定输入串：

然后我们接下来需要对这个输入串构建其语法树。

我们首先从开始符号$E$开始推导，因为$E$的$A\rightarrow$类型产生式只有一个，所以顺利展开就好：

然后根据最左推导，我们下一个要展开的非终结符是$E$。

那这个时候，问题就来了，我们发现最左推导针对这类文法会出现无线循环展开的问题，即最后：

无限循环问题的一种可能是因为我们存在这样的产生式：

$$A\rightarrow A\alpha$$

针对上面的例子，我们存在问题的产生式是：

$$E\rightarrow E+T$$

因此，我们将这类产生式称为直接左递归的产生式。

类似的，含有直接左递归产生式的文法我们称为直接左递归文法

另外一种情况是我们不存在直接左递归产生式，但是存在如下的产生式：

$$\begin{aligned} A&\rightarrow Ba\\ B&\rightarrow Acd \end{aligned}$$

那么我们对$A$进行推导，最后得到的还是递归的产生式。

因此，若一个文法中一个非终结符$A$使得对某个串$\alpha$存在一个推导：

$$A\Rightarrow^*A\alpha$$

则称这个文法为左递归文法

由此，我们称经过两步或两步以上推导产生的左递归为间接左递归

C. 消除直接左递归

1) 消除思想和原因

冗余计算问题和递归问题是我们需要解决的两个问题。我们首先解决递归问题，首先从直接左递归开始

我们处理直接左递归的思想就是：将直接左递归产生式转换为等价的（即表示相同语言的）右递归产生式。右递归产生式虽然也会导致编译器出现无限循环，但是我们在算法中可以检测到右递归，而后通过回溯跳出无限循环。

PS：为什么要先把直接左递归转换为右递归然后再通过回溯跳出循环而不能直接跳出循环？

因为对于左递归来说，回溯技术是没法避免无限循环的，因为回溯之后，分析器回溯到$A$，然后去尝试匹配$\alpha$。但是由于产生式的形式是$A\rightarrow A\alpha$，所以回溯到$A$之后，分析器又会再次展开成$A\alpha$，从而导致进入无限循环的状态。

2) 消除方法

对于直接左递归的产生式的通式：

$$A\rightarrow A\alpha|\beta (\alpha\neq\varepsilon)$$

我们首先分析其所表示的串：

所以，直接左递归产生式对应的正则表达式为：

$$r=\beta \alpha^*$$

即直接左递归产生式表达的串是$\beta$开头的，可以由$n$个$\alpha$的串

所以，我们构建如下的表示相同串的产生式：

$$A\rightarrow A\alpha \Leftrightarrow \left \{ \begin{aligned} A\ &\rightarrow \beta A'\\ A'&\rightarrow \alpha A' | \varepsilon \end{aligned} \right .$$

我们可以对转换后的产生式进行验证

而转换后的产生式，实际上是一个右递归的产生式，因此上面这种消除方式其实就是把左递归产生式转化为了右递归产生式

3) 举例

我们接下来举一个消除直接左递归的例子

对于第一个直接左递归产生式：

$$E\rightarrow E+T|T$$

和通式的对应关系为：

• $A$：$E$
• $\alpha$：$+T$
• $\beta$：$T$

同理，第二个直接左递归产生式进行如下的转换

4) 消除左递归的一般形式

我们接下来给出消除左递归的一般形式：

此外，从上面的讲解中，我们也明白了消除左递归是要付出代价的：

D. 消除间接左递归

间接左递归产生式代入即可得到直接左递归产生式，因此消除间接左递归产生式方法就是先代入，然后消除

E. 消除左递归的算法实现

我们接下来给出消除左递归的算法实现

F. 提取左公因子

我们通过消除左递归解决了无限循环问题，而针对冗余计算问题，提取左公因子可以减少一部分计算量。

1) 原理

提取左公因子的思想很简单，就是把具有相同前缀的产生式的前缀提取出来，构成一个新的产生式

提取左公因子减少了冗余计算量，因为左公因子的表达式只会计算一遍。

2) 算法实现

提取左公因子的算法实现如下：

4. LL1文法

递归下降分析可能会遇到回溯，回溯会降低分析器的效率。而如果我们在分析的每一步，都能够选择正确的产生式展开的话，那么我们就不需要回溯。这样的分析称为预测分析。但并不是所有的文法都可以实现预测分析的，不过我们接下来要介绍的一种文法，即LL1文法是可以实现预测分析的。

所以，我们先讲解LL1文法，然后再介绍预测分析法。具体来说，我们会先介绍FIRST集、FOLLOW集和SELECT集。

A. FIRST集：串首终结符集

FIRST集的主要意义就是计算SELECT集

1) 定义

定义串首终结符为：

• 位与串的开头的第一个非终结符，简称首终结符

形式化的定义为：

• 给定一个文法符号串$α$， $α$的串首终结符集定义为可以从$α$推导出的所有串首终结符构成的集合，记为：$FIRST(α)$

即：

$$\forall \alpha\in(V_T\cup V_N)^*, FIRST(\alpha)=\{a|\alpha\Rightarrow^*a\beta,\ a\in V_T, \beta\in(V_T\cup V_N)^*\}$$

2) 举例

假设我们有一个文法$G$，其中$S$是起始符号，$V_T={a,b,c}$，$V_N={A,B}$，产生式如下：

$$\begin{aligned} S &\rightarrow AaBb | BcA\\ A &\rightarrow aA | ε\\ B &\rightarrow bB | ε \end{aligned}$$

对于串AaBb，它的首终结符集合是{a}，因为它的第一个终结符是a。而对于串BcA，它的首终结符集合是{b, c}，因为它的第一个终结符可以是b或c。

3) 串首终结符的作用

串首终结符集对语法分析非常重要，因为在预测分析表的构建中，需要根据当前符号和下一个输入符号来决定采用哪个产生式进行推导。而串首终结符集可以帮助我们在构建预测分析表时快速确定当前符号的类型，从而提高语法分析的效率。

B. FOLLOW集：后继符号集

FOLLOW集的主要意义就是计算SELECT集

1) 定义

定义非终结符或者终结符$A$的后继符号集（FOLLOW集）为：

• 可能在某个句型中紧跟在$A$后边的终结符$a$的集合，记为$FOLLOW(A)$。

即：

$$FOLLOW(A)=\{a|S\Rightarrow^*\alpha Aa\beta,\ a\in V_T, \alpha,\beta\in(V_T\cup V_N)^*\}$$

其中：

• $a$表示终结符
• $\alpha$、$\beta$表示串

而某个非终结符的后继符号集可以通过产生式推导得知。例如对于上面的例子，$FOLLOW(B)={a,c}$

2) 结束符$

为了标记一个串的结尾，我们引入结束符$`。那么如果$A$是某个句型的的最右符号，则将结束符`$添加到$FOLLOW(A)$中

通过后继符号集，我们能够直接就判断出串ade是非法的。

C. SELECT集：产生式的可选集

1) 通过符号选择产生式

如果我们能够产生式和产生式能够生成的第一个符号的映射关系，那么我们就能够确定从开始符号到输入串，中间的推导使用了那些产生式。

构建语法树的时候就能够通过下一个符号来判断要选择使用哪个产生式：

例如我们给定如下的产生式和产生式生成的第一个符号的映射：

假设现在输入串ada，我们要求从语法开始符号S推导出串ada都使用了那些产生式。

1. 初始化阶段，token指针指向a
2. 首先使用了产生式1，因为开始符号只在产生式1中出现
   • token指针和a匹配，因此token指针指向d
   • 此时语法树为$S\Rightarrow aBC$
3. 接下来使用了产生式3，因为只有产生式3才可能生成d
   • token指针和d匹配，因此token指针指向a
   • 此时语法树为$S\Rightarrow adBC$
4. 接下来使用了产生式4，因为只有产生式4经过推导后可能生成a`
   • token指针不与a匹配，因此token指不移动，继续针指向a
   • 此时语法树为$S\Rightarrow adC$
5. 接下来使用了产生式6，因为只有产生式6才可能生成a
   • token指针和a匹配，因此token指针指向NULL
   • 此时语法树为$S\Rightarrow ada$
6. 此时已经将输入串完全匹配，匹配结束

从上面的例子，我们能够看出来，推导的关键就是要知道那个符号是由那个产生式产生的，因此我们才需要构建产生式的可选集。即遇到这个符号，就可以选择该产生式。

上面这种思想其实就是下面要详细讲解的预测分析法。但是实现上面这一根据输入串来得到推导过程中使用的产生式的关键就在于每个符号都确定了唯一的一个产生式。

例如：如果符号d对应产生式3和产生式5，那么上面推导到第三步就会有问题。

因此我们下面会介绍LL1文法

2) 产生式的可选集

定义产生式$A→\beta$的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为$SELECT( A→\beta)$。例如：

• 对于产生式$A\rightarrow a\beta$，$SELECT(A\rightarrow \beta)={a}$

可选集的含义是，遇到某个产生式的可选集内的符号，就可以选用这个产生式来进行推导

3) 可选集的计算

某个产生式的可选集，其实就是产生式右部的第一个非终结符的串首终结符集，即：

$$P\rightarrow AX_1X_2...X_N\\ SELECT(P) = FIRST(A)\\$$

G. LL1文法

我们称文法$G$是LL1文法，当且仅当$G$的任意两个具有相同左部的产生式$A → α | β$满足下面的条件：

• 如果$α$和$β$均不能推导出$ε$ ，则$FIRST(α)∩FIRST (β) =Φ$
• $α$和$β$至多有一个能推导出$ε$
  • 如果$β\Rightarrow^*ε$，则$FIRST (α)∩FOLLOW(A) =Φ$
  • 如果$α\Rightarrow^* ε$，则$FIRST (β)∩FOLLOW(A) =Φ$

定义的核心就是相同左部的产生式的SELECT集合不相交，即一个符号能确定唯一的一个产生式

下面我们会给出详细的例子

5. FIRST集、FOLLOW集、Select集、LL1文法举例

前面介绍了FIRST集、FOLLOW集、SELECT集和LL1文法，我们下面给出详细的例子。

A. FIRST集的计算

我们举下面的例子

FIRST集的定义为：

• FIRST(X)：可以从语法成分$X$推导出的所有串首终结符构成的集合

那么根据定义，如果产生式的右部第一个符号是一个终结符，那么这个终结符就在FIRST集中。因此就可以先写填写一些FIRST集：

此外，如果产生式能够推导出空串$\varepsilon$，那么空串也在FIRST集中。因此，继续填写一些FIRST集：

最后，如果产生式右部是一个非终结符，那么这个非终结符的FIRST集就肯定在左部的FIRST集中。因此，填写剩下的FIRST集：

所以，FIRST集的算法如下：

算法比较抽象，还是记住上面的三个规则

B. FOLLOW集的计算

我们接下来举一个计算FOLLOW集的例子：

FOLLOW集的定义为：

• FOLLOW(A)可能在某个句型中紧跟在$A$后边的终结符的集合

计算FOLLOW集要逐产生式的去计算。即从第一个产生式开始，依次计算所有出现过的符号。因此我们先从第一个产生式开始计算。

首先，如果一个非终结符是某个句型的最后一个符号，那么他的FOLLOW集就肯定有结束符$。例如：

• $E$本身作为开始符号，子集就能够成为一个矩形，所以他的FOLLOW集中一定有$

此外，一个非终结符的FOLLOW集实际上和下个非终结符的FIRST集有关。例如：

• $T$后面可能得符号有：$E’$（产生式1、产生式2）

因此，我们要$T$的FOLLOW集中一定包含了$E’$FIRST集中的所有元素。

注意，如果一个非终结符的FIRST集含有空串，就表示这个终结符可以推导出空串。因此在填写的时候，需要把FIRST集中的空串改为结束符$。

如果一个符号是产生式右部的最后一个符号，那么左部的FOLLOW集应该包含在这个符号的FOLLOW集中。例如第一个产生式，$E$后面能接的符号$E’$都能接，因此把$E$的$加入到$E’$的FOLLOW集中

若某个符号后面的符号可能为空，那么上面这个规则也使用。例如下面分析产生式3的时候

至此，第一个产生式分析结束

然后分析第二个产生式。由于第二个产生式的右部中，$T$、$E’$的位置和第一个产生式中的位置是一样的，因此不会为FOLLOW(T)和FOLLOW(E')中带来新的元素。

接着分析第三个产生式。规则一，T'的FIRST集可以加入到F的FOLLOW集中。

如果某个符号后面的符号可能都为空，那么注意还要用规则三，所以$F$的FOLLOW集还包含$T$的FOLLOW集

而后$T’$的是规则三，故$T’$的FOLLOW集应该包含$T$的FOLLOW集

接下来分析产生式4。由于$F$和$T’$位置和产生式3是一样的，所以不会带来更多的结果。

最后对于产生式5，会给E后面添加)

注意由于规则三，所以导致$E’$的FOLLOW集依赖$E$的FOLLOW集、$T’$的FOLLOW集依赖于$T$的FOLLOW集。因此规则四就是，如果后面的产生式修改了前面的FOLLOW集，那么就需要重新从产生式1开始在分析一次。

在第二次遍历的时候，分析有：

• $E’$依赖于$E$
• $T$依赖于$E$（$E’$为空）
• $T’$依赖于$T$

所以，所有的产生式中都需要添加)

所以，我们给出FOLLOW集的算法为：

C. SELECT集的计算

计算得到了FIRST集和FOLLOW集后，我们就能计算产生式的SELECT集

依据前面介绍的计算SELECT集的方法，针对每一个产生式：

• 如果右边第一个符号是非终结符的话，等于右部第一个非终结符的FIRST集合
• 如果右部是空串话，那么就是左部的FOLLOW集
• 如果右部第一个符号是终结符的话，那么就是就是这个终结符

例如给定下下面的文法和对应的FIRST集和FOLLOW集，我们计算其SELECT集

由于上面这个文法相同左部的产生式的SELECT集不想交，因此是一个LL1文法

6. 预测分析法

上面在介绍SELECT集合和LL1文法的时候，我们其实已经举了一个预测分析法的例子。我们这里首先介绍一下预测分析法的工作过程，然后给出预测分析法在进行时候会用到的预测分析表

A. 预测分析法的工作过程

预测分析法的工作过程为：

• 从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符$A$和当前输入符号$a$，选择正确的$A\rightarrow$产生式。为保证分析的确定性，选出的候选式必须是唯一的

其核心就在于：

• 预测分析法每次都能选出正确的、唯一的候选式

例如我们给定如下的产生式和产生式生成的第一个符号的映射：

假设现在输入串ada，我们要求从语法开始符号S推导出串ada都使用了那些产生式。

1. 初始化阶段，token指针指向a
2. 首先使用了产生式1，因为开始符号只在产生式1中出现
   • token指针和a匹配，因此token指针指向d
   • 此时语法树为$S\Rightarrow aBC$
3. 接下来使用了产生式3，因为只有产生式3才可能生成d
   • token指针和d匹配，因此token指针指向a
   • 此时语法树为$S\Rightarrow adBC$
4. 接下来使用了产生式4，因为只有产生式4经过推导后可能生成a`
   • token指针不与a匹配，因此token指不移动，继续针指向a
   • 此时语法树为$S\Rightarrow adC$
5. 接下来使用了产生式6，因为只有产生式6才可能生成a
   • token指针和a匹配，因此token指针指向NULL
   • 此时语法树为$S\Rightarrow ada$
6. 此时已经将输入串完全匹配，匹配结束

B. 预测分析表

预测分析法最关键的，就是对输入串进行扫描的时候，能够根据当前token指针指向的token选择出适用的产生式