Focus on FE learning

本篇笔记将继续讲解编译的第二步：自顶向下语法分析。

下面是这篇笔记的思维导图：

注意：以下的所有分析基于上下文无关文法。

1. 语法分析

1.1 语法分析器

在词法分析中，我们扫描输入源程序的每个字符，得到多种类型的单词（token），一系列的单词就构成了一条单词流。可以设想，单词流的某个部分有多个并排的单词，它们可能会构成某个句子，但是这个句子是否真的符合语法规则呢？我们需要借助语法分析器才能进行判断。更直接点，我们可以说语法分析器是用来判断句子是否符合某个给定的上下文无关文法的。

1.2 语法分析的方法

本篇笔记主要讲解自顶向下语法分析。要判断句子是否符合某个给定的上下文无关文法，可以尝试从文法的开始符号出发，若经过一系列推导之后可以得到完全匹配原句子的句子，则可以说原句子来自于给定的文法。

2. 自顶向下语法分析存在的问题

自顶向下分析的核心思路是：对任何需要分析的输入串，从文法的开始符号出发，试图用一切可能的方法，结合文法的产生式，自上而下地构造一棵基于输入串的语法树。但在这个过程中存在着一个问题，这个问题概况地说就是文法的不确定性。为什么说具有一种不确定性呢？我们可以从以下三个方面一一分析。

2.1 左递归

① 定义

其一，文法存在的左递归带来了不确定性。

如果一个文法存在非终结符 P 使得 P +⇒ Pa，那么这个文法就是含有左递归的。它的意思其实是说，当我们试图用 P 的右部去替换 P 这个非终结符的时候，替换得到的结果再次含有 P，若此时无法匹配输入的字符，则我们不得不对 P 进行又一轮的替换，反反复复，陷入了无限循环，始终没有找到递归的出口。

② 消除

我们并不希望一个文法存在不确定性，所以需要想办法消除文法的左递归。对于简单的左递归，我们的消除规则如下：若存在递归产生式 P → Pα|β，则将其改写为：P → βP‘，P’ → αP‘| ε。

比如说存在如下的文法：

E →  E + T|T
T → T * F|F
F → (E)|i

它的第一条和第二条产生式都是递归的，需要消除递归。将产生式与规则一一对应，那么 +T 就代表 α，T 就代表 β，所以 E → E + T|T 改写为 E → TE' 和 E'→ +TE'|ε；同理，*F 代表 α，F 代表 β，所以 T → T * F|F 就改写为 T → FT' 和 T → *FT'|ε。

对于更一般性的左递归，我们的消除规则如下：若存在递归产生式 P → Pα1|Pα2|...|Pαm|β1|β2|β3|βn（右部的一部分含左部，一部分不含），则将其改写为：P → |β1P'|β2P'|...|βnP' 和 P’ → α1P'|α2P‘|...|αmP’| ε

比如说存在如下的文法：

S → Qc|c
Q → Rb|b
R → Sa|a

看起来它似乎不是左递归文法，但其实经过 S ⇒ Qc ⇒ Rbc ⇒ Sabc 的推导后，会发现它其实也是左递归文法。这种不太明显的、需要经过替换才能体现递归性的，称之为间接左递归。我们将上面推导过程中使用过的产生式逆序排列，得到下面等价的文法：

R → Sa|a
Q → Rb|b
S → Qc|c

如何消除左递归呢？首先将第一条产生式代入第二条，得到 Q → Sab|ab|b，它仍然不包含左递归，所以继续代入第三条，得到 S → Sabc|abc|bc|c，它包含直接左递归，所以按照前面说过的一般左递归的消除方法对其进行处理，得到 S → (abc|bc|c)S' 和 S‘ → abcS’|ε。由于 Q 和 R 的相关产生式已经包含在里面，所以这两条产生式就构成了已经消除左递归的等价文法。

2.2 回溯

其二，文法存在的回溯带来了不确定性。

比方说对于文法 {Z → cAd,A → ab|a} 以及输入符号串 S = cad，当 A 面对输入符号 a 的时候，到底应该用 A → ab|a 的第一个还是第二个右部去替换呢？看起来好像都可行，但若选取了第一个右部，则后面会发现 b 无法匹配 d，所以这个选取是错误的。我们需要回溯到 A 产生子树之前，令其产生 a 子树而不是 ab 子树。设想产生式的右部如果是 ab|ac|ad|...|az，是不是意味着我们需要做更多的尝试/回溯呢？这会大大降低语法分析的效率，而这是我们不希望看到的。所以有必要消除回溯。

