求解first集與follow集

通過作業(yè)題目例子來體會。

題目

(0) E -> TE'
(1) E'-> +TE' | ε
(2) T -> FT'
(3) T'-> *FT' | ε
(4) F -> (E) | id

1. First 集

First（A）為A的開始符或者首符號集。

意義

如果兩個A產(chǎn)生式 A -> α | β，且FIRST(α)和FIRST(β)不相交；

下一個輸入符號是x，若x∈FIRST(α)，則選擇A->a，若x∈FIRST(β)，則選擇A->b。

算法

計算FIRST(X)的方法

• 如果 X 是終結(jié)符號，那么FIRST(X)={X}
• 如果 X 是非終結(jié)符號，且 X -> Y₁Y₂Y₃…Y_k 是產(chǎn)生式
  • 如果a在FIRST(Y_i)中，且 ε 在FIRST(Y₁)，F(xiàn)IRST(Y₂)，…，F(xiàn)IRST(Y_i-1)中，那么a也在FIRST(X)中；
  • 如果ε 在FIRST(Y₁)，F(xiàn)IRST(Y₂)，…，F(xiàn)IRST(Y_k)中，那么ε在FIRST(X)中；
• 如果X是非終結(jié)符號，且有X->ε，那么ε在FIRST(X)中

解題

如果算法看不懂，那我們來根據(jù)算法來模擬一下！

因為求FIRST集合如果有終結(jié)符號會比較好處理，所以我們逆順序進行實施；

• F -> (E) | id，可以推出 First(F)={ ( , id }
• T -> FT' ，可以推出 First(T)=First(F)={ ( , id }
• T'-> *FT' | ε ，可以推出 First(T')={ * , ε }
• E'-> +TE' | ε，可以推出 First(E')={ + , ε }
• E -> TE'，可以推出 First(E)=First(T)={ ( , id }

應(yīng)該一看明白了！

2. Follow集

Follow(A)指的是在某些句型中緊跟在A右邊的終結(jié)符號的集合

算法

• 將右端結(jié)束標(biāo)記 $ 放到 FOLLOW(S) 中
• 按照下面兩個規(guī)則不斷迭代，知道所有的FOLLOW集合都不再增長為止
  • 如果存在產(chǎn)生式A -> αBβ ，那么 FIRST(β)中所有非ε的符號都在FOLLOW(B)中；
  • 如果存在產(chǎn)生式A -> αB，或者A -> αBβ 且FIRST(β)包含ε，那么FOLLOW(A)中的所有符號都加入到FOLLOW(B)中

解題

一步一步來看

1. 首先將結(jié)束標(biāo)志$ 加入到FOLLOW(E)中FOLOOW(E)={ $ }；
2. 根據(jù)規(guī)則進行迭代

2.1 第一次迭代

• E -> TE'

第一種情況：FOLLOW(T)=FIRST(E')={ + }

第二種情況：FOLLOW(E')=FOLLOW(E)={ $ }

• E'-> +TE' | ε

第一種情況：FOLLOW(T)=FIRST(E')={ + }

第二種情況：FOLLOW(T)=FOLLOW(E')={ + , $ }

• T -> FT'

第一種情況：FOLLOW(F)=FIRST(T')={ * }

第二種情況：FOLLOW(T')=FOLLOW(T)={ + , $ }

• T'-> *FT' | ε

第一種情況：FOLLOW(F)=FIRST(T')={ * }

第二種情況：FOLLOW(F)=FOLLOW(T')={ + , * , $ }

• F -> (E) | id

第一種情況：FOLLOW(E)={ $ , ) }

2.2 第二次迭代

由于我們列出了等值關(guān)系，所以只需要再走一次第一次迭代的過程就可以了！

因為主要是FOLLOW可能在變，所以我們只需要找到FOLLOW的等值關(guān)系即可

我在上面標(biāo)出了第一次迭代的FOLLOW的最新版

下面我只要列出更新的即可

1. FOLLOW(E')=FOLLOW(E)={ $ , ) }
2. FOLLOW(T)=FOLLOW(E')={ $ , ) , + }
3. FOLLOW(T')=FOLLOW(T)={ $ , ) , + }
4. FOLLOW(F)=FOLLOW(T')={ $ , + , ) , * }
5. FOLLOW(E)={ $ , ) }

2.3 第三次迭代

第三次迭代就會發(fā)現(xiàn)FOLLOW集合不再發(fā)生改變，這時候規(guī)則結(jié)束，求出FOLLOW集合。

總結(jié)

Follow比較容易出錯，出錯的點主要在迭代過程的第二種情況的：A -> αBβ 且FIRST(β)包含ε

我們?nèi)菀缀雎赃@種情況。

只要把每一次迭代過程都寫在紙上，尤其注重Follow集合的等值！