如何找到FIRST和FOLLOW

Question

我想找到FIRST和遵循以下CFG：

S -> O | M 
M -> iEtMeM | a 
O -> iEtS | iEtMeO 
E -> b 

我做了左分解，所以我得到：

S -> O | M 
M -> iEtMeM | a 
O -> iEtO' 
O'-> S | MeO 
E -> b 

第一組：

FIRST(S) = FIRST(O)|FIRST(M) = {i,a} 
FIRST(M) = {i,a} 
FIRST(O) = {i} 
FIRST(O') = FIRST(S)|FIRST(M) = {i,a} 
FIRST(E) = {b} 

現在我不能找到S的FOLLOW集，因爲我不知道什麼是FOLLOW(O')：

FOLLOW(S) = {$, FOLLOW(O')} 

Answer 1

實際上只有FOLLOW(S) = {$}。

所以，我忽略了S是在右手邊 提及。更正如下：

首先我們通過添加生產S' ->S$，然後 FOLLOW(S') = {$}得到增強的語法。

然後我們有

• 從S' -> S$和O' -> S

  FOLLOW（S）= FIRST（$）+ FOLLOW（O'）

• 從M -> iEtMeM，O' -> MeO和S -> M

  FOLLOW（M）= FIRST（EM）+ FIRST（EO）+ FOLLOW（S）

• 從S -> O

  和O' -> MeO

  FOLLOW（O）= FOLLOW（S）+ FOLLOW '

• 從O -> iEtO'

  FOLLOW（O（O）'）= FOLLOW（O）

• 從M -> iEtMeM

  和O -> iEtO'

  FOLLOW（ E）= FIRST（TMEM）+ FIRST（到 '）

「問題」 是 FOLLOW(S)，FOLLOW(O)相互遞歸定義，和`FOLLOW（O'） - 這意味着每個這些 跟隨臺是別人的一個子集，因此它們 相等。

如果一個表示該組包含的限制，由上面的等式 強加的，作爲圖（與非末端符號爲節點）， 各組相互遞歸定義形成 強連接組件。用新的節點代替每個SCC將產生一個DAG，代表一組非非遞歸方程組，然後可以通過 「評估」拓撲順序。假設，我們用節點N替換節點，對應於符號S，O和O'。節點N。節點N。節點N。節點N。該公式變爲：

FOLLOW(N) = FIRST($) + FOLLOW(N) 
FOLLOW(M) = FIRST(eM) + FIRST(eO) + FOLLOW(N) 
FOLLOW(N) = FOLLOW(N) + FOLLOW(N) 
FOLLOW(N) = FOLLOW(N) 
FOLLOW(E) = FIRST(tMeM) + FIRST(tO') 

，並通過切斷多餘的部分：

FOLLOW(N) = FIRST($) = {$} 
FOLLOW(M) = FIRST(eM) + FIRST(eO) + FOLLOW(N) = {e, $} 
FOLLOW(E) = FIRST(tMeM) + FIRST(tO') = {t} 

，而且由於N代表要麼S，O，或O'我們得到：

FOLLOW(S`) = FOLLOW(S) = FOLLOW(O) = FOLLOW(O`) = {$} 
FOLLOW(M) = {e, $} 
FOLLOW(E) = {t}