在这之前，我们先考虑如何更加准确地判断某个文法是否存在回溯的情况。这里我们要引入一个 First 集的概念。

① First 集

First 集又叫终结首符集，对非终结符 A 的每一个右部 m 都存在着一个 First 集，集合中的元素都是 m 的所有可能推导的开头终结符或者可能的 ε。比如上面的 A → ab|a ，A 的右部是 ab 或者 a，ab 或者 a 的推导（在这里是它们自身）的开头终结符就是 a，所以 First(ab) = First(a) = {a}。

② 如何判断无回溯

对于非终结符 A，它的每一个右部都会产生对应的 First 集，若这些集合两两不相交，即 First(ai) ∩ First(aj) = Ø，那么至少对于 A 而言，它是不存在回溯的。比如，A → ab|cd|ef ，每一个右部的 First 集两两之间都没有交集，那么 A 就是没有回溯的，当它面对一个输入符号（比方说 a，c，e）的时候，它可以确切地让一个右部去进行替换，而无需担心替换失败、需要回过头来选择其它右部的情况。

③ 如何克服回溯

不幸的是，大部分情况下，很多非终结符都存在回溯的情况。不过，我们可以通过提取左公因子来克服这种回溯。比如说产生式 A → ab|ac|ad|...|az，可以提取公因子 a，改写为 A → a(b|c|d|...|z)，再改写得到 A → aX 和 X → (b|c|d|...|z)。至少这个时候，对于 A 而言它已经不存在回溯的情况，毕竟它只有一个右部了。当然，对于 X，它依然可能存在回溯，比如说 b=mn，c = ml，诸如此类，若存在这种情况，我们就再次提取公因子。这样反复提取之后，我们可以确保所有非终结符的右部的 First 集都不存在交集，因此得以消除回溯。不过，这样的代价就是引入了大量的非终结符作为替换时的过渡。

2.3 空符号串

我们已经消除了左递归和回溯，这样文法是不是就真的确定了呢？其实不是，因为我们还得考虑空符号串的问题。简单地说，假设左部为非终结符 A 的产生式，它有一个右部是 ε，且 A 当前面对的输入符号为 a，那么到底要不要用 ε 去替换掉 A 呢？如果不使用 ε，至少说明了 A 存在其它右部足以处理输入符号 a，也许刚好就是 a，或者是以 a 开头的符号串；如果使用 ε，则意味着 A 放弃了处理 a 的任务，这其中隐含的意思是，A 自己无法处理 a，但是它确信在语法树中，排在自己右边的非终结符足以处理 a。不过，这样的非终结符是否确实存在？这时候，我们引入了另一个新的概念，即 Follow 集。

① Follow 集

