如何找到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}