构造LR预测分析表：FIRST与FOLLOW集

1. FIRST 集

顾名思义，“第一个” + “集合”，也就是

FIRST(A) 表示 A 所能推导出的串的首终结符构成的集合

举个例：

有文法：
	A ——> aB
那么 FIRST(A) = {a}，因为
	A ——> a...

那么如何求解呢？分三种情况：

能推出空串：

本文中我用 ‘’ 表示空串

A ——> B | ''
那么 '' 应该被加入到 FIRST(A) 中

注：
如果有
	A ——> B
	B ——> ''
那么 A 也能推出空串，也就是说：
'' 应该被加入到 FIRST(A) 中。

产生式体的首字符为非终结符：

A ——> B
A 能推导出的串显然依赖于 B，因此
FIRST(B) 应该被加入到 FIRST(A) 中
或者说 FIRST(A) = FIRST(B)

产生式体的首字符为终结符：

A ——> aB
无论 B 能推导出什么，显然 
A 能推导出的串的首字符一定是 a；
因此 a 应该被加入到 FIRST(A) 中。

'这也可以换一种理解方式'：
FIRST(A) = FIRST(aB) =
FIRST(a) = { a }

来个综合的例子：

(0) E ——> TG
(1) G ——> +TG | ''
(2) T ——> FU 
(3) U ——> *FU | ''
(4) F ——> (E) | id

对于（1）式，由于 E 的产生式体的首字符为非终结符 T，因此有 FIRST(E) = FIRST(T)；
同理（2）式有 FIRST(T) = FIRST(F)，也就是

FIRST(E) = FIRST(T) = FIRST(F)

那么看 F 的产生式（4）式，由于其产生式体首字符都是终结符，因此 FIRST(F) = { (, id }，也就是说

FIRST(E) = FIRST(T) = FIRST(F) = { (, id }

现在还剩（1）、（3）式，两个产生式形式基本相同：产生式体首字符是终结符，能推导出空串，因此：

FIRST(G) = { +, ‘’ }
FIRST(U) = { *, ‘’ }

FIRST集计算完毕。

2. FOLLOW 集

**“跟在后面的” + “集合”，也就是

FOLLOW(A) 表示能出现在 A 的后面的第一个终结符集合

比如

A ——> Ba
对于 B 而言，在这个产生式中，
B 后面紧跟的第一个终结符为 a，
因此 a 应加入 FOLLOW(B)

求解方式分四种：

应将 $ 加入开始符号的 FOLLOW 集

$ 表示输入结束标记字符
```
S ——> A
A ——> a
那么 $ 应加入 FOLLOW(S)
```

后面紧跟着终结符

S ——> Aa
那么 a 应加入 FOLLOW(A)

后面紧跟着非终结符

S ——> AB
由于 A 后面是 B，那么
FIRST(B) 应加入 FOLLOW(A) 中

产生式体末尾是非终结符

S ——> ABC
C ——> ''

1. FOLLOW(S) 应加入到 FOLLOW(C) 中；

由于 S ——> ABC，那么 S 等价于就是 ABC，
显然 FOLLOW(S) 应加入到 FOLLOW(C) 中; 
但注意 FOLLOW(S) 不一定等于 FOLLOW(C)。
"一种理解方式"：
S 和 C 都是 S 文法定义的语言的某语法成分，
但是 S 显然比 C 更大；
如果 C 只出现在 S 的末尾，
那么 FOLLOW(C) = FOLLOW(S)；
但如果 C 还出现在了 S 的中间，比如
	S ——> ACBC
那么可能有 FOLLOW(S) < FOLLOW(B) 

2. 如果 
	C 能推出空串 (或者 '' 属于 FIRST(C))
那么 
	FOLLOW(S) 应加入 FOLLOW(B) 中。

当 C ——> '' 时，那么 S 等价于 AB，因此 
FOLLOW(B) 应加入到 FOLLOW(A) 中。

3. 依次类推，直到出现
   第一个不能推出空串的非终结符

同样的例子：

(0) E ——> TG
(1) G ——> +TG | ''
(2) T ——> FU 
(3) U ——> *FU | ''
(4) F ——> (E) | id

FOLLOW集的分析比 FIRST集复杂得多，一不小心就容易漏掉个别情况。对此我建议采用以下方法进行求解：

先将 $ 加入 FOLLOW(开始符号)
分析产生式右部
分析产生式整体
从 (0) - (4) 依次分析，如果有 FOLLOW集改变，执行依次更新操作

将 $ 加入 FOLLOW(开始符号)

FOLLOW(E) = { $ }
分析产生式（0）的右部
```
TG
```
由于 T 后面紧跟的是非终结符 G，因此 FIRST(G) = { +, ‘’ } 应加入 FOLLOW(T)

FOLLOW(T) = { + }
分析产生式 (0) 的整体
```
E ——> TG
```
由于 E 相当于 TG，因此 FOLLOW(E) 应加入 FOLLOW(G)

FOLLOW(G) = { $ }
为了避免忘记，你自己在分析时做相应的标记，方便后续的分析

此外，由于 G 能推出空串，因此 E 也相当于 T，所以 FOLLOW(E) 应加入 FOLLOW(T)

FOLLOW(T) = { $, + }
分析产生式（1）
```
+TG | ''
空串在 FOLLOW集 中没有分析的必要，因此只需要分析：
+TG
```
由于 “+TG” 与 “TG” 在形式上基本相同（G都紧跟在T后面，并且G都在末尾），因此（1）的分析结果与（0）的分析结果相同，跳过

你可以自行验证
分析（2）的右部
```
FU 
```
与（0）的右部分析类似：FIRST(U) = { *, ‘’ } 应加入 FOLLOW(F)

FOLLOW(F) = { * }
分析（2）的整体
```
T ——> FU 
```
与（0）的整体分析类似：FOLLOW(T) 应加入 FOLLOW(U)，FOLLOW(T) 应加入 FOLLOW(F)

FOLLOW(U) = { $, + }
FOLLOW(F) = { $, +, * }
分析(3)
分析结果同（2），跳过
分析（4）的右部
```
(E) | id
'id' 只有终结符，因此不参与分析 
```
由于 E 后面为终结符 )，因此加入 FOLLOW(E)

**FOLLOW(E) = { $, ) }