Follow 集又叫做后跟符号集，对某个非终结符 A存在着一个 Follow 集，集合中的所有元素都是开始符号 S 与 A 之间的相关推导中，紧跟着出现在 A 右边的终结符。比如说存在文法 {S → Bc,B → Aa,A → de}，要求 A 的 Follow 集，那么 S 与 A 之间就存在着一个相关推导为 S → Aac，紧跟着 A 后面的是终结符 a，所以 Follow(A)={a}；如果是要求 S 的 Follow 集呢？S 与 S 之间的相关推导就是 S → S，可以看到 S 右边没有紧跟着终结符，这时候我们就规定 Follow(S)={ # }。

② 空符号串的处理

有没有注意到 Follow 集的定义刚好与我们谈到的空符号串的处理有相关的地方？—— 空符号串 ε 如果被使用，说明语法树中 A 的右侧存在着另一个非终结符可以处理当前输入符号，而 Follow(A) 代表的又是语法推导中位于 A 的右侧的那些终结符，那么，重点来了，假设 Follow(A) 中刚好就包含当前输入符号，那么就说明 A 的推导的右侧存在着终结符 a，而这个 a 是由 A 右侧的非终结符推导得到的。换句话说，当 Follow(A) 中刚好就包含当前输入符号的时候，我们可以肯定，存在着某个非终结符可以处理当前输入符号，并使得 A 可以用空符号串 ε 进行代替，而无需去处理当前输入符号。

所以，我们通过求解 Follow(A) ，消除了**考虑是否需要用空符号串替代 A **的不确定性。我们可以看下面这个例子再来理解一下。假定有文法：

S → aA|d
A → bAS|ε

若输入符号串为 abd，尝试推导该符号串是否符合给定的文法：

第一个输入符号是 a，程序经过判断，决定使用 S → aA 开始构造语法树，这样就处理了第一个输入符号 a；
第二个输入符号是 b，程序经过判断，决定使用 A → bAS 将 A 替换，这样就处理了第二个输入符号 b；
第三个输入符号是 d，程序此时如何判断呢？查看 First(A)，发现不包含 d，所以 A 是无法直接处理当前输入符号 d 的，那么它是否应该用 ε 替换掉，并让 S 去处理 d 呢？查看 Follow(A)，发现刚好是包含 d 的，所以这里用 ε 替换 A
当前输入符号还是 d，用 d 替换 S，成功处理完第三个输入符号 d。

③ 如果 First 集和 Follow 集有交集…

到了这里，可能会产生一个疑问：既然 A 的 First 集在某种程度上决定了非终结符 A 自身是否足以处理当前输入符号，而 A 的 Follow 集在某种程度上决定了 A 右侧的非终结符是否足以处理当前输入符号，那么如果 First(A) 和 Follow(A) 都包含了当前输入符号，好像就说明了 A 和右侧非终结符都能处理输入符号了？这时候要让谁来处理呢？其实这里又带来了一种不确定性，这同样是我们不希望看到的。

3. LL(1) 文法

3.1 定义

上面说了这么多东西，又要求文法不存在左递归、又要求没有回溯，还要求非终结符的 First(A) 和 Follow(A) 最好没有交集，那么是否存在某种文法可以满足所有这些条件呢？—— 有的，那就是 LL(1) 文法。 LL(1) 文法是确定的，只有基于这种确定的文法，我们才能进行确定的自顶向下分析。联系上面我们分析导致文法不确定的因素的过程，可以给出 LL(1) 文法的定义如下：

必须不包含左递归
对于每个非终结符，它的各个右部的 First 集两两不相交
对于每个非终结符，如果它的 First 集包含 ε ，则它的 First 集和 Follow 集不相交

因为我们前面已经经过了分析，会发现这里要理解 LL(1) 文法的定义，相对容易很多，而且我们也知道它为什么要这么定义，对他的来龙去脉有一个清晰的理解。

3.2 判断

那么，如何判断一个文法是否属于 LL(1) 文法呢？我们可以选择用定义判断，也可以结合稍后介绍的 select 集进行判断。以下面这个文法为例：

S → aA|d
A → bAS|ε

① 基于定义进行判断

显而易见，它不存在左递归
分析 S 的各个右部，aA 的 First 集为 {a}，d 的 First 集为 {d}，两个集合不相交；分析 A 的各个右部，bAS 的 First 集为 {b}，ε 的 First 集为 {ε}，两个集合也不相交。所以，文法的每个非终结符的候选 First 集两两都不相交
A 的 First 集为 {ε,b} ，它的 Follow 集为 { a,d,# }，两者不相交（注意不要漏掉 #，因为 S → aA 也是 S 和 A 之间的相关推导）

由于该文法符合 LL(1) 文法的定义，所以它属于 LL(1) 文法。

② 基于 select 集进行判断

对于给定文法的每一条产生式，select 集的规则如下：

如果产生式右部无法推导出 ε：该产生式的 select 集为产生式右部的 First 集
如果产生式右部可以推导出 ε：该产生式的 select 集为产生式右部的 First 集去除 ε ，并上产生式左部的 Follow 集

求解给定文法的每一条产生式，若左部相同的产生式两两之间的 select 集不相交，则该文法属于 LL(1) 文法。

以上面为例，我们可以得到如下四条产生式：

S → aA
S → d
A → bAS
A → ε

对应的 select 集为：

select(S → aA) = First(aA) = {a}
select(S → d) = First(d) = {d}
select(A → bAS) = First(bAS) = {b}
select(A → ε) = (First(ε)-{ε}) U Follow(A) = { a,d,# }

对左部相同的产生式的 select 集，两两之间求交集：

select(S → aA) U select(S → d) = Ø
select(A → bAS) U select(A → ε) = Ø

发现都是不相交的，根据上面的规则，可以判断该文法属于 LL(1) 文法。

4. 递归下降分析程序

这一节没有重点讲解，可以略过。

当一个文法满足 LL(1) 条件时，我们可以选择构造一个不带回溯的自上而下分析程序。这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符，这种分析程序称为递归下降分析器。如果用某种高级语言写出所有递归过程，那就可以用这个语言的编译习题来产生整个分析程序了。

4.1 扩充的巴科斯范式

用花括号 {α} 表示闭包运算 α*
用 {α}_n^0 表示 α 可以任意重复 0 次到 n 次， {α}_n^0 = α^0 = ε
用方括号 [α] 表示 {α}_1^0 ，即表示 α 的出现可有可无（等价于 α|ε ）

4.2 编写递归下降分析程序

对于给定的文法，可以利用扩充的巴科斯范式进行改写：

E → T|E + T
T → F|T * F
F → (E)|i
// 改写为
E → T{+T}
T → F|{*F}
F → (E)|i

PS：也可以用语法图表示改写后的结果，这会更加直观：

基于改写后的文法或者是语法图，可以构造如下的递归下降分析程序（ADVANCE 表示扫描下一个输入符号，SYM 表示当前输入符号，ERROR 表示出错纠察处理程序）：

5. 预测分析程序

使用高级语言的递归过程描述递归下降分析器，只有当具有实现这种过程的编译系统时才有实际意义，构造预测分析程序是实现 LL(1) 分析的另一种有效方式。

4.1 主要流程

借助 LL(1) 预测分析程序，可以进行语法分析：

预测分析程序的核心是借助一张分析表以及一个栈。分析表是一个 M[A,a] 形式的矩阵，A 表示非终结符，a 表示终结符或者 #，矩阵的每一个元素 M[A,a] 都存放着一条关于 A 的产生式，表示当 A 面对输入符号 a 的时候应该使用什么样的右部去进行替换；元素也可能存放一个出错标志（在表中用空白表示），这时候表示分析出错：

栈中一开始放的是栈底的 # 以及栈顶的文法开始符号，在预测分析程序运行的整个过程中，栈中元素会不断发生变动：

当栈顶为 A，面对输入符号 a 的时候，这时候视情况有三种可能的操作：

A = a = #，此时成功完成分析，语法分析通过
A = a ≠ #，此时 A 出栈，扫描下一个输入符号
A∈V_N，则根据 M[A,a] 到分析表中查询对应元素，该元素可能为产生式或者一个错误标志：若为产生式，则栈顶元素出栈，让产生式右部逆序依次进栈；若为错误标志，则分析出错，语法分析不通过。

4.2 具体分析

在正式进行预测分析之前，还需要解决几个问题：首先，文法未必是 LL(1) 文法，可能需要先对文法进行处理，消除左递归和回溯；其次，需要构造一张预测分析表以用于后续的预测分析，做完这些准备工作，最后才是预测分析。我们现在以一个例子来讲解整个流程。假设给定如下文法和输入符号串：

// 文法
E → E + T|T
T → T * F|F
F → i|(E)
// 输入符号串
i + i * i

符号串是否符合给定文法呢？我们试着用预测分析程序进行语法分析。

① LL(1) 判断

有没有左递归？

很明显，这个文法存在直接左递归，为了方便后续工作的开展，这里先消除左递归。根据左递归消除的规则，将原文法改写为如下的等价文法：

E → TE'
E' → +TE'|ε
T → FT'
T' → *FT'|ε
F → i|(E)

有没有回溯？

尝试基于 select 集判断文法是否存在回溯。为了方便，这里先计算出 First 集和 Follow 集。

产生式右部的 First 集：

First(TE') = {i,(}
First(+TE') = {+}
First(ε) = {ε}
First(*FT) = {*}
First((E)) = {(}

非终结符的 Follow 集：

从 E 到 E，存在相关推导 E ⇒ E 和 E ⇒ (E)T'E'，所以 Follow(E) = { ),# }
从 E 到 E’，存在相关推导 E ⇒ TE' 和 E ⇒ TE' ⇒ T+TE' ⇒ T+FT'E' ⇒ T+(E)T'E' ⇒ T+(TE')T'E'，所以 Follow(E') = { ),# }
从 E 到 T，存在相关推导 E ⇒ TE' ⇒ Tε ⇒ T ， E ⇒ TE'⇒ T+TE' ， E ⇒ TE'⇒ T+TE'⇒ FT'+TE' ⇒ (E)T'+TE' ⇒ (TE')T'+TE' ⇒ (Tε)T'+TE'⇒ (T)T'+TE' ，所以 Follow(T) = { +,),# }
从 E 到 T’，存在相关推导 E ⇒ TE' ⇒ FT'E' ⇒ FT'ε ， E ⇒ TE' ⇒ FT'E' ⇒ FT'+TE‘， E ⇒ TE' ⇒ FT'E' ⇒ FT'ε ⇒ F*FT’ ⇒ F*(E)T' ⇒ F*(TE')T' ⇒ F*(FT'E')T' ⇒ F*(FT')T，所以 Follow(T') = { +,),# }
从 E 到 F，存在相关推导 E ⇒ TE' ⇒ FT'E ⇒ F*FT'E'， E ⇒ TE' ⇒ FT'E ⇒ F*FE' ⇒ F*F， E ⇒ TE' ⇒ FT'E ⇒ F*FE' ⇒ F*(E) ⇒ F*(TE') ⇒ F*(FT'E') ⇒ F*(F)，E ⇒ TE' ⇒ FT'E ⇒ FT'TE'⇒ FT'T+TE ⇒ FT'FT'+TE ⇒ FT'F+TE 所以 Follow(T') = {*,#,),+}

整个过程相当之麻烦，因为要尝试各种可能的组合，找出所有推导中每个非终结符后面可能跟着的终结符。但是我们可以稍微换个角度想一想，与其去求非终结符后面可能存在的终结符，不如先假设后面一定存在某个终结符，并尽可能地朝着那个方向进行替换。这并不会减轻我们的大部分工作，但是有目标总比没目标要来的轻松。

现在已经计算出 First 集和 Follow 集，接着计算各条产生式的 select 集就会轻松很多了：

select(E → TE') = {i,(}
select(E' → +TE') = {+}
select(E' → ε) = { ε,),# }
select(T → FT') = {i,(}
select(T' → *FT') = {*}
select(T' → ε) = { ε,+,),# }
select(F → i) = {i}
select(F → (E)) = {(}

左部相同的产生式，其 select 集两两之间不相交，所以可以确定该文法为 LL(1) 文法。

若某个非终结符的 First 集存在空符号串，该 First 集和 Follow 集是否会相交？

观察 E' → +TE'|ε 和 T' → *FT'|ε 这两条产生式，会发现 E‘ 和 T’ 这两个非终结符的 First 集存在空符号串 —— 所以要分别对 E‘ 和 T’ 求 First 集和 Follow 集，看是否会与各自的 First 集相交。

我们上面已经求了 Follow 集，分别是 { ),# } 和 { #,),+ }，这里可以求 First 集，分别是 {+，ε} 和 {*,ε}，可以看出 Follow 集和对应的 First 集不相交。

综上，我们已经将这个文法改写为等价的 LL(1) 文法。

② 构造预测分析表

我们在上面求出 select 集，不仅仅是为了检测文法是否属于 LL(1) 文法，也是为了构造预测分析表。要构造构造预测分析表，首先写好基本结构，即行头（非终结符）和列头（终结符）：

如何填充矩阵的元素呢？我们把上面求出的 select 集拿过来：

select(E → TE') = {i,(}
select(E' → +TE') = {+}
select(E' → ε) = { ε,),# }
select(T → FT') = {i,(}
select(T' → *FT') = {*}
select(T' → ε) = { ε,+,),# }
select(F → i) = {i}
select(F → (E)) = {(}

针对每一个终结符 x，若终结符 x 存在于 select(X → Y) 中，则将产生式 X → Y 填入非终结符 X 对应于终结符 x 的矩阵元素中。再填充完所有能找到的元素之后，剩下未填充的一律留白，作为错误标志。

比如说，终结符 i 存在于 select(E → TE') = {i,(}，select(T → FT') = {i,(}，select(F → i) = {i} 中，那么就把 E → TE' 填入 E 对应于 i 的矩阵元素中，把 T → FT' 填入 T 对应于 i 的矩阵元素中，以此类推。所以，我们最终得到了如下的预测分析表：

③ 进行预测分析

经过“长途跋涉”，终于可以针对输入符号串 i + i * i# 开始我们正式的预测分析过程了！首先准备一个栈、一个输入符号列表和一个所用产生式列表：

栈	输入符号	所用产生式
#E	…	…

正如之前所说，一开始栈里是 #E，首先输入的符号是 i，对照预测分析表，找到我们要使用的产生式：

栈	输入符号	所用产生式
#E	i	`E → TE'`

因为栈顶元素和输入符号不等，所以栈顶元素出栈，产生式右部逆序进栈，输入符号不变。此时再对照预测分析表，找到我们要使用的产生式：

栈	输入符号	所用产生式
#E	i	`E → TE'`
#E’T	i	`T → FT'`

同理，栈顶元素出栈，产生式右部逆序进栈，输入符号不变，改变所用产生式：

栈	输入符号	所用产生式
#E	i	`E → TE'`
#E’T	i	`T → FT'`
#E’T‘F	i	`F → i`

继续出栈和进栈：

栈	输入符号	所用产生式
#E	i	`E → TE'`
#E’T	i	`T → FT'`
#E’T‘F	i	`F → i`
#E’T‘i	i	匹配

栈顶元素和输入符号匹配，且不等于 #，此时就让栈顶元素出栈，同时扫描下一个输入符号，找到对应的产生式：

栈	输入符号	所用产生式
#E	i	`E → TE'`
#E’T	i	`T → FT'`
#E’T‘F	i	`F → i`
#E’T‘i	i	匹配
#E’T‘	+	`T' → ε`

继续出栈和进栈：

栈	输入符号	所用产生式
#E	i	`E → TE'`
#E’T	i	`T → FT'`
#E’T‘F	i	`F → i`
#E’T‘i	i	匹配
#E’T‘	+	`T' → ε`
#E’	+	`E' → +TE'`

此后的过程类似，这里就不一一展示了。在某个时刻，我们到达下面这个状态：

栈	输入符号	所用产生式
#E	i	`E → TE'`
#E’T	i	`T → FT'`
#E’T‘F	i	`F → i`
#E’T‘i	i	匹配
#E’T‘	+	`T' → ε`
#E’	+	`E' → +TE'`
…	…	…
#E’	#	`E' → ε`

在这个状态下继续往后执行：

栈	输入符号	所用产生式
…	…	…
#E’	#	`E' → ε`
#	#	匹配且等于 #

这时候，栈顶元素等于输入符号等于 #，说明成功完成了分析，符号串是符合该文法的。

4.3 错误处理

具体对错误的处理，我们可以向预测分析表中引入同步符号。针对每一个非终结符 X，如果他的 Follow 集包含终结符 x，则把矩阵对应的元素 [X,x] 加上同步符号，表示将 x 加入 X 的同步符号集。因此，我们得到了如下的预测分析表：

这样，在进行分析的时候，如果矩阵元素还是空，则跳过当前输入符号；如果矩阵元素为 synch，则弹出栈顶非终结符；如果栈顶终结符和输入符号不匹配，则弹出栈顶终结符。

6. 更简单地构造 Follow 集和分析表

上面构造 Follow 集和分析表存在的问题：

求解 Follow 集采用的是定义推导的方式，基本上需要穷举各种可能的情况，太过繁琐
构造分析表之前额外求解了 Select 集，其实这不是必要的，完全可以只通过 First 集和 Follow 集构造

这里补充介绍更加简便的方法。

首先我们的目标文法不变，还是这个：

E → TE'
E' → +TE'|ε
T → FT'
T' → *FT'|ε
F → i|(E)

因为这次不使用 Select 集，所以只需要求解非终结符的 First 集，而不是产生式右部的 First 集。这里直接写结果：

First(E) = First(T) = First(F) = {i,(}
First(E') = {+,ε}
First(T') = {*,ε}

6.1 构造 Follow 集

依次使用下面的规则构造各条产生式的 Follow 集：

① # 属于 Follow(S)（S 表示开始符号）

② 遍历每一条产生式，尝试将产生式用 A -> αBβ 的格式代替，若符合格式，则有 First(β)-{ε}∈Follow(B)

③ 遍历每一条产生式，尝试将产生式用 A -> αB 的格式代替；或者用 A -> αBβ 且 ε∈First(β)代替，若符合格式，则有 Follow(A)∈Follow(B)

④ 综上上面所求的所有 Follow 集

以上面的文法为例，尝试构造 Follow 集：

① # 属于 Follow(E)

② 遍历每一条产生式：

E → TE'：E 对应 A，T 对应 B，E‘ 对应 β，所以 First(E')-{ε}∈Follow(T)={+}
E' → +TE'|ε：E’ 对应 A，T 对应 B（不能让 E‘ 对应 B，否则 β 为空，无意义），E’ 对应 β，后面的过程和上一条推导重复了，故忽略本条产生式
T → FT'：T 对应 A，F 对应 B，T‘ 对应 β，所以 First(T')-{ε}∈Follow(F)={*}
T' → *FT'|ε：T’ 对应 A，F 对应 B，T’ 对应 β，后面的过程和上一条推导重复了，故忽略本条产生式
F → (E)|i：F 对应 A，E 对应 B，）对应 β，所以 First())∈Follow(E)={)}，加上在 ① 中求出的 Follow(E)，故 Follow(E)={ #,) }

③ 遍历每一条产生式：

E → TE'：E 对应 A，T 对应 α，E‘ 对应 B，所以 Follow(E)∈Follow(E')={ #,) }；换种方式，E 对应 A，T 对应 B，E’ 对应 β，且 ε∈First(E')，所以 Follow(E)∈Follow(T)={+,#,)}；或者，E 对应 A，T 对应 α，E‘ 对应 B，且 ε∈First(ε)，所以 Follow(E)∈Follow(E')={ #,) }，这和最开始的推导重复了，故忽略之
T → FT'：T 对应 A，F 对应 α，T‘ 对应 B，所以 Follow(T)∈Follow(T')={+}；换种方式，类似上面的，可以推导得到 Follow(F)={ *,+,),# }，以及得到 Follow(T')={ +,),# }
E' → +TE'|ε：E’ 对应 A，+T 对应 α，E’ 对应 B，所以 Follow(E')∈Follow(E')，忽略之；换种方式，E’ 对应 A，+ 对应 α，T 对应 B，E‘ 对应 β，因为 Follow(E') 本身已经属于Follow(T)，故忽略之
T' → *FT'|ε：整个过程类似上面的，没有得到新的推导结果，故忽略之
F → (E)|i：F 对应 A，( 对应 α，E 对应 B， ) 对应 β，但是 ) 无法推导得到 ε，所以忽略之

④ 综上，Follow 集如下：

Follow(E) = Follow(E’) = { ),# }
Follow(T) = Follow(T’) = { +,),# }
Follow(F) = { *,+,),# }

6.2 构造分析表

要构造构造预测分析表，首先写好基本结构，即行头（非终结符）和列头（终结符）：

如何填充矩阵的元素呢？我们把上面求出的 First 集和 Follow 集拿过来：

First(E) = First(T) = First(F) = {i,(}
First(E') = {+,ε}
First(T') = {*,ε}

Follow(E) = Follow(E’) = { ),# }
Follow(T) = Follow(T’) = { +,),# }
Follow(F) = { *,+,),# }

查看 [E,i] 对应的单元格，将 E → TE' 填入，查看 [E,(] 对应的单元格，同样将 E → TE' 填入
查看 [T,i] 和 [T,(] 对应的单元格，这里和上面一样
查看 [F,i] 对应的单元格，将 F → i 填入；查看 [F,(] 对应的单元格，将 F → (E) 填入
查看 [E’,+] 对应的单元格，将 E‘ → +TE’ 填入；查看 [E‘,ε] 对应的单元格，注意这里遇到了 ε，转到 Follow 集查看，来到 Follow(E’)={ ),# }，将 [E’,)] 和 [E',#] 对应的单元格都填入 E'->ε

总之，优先以 First 集为准，查看每个单元格，并将相应的产生式放进去，若遇到 ε，则跳转到 Follow 集查看。后面的情况都是类似的，这里就不一一说明了，最后还没填充的单元格一律空着即可。

所以，我们最终得到了如下的预测分析表：

编译原理学习笔记（5）：自顶向下语法分析