一、First 集（首符號集）

定義：
對于符號（非終結符或終結符）或符號串，First 集是該符號串能夠推導出的所有可能開頭的終結符的集合。若符號串可以推導出空串（ε），則 ε 也屬于 First 集。

注意:這里是終結符哦!(不包括一些特殊符號)

計算規則：

1. 終結符：First(a) = {a}。
2. 非終結符 A：
   • 若存在產生式 A → a…，則將 a 加入 First (A)。
   • 若存在產生式 A → B…，則將 First (B) 加入 First (A)。
   • 若 B 可以推導出 ε（即 First (B) 包含 ε），則遞歸處理后續符號。
   • 若所有產生式均以 ε 結尾（如 A → ε），則 First (A) 包含 ε。

舉幾個例子:

1.后面跟的不是非終結符
????????A->aB|ε
????????A->c
????????First(A)={a,ε,c}

2.后面跟非終結符（一）
????????A->Ba
????????B->b
????????First(A)={b}

3.后面跟非終結符（二）
????????A->Bc
????????B->b|ε
????????First(A)={b,c}

4.后面跟非終結符（三）
????????A->BC
????????B->b｜ε
????????C->c|ε
????????First(A)={b,c,ε}

二、Follow 集（后繼符號集）

定義：
對于非終結符 A，Follow (A) 是所有可能出現在 A 后面的終結符的集合，包括結束符 $（表示輸入結束）。

計算規則：

1. 起始符號 S：Follow (S) 初始包含 $。
2. 若存在產生式 B → αAβ，則將 First (β)（除去 ε）加入 Follow (A)。
3. 若存在產生式 B → αA（即 β 為空），則將 Follow (B) 加入 Follow (A)。
4. 若 A → αBβ 且 B 可以推導出 ε，則將 First (β)（除去 ε）和 Follow (A) 加入 Follow (B)。

給規則3舉例:

形如A->aB（a可以是終結符或者非終結符或者直接為空）或者A->aBβ是一個產生式且β=>ε
比如
A->B
A->CB
A->dBC
C->ε
將Follow(A)加入到Follow(B)中

三、綜合例題

例一:

給定文法?G(S)?如下：
S→IETSP∣O
I→if
E→b
O→other
L→else
T→then
P→LS∣ε

符號	First 集	Follow 集
S	{if, other}	{#, else}
I	{if}	{b}
E	{b}	{then}
O	{other}	{else, #}
L	{else}	{if, other}
P	{else, ε}	{else, #}

例二:

G(E):E->TE'
E'->+TE'|E
T->FT'
T'->*FT'|E
F->(E)|i

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

例三:

G[S]:S→aH
H→aMd
H→d
M→Ab
M→ε
A→aM
A→e

First	Follow
First(S)={a}	Follow(S)={#}
First(H)={a,d}	Follow(H)={#}
First(M)={a,e,ε}	Follow(M)={d,b}
First(A)={a,e}	Follow(A)={b}

例四:

G(E):E->TE'
E'->+E|ε
T->FT'
T'->Tlε
F->PF'
F'->*F'|ε
P->(E)|a|b|^

First	Follow
First(E)={(,a,b,^}	Follow(E)={#,)}
First(E')={+,ε}	Follow(E')={#,)}
First(T)={(,a,b,^}	Follow(T)={+,#,)}
First(T')={(,a,b,^,ε}	Follow(T')={+,#,)}
First(F)={(,a,b,^}	Follow(F)={(,a,b,^,+,#,)}
First(F')={*,ε}	Follow(F')={(,a,b,^,+,#,)}
First(P)={(,a,b,^}	Follow(P)={*,(,a,b,^,+,#,)}