编译原理（三）语法分析：6.预测分析器

---

【编译原理博客列表】》》》》》》

---

一、构造预测分析表

①首先构造FIRST集合与FOLLOW集合；
②然后根据两个集合构造预测分析表。

1.FIRST集合

（1）定义3.10

文法符号序列α的FIRST集合为: F I R S T ( α ) = { a ∣ α = ? > a . . . ， a ∈ T } FIRST(α)=\{a|α=*>a...，a∈T\} FIRST(α)={ a∣α=?>a...，a∈T}，若$\alpha =?>\epsilon$，则$\epsilon \in FIRST(\alpha )$。

解析：

• FIRST()内是文法符号序列α（包括终结符、非终结符）
• $a$表示终结符。
• 通俗地讲，文法符号序列α的FIRST集合就是从α开始可以导出的文法符号序列中的开头终结符。（开头意思是FIRST集合只取第一个终结符）

（2）算法3.5 文法符号X

• 输入：文法符号X
• 输出：X的FIRST集合
• 方法：

1. 若X是终结符，则就是自身，FIRST(X)={X}；
2. 若X是非终结符且有X→ε，则加入ε到FIRST(X)；
3. 若X是非终结符且有$X\to X_1{X}_2...X_k$，FIRST（X）= FIRST（$X_1{X}_2...X_k$），同FISRT（文法符号序列）的方法

（3）FISRT（文法符号序列）

设$X_0=\epsilon$，$X_{k+1}=\epsilon$。
$FIRST(X_1{X}_2...X_n)$是所有 F I R S T ( X i ) ( i = 1 , 2 , . . , k ) ? { ε } \textcolor{blue}{FIRST(X_i)(i=1,2,..,k)-\{ε\}} FIRST(Xi?)(i=1,2,..,k)?{ ε}的并集，其中$X_k$为第一个具有ε不属于$FIRST(X_j)$性质或k>n的文法符号，从$1?k?1$每个$X$都满足$\epsilon \in FIRST(X_i)$
若k>n，则将ε加入$FIRST(X_1{X}_2...X_n)$，即所有 F I R S T ( X i ) ? { ε } {FIRST(X_i)-\{ε\}} FIRST(Xi?)?{ ε}的并集再加上ε。

（4）例：

文法G为S→Ap|Bq，A→a|cA，B→dB|ε

FIRST(a) = {a}，FIRST(ε) = {ε}
FIRST(B) = {d,ε}，FIRST(A) = {a,c}，FIRST(S) = {a,c,d,q}
FIRST(cA) = {c}，FIRST(dB) = {d}
FIRST(Aq) = FIRST(A) = {a,c}，第一个就是$X_k$，
FIRST(Bq) = FIRST(B) - {ε} U FIRST(q) = {d,q}，第二个就是$X_k$

更多例子：FIRST(a)集合

2.FOLLOW集合

（1）定义3.11

非终结符A的FOLLOW集合如下：
F O L L O W ( A ) = { a ∣ S = ? > . . . A a . . . ， a ∈ T } FOLLOW(A) = \{a |S=*>...Aa...，a∈T\} FOLLOW(A)={ a∣S=?>...Aa...，a∈T}。

若A是某句型的最右符号，则$\#\in FOLLOW(A)$。

解析：
A的FOLLOW集合，就是从开始符号可以导出的所有含A的文法符号序列中紧跟A之后的终结符。

（2）算法3.6

• 输入：文法G
• 输出：G中所有非终结符的FOLLOW集合
• 方法：

1. 加入#到FOLLOW(S)，其中S是开始符号，#是输入结束标记
2. 若有产生式A→αB，则FOLLOW(A)的全体加入到FOLLOW(B)。
3. 若有产生式A→αBβ，
   ①先将 $FIRST(\beta )$ 除ε外的全体加入到FOLLOW(B)。
   ②然后判断如果 $\epsilon \in FIRST(\beta )$ ，则将$FOLLOW(A)$的全体加入到FOLLOW(B)。
   【先first，再follow，都是FOLLOW(A)】

解析：
这个α可以是终结符，也可以是非终结符（S→AB，那么FOLLOW(B)=FOLLOW(S)），我们只关心后面的β。
规则1只对开始符号起作用

