FIRST集合意義明确，求解直覺，不再贅述

FOLLOW集的不動點算法

先給出僞碼：

//init 
foreach(nonterminal N)
	FOLLOW(N) = {}
//開始符号S
FOLLOW(S) = { $ }

while(somw set is changing)
	foreach (production p: N->β1 ... βn)
	temp = FOLLOW(N)
	foreach (βi from βn downto β1)
		if(βi == a...)
			temp = {a}
		if(βi == M...)
			FOLLOW(M) ∪= temp
			if(M is not NULLABLE)
				temp = FIRST(M)
			else 
				temp ∪= FIRST(M)
           

為什麼這樣做呢？

因為如果有N->β1 …βn-2 βn-1βn

• 如果βn-1是一個終結符，那麼一定會有一個句型根據廣義推導，使得βn-1跟在βn-2後，是以應該有

  βn-2 ∈ FOLLOW(βn-1)

• 如果βn-1是一個非終結符，并且βn-1推不出ε，那麼有， FIRST(βn-1) ∈ FOLLOW(βn-2)
• 如果βn-1是一個非終結符，并且βn-1可以經過若幹推導産生ε，也即 ε∈FIRST(βn-1)， FIRST(βn-1) ∈ FOLLOW(βn-2)，并且βn-1可以推到産生ε，FIRST(βn) 也可以加入FOLLOW(βn-2)

注意上述推導都是逆序周遊每一個産生式。

還是不懂？沒關系，我們來看一個例子，直覺的感受一下這個算法。

設有文法G[S]

S − > A A − > B A ′ A ′ = > i B A ′ ∣ ϵ B − > C B ′ B ′ − > + C B ′ ∣ ϵ C − > ) A ∗ ∣ ( S->A\\A->BA'\\A'=>iBA'|ϵ\\B->CB'\\B'->+CB'|ϵ\\C->)A*|( S−>AA−>BA′A′=>iBA′∣ϵB−>CB′B′−>+CB′∣ϵC−>)A∗∣(

求每個非終結符FOLLOW集

FIRST(S)={（ , ）}

FIRST(A)={（ , ）}

FIRST(A’)={ i，ε }

FIRST(B)={（ , ）}

FIRST(B’)={ +，ε }

FIRST©={（ , ）}

開始求解FOLLOW集：

第一次周遊	第二次周遊	第三次周遊（沒有變化，算法終止）
FOLLOW(S)	{ $ }	{ $ }	{ $ }
FOLLOW(A)	{ $ , * }	{ $ , * }	{ $ , * }
FOLLOW(A’)	{ $ }	{ $ , * }	{ $ , * }
FOLLOW(B)	{ $ , i }	{ $ , i , * }	{ $ , i , * }
FOLLOW(B’)	{ $ , i }	{ $ , i , * }	{ $ , i , * }
FOLLOW©	{ $, *，+ , i }	{ $, *，+ , i }	{ $, *，+ , i }