这里你会发现个问题，我们第一个求解的是 FOLLOW(E)，而 FOLLOW(E) 又会被加入到其他的 FOLLOW集中（比如 FOLLOW(T) 等），那么这时候就需要更新对应的 FOLLOW集，这也是为什么要记录 “谁加入谁的原因”。但是此时还没分析完，还有一步：分析（4）的整体，因此在分析完一遍后再进行更新操作
分析（4）的整体
```
F ——> (E) | id
```
由于产生式右部的末尾都是终结符，因此没有分析的必要，跳过
更新操作：
- FOLLOW(E) 应加入 FOLLOW(G)
- FOLLOW(E) 应加入 FOLLOW(T)
- FOLLOW(T) 应加入 FOLLOW(U)
- FOLLOW(T) 应加入 FOLLOW(F)
因此最后的结果为

FOLLOW(E) = { $, ) }
FOLLOW(G) = { $, ) }
FOLLOW(T) = { $, ), + }
FOLLOW(U) = { $, ), + }
FOLLOW(F) = { $, ), +, * }

3. 预测分析表

为了更好地理解此部分，你应该知道如何使用预测分析表进行 LR分析

先看两个例子：

现有文法：
	S ——> aA 
	S ——> ''
那么 
	FIRST(S) = { a, '' }
	FOLLOW(S) = { $ }
1. 如果现在输入为 a...，
   需要使用 S 进行分析，
   那么应该使用 
   	   S ——> aA 
   进行语法分析
   
2. 如果现在输入结束了，
   相当于输入为 $，
   需要使用 S 进行分析，
   由于 '' 属于 FIRST(S)，
   并且 $ 属于 FOLLOW(S)，
   因此因使用
   	   S ——> ''
   进行语法分析
