都知道FOLLOW集是针对非终结符的，而LEMON中的项目FOLLOW集是针对项目的，指的是项目产生式左部非终结符FOLLOW集。
知道了项目FOLLOW集，它的求法也自然清楚了。这里把项目分成两类，它们的FOLLOW集来源是不一样的：
A. 号点不在最左的项目，FOLLOW集来源于生产式相同，点号在它前面的项目。
B. 点号在最左的项目，FOLLOW集就是生产式左部非终结符FOLLOW集。
非终结符FOLLOW集的计算方法：
1. 对于方法的开始符S，将用于表示输入结束的’$’符放入FOLLOW(S)中；
2. 若A->αBβ是一个产生式，则把FIRST(β)/{ ε}加至FOLLOW(B)中；
3. 若A->αB是一个产生式，或A->αBβ是一个产生式，且β->ε，则把FOLLOW(A)加至FOLLOW(B)中。
以状态项目的生成过程介绍项目FOLLOW集的计算。
开始状态中的所有项目都是B类型项目，于是计算开始符FOLLOW集，也就是方法1，对就代码为（FindStates）:
for(rp=sp->rule; rp; rp=rp->nextlhs)
{
struct config *newcfp;
rp->lhsStart = 1;
newcfp = Configlist_addbasis(rp,0);
SetAdd(newcfp->fws,0);//第一个符号为$
}
对当前状态中的项目进行closure运算，也就是要产生B类的项目，此时运用方法2与方法3计算，对应代码（Configlist_closure函数中）：
for(newrp=sp->rule; newrp; newrp=newrp->nextlhs)
{
newcfp = Configlist_add(newrp,0);//生成B型项目
for(i=dot+1; i<rp->nrhs; i++)
{
xsp = rp->rhs[i];
if( xsp->type==TERMINAL )
{
SetAdd(newcfp->fws,xsp->index);//运用方法2
break;
}
else if( xsp->type==MULTITERMINAL )
{
…
}
else
{
SetUnion(newcfp->fws,xsp->firstset);//运用方法2
if( xsp->lambda==LEMON_FALSE ) break;
}
}
if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp);//运用方法3
}
运用方法3时，并没有进行真正的FOLLOW拷贝，而只是做了一个记录，在后面一起 “结账”。这里也可以看出，config会将自己的FOLLOW集传给自己的fplp域。
求完闭包后，就开始传播了，传播产生A型项目。些时的FOLLOW集，直接由上级往下传就行了。代码位于函数buildshifts中：
for(bcfp=cfp; bcfp; bcfp=bcfp->next)
{
if( bcfp->status==COMPLETE ) continue; /* Already used */
if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can’t shift this one */
bsp = bcfp->rp->rhs[bcfp->dot]; /* Get symbol after dot */
if( !same_symbol(bsp,sp) ) continue; /* Must be same as for “cfp”*/
bcfp->status = COMPLETE; /* Mark this config as used */
new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
Plink_add(&new->bplp,bcfp); //A型项目FOLLOW集计算方法
}
这里也只是做了个标记，并没有真正传播FOLLOW集。从Plink_add(&new->bplp,bcfp);可以看出bplp暂存着可以将FOLLOW集传播给本项目的项目。
最后将标记转换成实际上的传播。
首先，把bplp转换为fplp（FindLinks）：
for(i=0; i<lemp->nstate; i++)
{
stp = lemp->sorted[i];
for(cfp=stp->cfp; cfp; cfp=cfp->next)//遍历每个状态的所有项目
{
for(plp=cfp->bplp; plp; plp=plp->next)
{
other = plp->cfp;
Plink_add(&other->fplp,cfp);
}
}
}
再将项目的FOLLOW集，传给它的fplp（FindFollowSets）：
void FindFollowSets(struct lemon *lemp)
{
…
do
{
progress = 0;
for(i=0; i<lemp->nstate; i++)//遍历所有状态
{
for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next)//遍历状态内所有项目
{
if( cfp->status==COMPLETE ) continue;
for(plp=cfp->fplp; plp; plp=plp->next)
{
change = SetUnion(plp->cfp->fws,cfp->fws);
if( change )
{
plp->cfp->status = INCOMPLETE;
progress = 1;
}
}
cfp->status = COMPLETE;
}
}
}
while( progress );
}
本文出自：https://blog.csdn.net/tms_li/article/details/6305498
