编译原理中LL(1)文法求FIRST集和FOLLOW集的方法

一、求FIRST集

1、右部首个字符是终结符则加入左部字符的FIRST集中，比如对形如U－>a…的产生式（其中a是终结符），把a收入到FIRST(U)中。

2、右部首个字符是非终结符，

若此非终结符能推出空字符，则把它的FIRST集传送到左部字符的FIRST集中，*

  若此非终结符后是终结符，则把此终结符加入到左部字符的FIRST集中，同时推导结束；

  若此非终结符后是非终结符，则回到(*)。

若此非终结符不能推出空字符，则把它的FIRST集传送到左部字符的FIRST集中，同时推导结束。

二、求FOLLOW集

1、FOLLOW集合是从开始符号S开始推导，把#加入FOLLOW(S)中。

2、左部是S的产生式，右部末尾是非终结符，则把#加入此非终结符的FOLLOW集中。

3、右部中若某非终结符的后面是终结符，则把此终结符加入到非终结符的FOLLOW集中。

4、右部中若某非终结符的后面是非终结符，

若后非终结符能推出空字符，则把后非终结符的FIRST集（去掉空字符）传送到前非终结符的FOLLOW集中，同时把左部非终结符的FOLLOW集传送到后非终结符的FOLLOW集中。

若后非终结符不能推出空字符，则把后非终结符的FIRST集传送到前非终结符的FOLLOW集中。