编译原理笔记

为什么需要follow集

follow集的存在还是为了计算first集,如果没有空字符ε的存在,那么follow集是没有必要的。

S → AB
A → a | ε
B → b

这种情况下,B的first集一定是b;

但如果B可以推导出ε

S → AB
A → a | ε
B → b | ε

那么B推导完可能直接消失了,这就需要看看在B后面可能跟着什么,而因为B为空,所以B后面跟着的东西实际上是B的前一个非终结符后面跟着的东西。

在上面这个例子中,因为B可能为空,所以有可能S→AB→A,所以要看看A后面可能跟着啥。这里A后面跟着结束符$,所以first(B)应该含有结束符$

LL(1)冲突处理

消除左递归

提取左公因子

X -> aY | aZ
Y -> b
Z -> c

变成

X -> aX'
X'-> Y | Z
Y -> b
Z -> c

评论