（3）例子

例3.22 计算非终结符的FIRST与FOLLOW。
L →E;L|ε（1）
E →TE'（2）
E'→+TE'|-TE'|ε（3）
T →FT'（4）
T'→*FT'|/FT'|mod FT'|ε（5）
F →(E)|id|num（6）

自下而上计算FIRST（倒着，倒数第一）
自上而下计算FOLLOW（顺着FOLLOW）

解：

FIRST(F)  =	{
    ( id num}
FIRST(T') =	{
    * / mod ε}
FIRST(T)  = FIRST(F) =	{
    ( id num}
FIRST(E') =	{
    + - ε}
FIRST(E)  = FIRST(T) = FIRST(F) = {
    ( id num}
FIRST(L)  = {
    ε}∪FIRST(E) = {
    ε ( id num} FOLLOW(L)  = {
    #}							// 规则1
FOLL0W(E)  = {
    ) ;}							// （1）（6）规则3①
FOLLOW(E') = FOLL0W(E) = {
    ) ;}				// （2）（3）规则2
FOLLOW(T)  = {
    + - ) ;}						// （2）（3）规则3①{+ -}和②{) ;}
FOLLOW(T') = FOLLOW(T) = {
    +  -  ; )}		// （4）（5）规则2
FOLLOW(F)  = {
    * / mod + - ) ;} 				// （4）（5）规则3①{* / mod}和②{+ - ) ;}

3.算法3.7 构造预测分析表

• 输入：文法G
• 输出：分析表M
• 方法：

1. 对文法的每个产生式A→α，执行2和3；
   （分析表的行首是每个产生式的左部非终结符，列首是每个终结符和#）
   【注意列首中没有ε那一列，ε列要填产生式相关部分就是ε，会和FOLLOW集填入的ε冲突。所以ε就要看有没有填入FOLLOW列就知道】
2. 对$FIRST(\alpha )$的每个终结符a，加入$产生式右部相关部分$到M[A，a]；
3. 若$\epsilon \in FIRST(\alpha )$，则对$FOLLOW(A)$的每个终结符b(包括#)，加入$\epsilon$到M[A，b]；
4. M中其它没有定义的条目均是error。

例：
L →E;L|ε（1）
E →TE'（2）
E'→+TE'|-TE'|ε（3）
T →FT'（4）
T'→*FT'|/FT'|mod FT'|ε（5）
F →(E)|id|num（6）

FIRST(F/T/E)= {
    (  id  num}
FIRST(T')   = {
    *  /  mod ε}
FIRST(E')   = {
    +  - ε}
FIRST(L)    = {
    ε (  id  num}
FOLLOW(L)   = {
    #}
FOLL0W(E/E')= {
    ) ;}
FOLLOW(T/T')= {
    +  -  ; )}
FOLLOW(F) = {
    +  -  *  /  mod  ) ;}  

比如F行，FIRST(F) = {( id num}，比如列(，对应产生式是F→(E)，将产生式右部相关部分(E)填入列(
比如T'行，FIRST(T') = {* / mod ε}，填入对应的产生式右部相关部分后，有ε填FOLLOW，FOLLOW(T')= {+ - ; )}，将这几列中填入ε

二、预测

已知某文法 G 如下所示，其中，S、A、B 为非终结符且 S 为开始符号。
G：S→AB，A→aA |bA|ε，B→cB |ε
根据前面的计算结果说明在基于预测分析器的语法分析过程中，当要展开的非终结符为A时，如何根据输入的下一个终结符选择具体的候选项。

FIRST(B) = {
    c, ε}
FIRST(A) = {
    a, b, ε} 
FIRST(S) = {
    a, b, c, ε} FOLLOW(S) = {
    #} 
FOLLOW(A) = {
    c, #} 
FOLLOW(B) = {
    #}

若输入为 a 则按照 aA 展开；【产生式，很好理解，这是FIRST集中的a】
若输入为 b 则按照 bA；【产生式，很好理解，这是FIRST集中的b】
若输入为 c 或#则按照ε展开。【A产生式展开不出c或#开头的，那就展开成ε，要给剩下的非终结符展开去匹配。这就是FOLLOW集的意义。】