求解first集與follow集
通過作業(yè)題目例子來體會(huì)腕够。
題目
(0) E -> TE'
(1) E'-> +TE' | ε
(2) T -> FT'
(3) T'-> *FT' | ε
(4) F -> (E) | id
1. First 集
First（A）為A的開始符或者首符號(hào)集逊谋。
意義
如果兩個(gè)A產(chǎn)生式 A -> α | β，且FIRST(α)和FIRST(β)不相交；
下一個(gè)輸入符號(hào)是x，若x∈FIRST(α)，則選擇A->a绍刮，若x∈FIRST(β)，則選擇A->b挨摸。
算法
計(jì)算FIRST(X)的方法
- 如果 X 是終結(jié)符號(hào)孩革，那么FIRST(X)={X}
- 如果 X 是非終結(jié)符號(hào)，且 X -> Y1Y2Y3…Yk 是產(chǎn)生式
- 如果a在FIRST(Yi)中得运，且 ε 在FIRST(Y1)膝蜈，F(xiàn)IRST(Y2)，…熔掺，F(xiàn)IRST(Yi-1)中饱搏，那么a也在FIRST(X)中；
- 如果ε 在FIRST(Y1)置逻，F(xiàn)IRST(Y2)推沸，…，F(xiàn)IRST(Yk)中券坞，那么ε在FIRST(X)中鬓催；
- 如果X是非終結(jié)符號(hào)，且有X->ε恨锚，那么ε在FIRST(X)中
解題
如果算法看不懂宇驾，那我們來根據(jù)算法來模擬一下！
因?yàn)榍驠IRST集合如果有終結(jié)符號(hào)會(huì)比較好處理猴伶，所以我們逆順序進(jìn)行實(shí)施课舍；
-
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é)符號(hào)的集合
算法
- 將右端結(jié)束標(biāo)記
$放到 FOLLOW(S) 中 - 按照下面兩個(gè)規(guī)則不斷迭代，知道所有的FOLLOW集合都不再增長為止
- 如果存在產(chǎn)生式
A -> αBβ崔挖，那么 FIRST(β)中所有非ε的符號(hào)都在FOLLOW(B)中贸街； - 如果存在產(chǎn)生式
A -> αB，或者A -> αBβ且FIRST(β)包含ε狸相，那么FOLLOW(A)中的所有符號(hào)都加入到FOLLOW(B)中
- 如果存在產(chǎn)生式
解題
一步一步來看
- 首先將結(jié)束標(biāo)志
$加入到FOLLOW(E)中FOLOOW(E)={ $ }薛匪； - 根據(jù)規(guī)則進(jìn)行迭代
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)系，所以只需要再走一次第一次迭代的過程就可以了脓鹃！
因?yàn)橹饕荈OLLOW可能在變逸尖，所以我們只需要找到FOLLOW的等值關(guān)系即可
我在上面標(biāo)出了第一次迭代的FOLLOW的最新版
下面我只要列出更新的即可
FOLLOW(E')=FOLLOW(E)={ $ , ) }FOLLOW(T)=FOLLOW(E')={ $ , ) , + }FOLLOW(T')=FOLLOW(T)={ $ , ) , + }FOLLOW(F)=FOLLOW(T')={ $ , + , ) , * }FOLLOW(E)={ $ , ) }
2.3 第三次迭代
第三次迭代就會(huì)發(fā)現(xiàn)FOLLOW集合不再發(fā)生改變，這時(shí)候規(guī)則結(jié)束瘸右，求出FOLLOW集合娇跟。
總結(jié)
Follow比較容易出錯(cuò)，出錯(cuò)的點(diǎn)主要在迭代過程的第二種情況的：A -> αBβ 且FIRST(β)包含ε
我們?nèi)菀缀雎赃@種情況太颤。
只要把每一次迭代過程都寫在紙上苞俘，尤其注重Follow集合的等值！