'可以这么理解'：
   因为使用 S 去进行分析，但是输入
   却是 FOLLOW(S)，也就是说，没有
   遇到 S 能推导出的
       首终结符 (FIRST(S)),
   遇到的是 S 后面'紧跟'的
	   首终结符(FOLLOW(S))
   那么 S 应该被'忽略'，也就是
       S 应该换为空串，同时
   由于 S 可以推空串，因此使用 
	   S ——> ''
   进行语法分析

3. 如果输入为 b，
   既不属于 FIRST(S)，
   也不属于 FOLLOW(S)，
   因此语法分析错误

现有文法：
	S ——> aA
那么 
	FIRST(S) = { a }
	FOLLOW(S) = { $ }
1. 如果现在输入字符为 a ...
   并且需要使用 S 进行分析，
   那么你就知道应该用 
	   S ——> aA
   去进行语法分析

2. 如果输入字符为 $
   需要用 S 进行分析，
   虽然 $ 属于 FOLLOW(S)，
   但是 S 不能推空串，
   因此语法分析错误
 
3. 如果输入为 c ...
   需要使用 S 进行分析，
   由于 FIRST(S) 中没有 c
   因此语法分析错误

看了上面两个例子，相信的你对如何构造预测分析表有了基本的理解。下面使用之前的例子以及求出的 FIRST集与 FOLLOW集来构造预测分析表。

基本思路：对文法的每一个产生式的右部 (非终结符)，针对不同的终结符，使用对应的 FIRST、FOLLOW集进行构造

文法

(0) E ——> TG
(1) G ——> +TG | ''
(2) T ——> FU 
(3) U ——> *FU | ''
(4) F ——> (E) | id

FIRST集

FIRST(E) = FIRST(T) = FIRST(F) = { (, id }
FIRST(G) = { +, ‘’ }
FIRST(U) = { *, ‘’ }
FOLLOW集

FOLLOW(E) = FOLLOW(G) = { $, ) }
FOLLOW(T) = FOLLOW(U) = { $, ), + }
FOLLOW(F) = { $, ), +, * }

规定：预测分析表横轴为终结符，纵轴为非终结符，中间的元素为指定的产生式（比如表[S][$] = S —> ‘’，表示当 S 遇到输入字符 $ 时应使用 S —> ‘’ 来进行语法分析）

	$
S	S —> ‘’

算法：对于每个产生式：A —> B

对于 FIRST(B) 的每个终结符 a，将 A —> B 加入表[A][a]
如果 ‘’ 属于 FIRST(B)，对于 FOLLOW(B) 中的每个终结符 b，将 A —> ‘’ 加入表[A][b]
其他都是空，表示语法分析错误

先找出所有的终结符

{ id, (, ), +, *, $ }
(0) E —> TG
首先有

FIRST(E) = { (, id }
FOLLOW(E) = { $, ) }

因为 E 与 TG 等效（E —> TG），那么 FIRST(E) = FIRST(TG) = { (, id }，因此对于 FIRST(TG) 中的每一个终结符 a，将 E ——> TG 加入表[E][a]（即表[ E ][ ( ]、表[ E ][ id ]）
故有

id ( ) + * $
E E —> TG E —> TG

由于不存在 E —> ‘’ ，所以不需要考虑 FOLLOW(E)
(1) G ——> +TG | ‘’
首先有

FIRST(G) = { +, ‘’ }
FOLLOW(G) = { $, ) }

同理由于 FIRST(+TG) = { + }，因此将 G —> +TG 加入表[ G ][ + ]；
现在 ‘’ 属于 FIRST(G)了，需要考虑 FOLLOW(G)：
**对于 FOLLOW(G) 中的每一个终结符 b，将 G —> ‘’ 加入表[ G ] [ b ]（也就是表[ G ][ $ ]、表[ G ][ ) ]）
即

id ( ) + * $
G G —> ‘’ G —> +TG G —> ‘’
其余的自行分析
最后结果为

id ( ) + * $
E E —> TG E —> TG
G G —> ‘’ G —> +TG G —> ‘’
T T—> FU T —> FU
U U —> ‘’ U —> ‘’ U —> *FU U —> ‘’
F F —> id F —> (E)