求解first集与follow集
通过作业题目例子来体会。
题目
(0) E -> TE'
(1) E'-> +TE' | ε
(2) T -> FT'
(3) T'-> *FT' | ε
(4) F -> (E) | id
1. First 集
First（A）为A的开始符或者首符号集。
意义
如果两个A产生式 A -> α | β，且FIRST(α)和FIRST(β)不相交；
下一个输入符号是x，若x∈FIRST(α)，则选择A->a，若x∈FIRST(β)，则选择A->b。
算法
计算FIRST(X)的方法
- 如果 X 是终结符号，那么FIRST(X)={X}
- 如果 X 是非终结符号，且 X -> Y1Y2Y3…Yk 是产生式
- 如果a在FIRST(Yi)中，且 ε 在FIRST(Y1)，FIRST(Y2)，…，FIRST(Yi-1)中，那么a也在FIRST(X)中；
- 如果ε 在FIRST(Y1)，FIRST(Y2)，…，FIRST(Yk)中，那么ε在FIRST(X)中；
- 如果X是非终结符号，且有X->ε，那么ε在FIRST(X)中
解题
如果算法看不懂，那我们来根据算法来模拟一下！
因为求FIRST集合如果有终结符号会比较好处理，所以我们逆顺序进行实施；
-
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 }
应该一看明白了！
2. Follow集
Follow(A)指的是在某些句型中紧跟在A右边的终结符号的集合
算法
- 将右端结束标记
$放到 FOLLOW(S) 中 - 按照下面两个规则不断迭代，知道所有的FOLLOW集合都不再增长为止
- 如果存在产生式
A -> αBβ，那么 FIRST(β)中所有非ε的符号都在FOLLOW(B)中； - 如果存在产生式
A -> αB，或者A -> αBβ且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都加入到FOLLOW(B)中
- 如果存在产生式
解题
一步一步来看
- 首先将结束标志
$加入到FOLLOW(E)中FOLOOW(E)={ $ }； - 根据规则进行迭代
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 第二次迭代
由于我们列出了等值关系，所以只需要再走一次第一次迭代的过程就可以了！
因为主要是FOLLOW可能在变，所以我们只需要找到FOLLOW的等值关系即可
我在上面标出了第一次迭代的FOLLOW的最新版
下面我只要列出更新的即可
FOLLOW(E')=FOLLOW(E)={ $ , ) }FOLLOW(T)=FOLLOW(E')={ $ , ) , + }FOLLOW(T')=FOLLOW(T)={ $ , ) , + }FOLLOW(F)=FOLLOW(T')={ $ , + , ) , * }FOLLOW(E)={ $ , ) }
2.3 第三次迭代
第三次迭代就会发现FOLLOW集合不再发生改变，这时候规则结束，求出FOLLOW集合。
总结
Follow比较容易出错，出错的点主要在迭代过程的第二种情况的：A -> αBβ 且FIRST(β)包含ε
我们容易忽略这种情况。
只要把每一次迭代过程都写在纸上，尤其注重Follow集合的等值！
