编译原理——First集与Follow集
First(A)为A的开始符或者首符号集。
如果两个A产生式 A -> α | β ,且FIRST(α)和FIRST(β)不相交;
下一个输入符号是x,若x∈FIRST(α),则选择 A->a ,若x∈FIRST(β),则选择 A->b 。
计算FIRST(X)的方法
如果算法看不懂,那我们来根据算法来模拟一下!
因为求FIRST集合如果有终结符号会比较好处理,所以我们逆顺序进行实施;
应该一看明白了!
Follow(A)指的是在某些句型中紧跟在A右边的 终结符号 的集合
一步一步来看
2.1 第一次迭代
第一种情况: FOLLOW(T)=FIRST(E')={ + }
第二种情况 : FOLLOW(E')=FOLLOW(E)={ $ }
第一种情况: FOLLOW(T)=FIRST(E')={ + }
第二种情况 : FOLLOW(T)=FOLLOW(E')={ + , $ }
第一种情况: FOLLOW(F)=FIRST(T')={ * }
第二种情况 : FOLLOW(T')=FOLLOW(T)={ + , $ }
第一种情况: FOLLOW(F)=FIRST(T')={ * }
第二种情况 : FOLLOW(F)=FOLLOW(T')={ + , * , $ }
第一种情况 : FOLLOW(E)={ $ , ) }
2.2 第二次迭代
由于我们列出了等值关系,所以只需要再走一次第一次迭代的过程就可以了!
因为主要是FOLLOW可能在变,所以我们只需要找到FOLLOW的等值关系即可
我在上面标出了第一次迭代的FOLLOW的最新版
下面我只要列出更新的即可
2.3 第三次迭代
第三次迭代就会发现 FOLLOW集合 不再发生改变,这时候规则结束,求出FOLLOW集合。
Follow比较容易出错,出错的点主要在迭代过程的第二种情况的: A -> αBβ 且FIRST(β)包含ε
我们容易忽略这种情况。
只要把每一次迭代过程都写在纸上,尤其注重 Follow集合 的等值!