void AddFirst(int U, int nCh) /*当数值小于100时nCh为Vt*/ /*当处理非终结符时,AddFirst不添加空项(-1)*/ {
struct collectNode *pt, *qt; int ch; /*用于处理Vn*/ pt = NULL; qt = NULL; if(nCh < 100) {
pt = first[U - 100]; while(NULL != pt) {
if(pt->nVt == nCh) break; else {
qt = pt;
pt = pt->next; } }
if(NULL == pt) {
pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh; pt->next = NULL;
if(NULL == first[U - 100]) {
first[U - 100] = pt; } else {
qt->next = pt; /*qt指向first集的最后一个元素*/ }
pt = pt->next; } } else {
pt = first[nCh - 100]; while(NULL != pt) {
ch = pt->nVt; if(-1 != ch) {
AddFirst(U, ch); }
pt = pt->next; } } }
/*判断first集中是否有空(-1)*/ bool HaveEmpty(int nVn) {
if(nVn < 100) /*为终结符时(含-1)，在follow集中用到*/ return false;
struct collectNode *pt; pt = first[nVn - 100]; while(NULL != pt) {
if(-1 == pt->nVt) return true; pt = pt->next; }
return false; }
/*计算follow集,例：U->xVy,U->xV.(注：初始符必含#——\void Follow(int V) {
int i;
struct pRNode *pt ;
if(100 == V) /*当为初始符时*/ AddFollow(V, -1, 0 ); for(i = 0; i < PNum; i++) {
pt = P[i].rHead;
while(NULL != pt && pt->rCursor != V) /*注此不能处理：U->xVyVz的情况*/ pt = pt->next; if(NULL != pt) {
pt = pt->next; /*V右侧的符号*/
if(NULL == pt) /*当V后为空时V->xV，将左符的follow集并入V的follow集中*/ {
if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {
Follow(P[i].lCursor); }
AddFollow(V, P[i].lCursor, 0); }
else /*不为空时V->xVy,(注意：y->)，调用AddFollow加入Vt或y的first集*/ {
while(NULL != pt && HaveEmpty(pt->rCursor)) {
AddFollow(V, pt->rCursor, 1); /*y的前缀中有空时，加如first集*/ pt = pt->next; }
if(NULL == pt) /*当后面的字符可以推出空时*/ {
if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {
Follow(P[i].lCursor); }
AddFollow(V, P[i].lCursor, 0); }
else /*发现不为空的字符时*/ {
AddFollow(V, pt->rCursor, 1); } } } } }
/*当数值小于100时nCh为Vt*/
/*#用-1表示,kind用于区分是并入符号的first集，还是follow集 kind = 0表加入follow集，kind = 1加入first集*/ void AddFollow(int V, int nCh, int kind) {
struct collectNode *pt, *qt; int ch; /*用于处理Vn*/ pt = NULL; qt = NULL;
if(nCh < 100) /*为终结符时*/ {
pt = follow[V - 100]; while(NULL != pt) {
if(pt->nVt == nCh) break; else {
qt = pt;
pt = pt->next; }
}
if(NULL == pt) {
pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh; pt->next = NULL;
if(NULL == follow[V - 100]) {
follow[V - 100] = pt; } else {
qt->next = pt; /*qt指向follow集的最后一个元素*/ }
pt = pt->next; } }
else /*为非终结符时，要区分是加first还是follow*/ {
if(0 == kind) {
pt = follow[nCh - 100]; while(NULL != pt) {
ch = pt->nVt;
AddFollow(V, ch, 0); pt = pt->next; } } else {
pt = first[nCh - 100]; while(NULL != pt) {
ch = pt->nVt; if(-1 != ch) {
AddFollow(V, ch, 1); }
pt = pt->next; } } } }
/*输出first或follow集*/
void ShowCollect(struct collectNode **collect) {
int i;
struct collectNode *pt; i = 0;
while(NULL != collect[i]) {
pt = collect[i];
printf(\ while(NULL != pt) {
if(-1 != pt->nVt) {
printf(\ } else
printf(\ pt = pt->next; } i++; }
printf(\}
/*计算first和follow*/ void FirstFollow() {
int i; i = 0;
while('\\0' != Vn[i]) {
if(NULL == first[i]) First(100 + i); i++; }
i = 0;
while('\\0' != Vn[i]) {
if(NULL == follow[i]) Follow(100 + i); i++; } }
/*=================构造预测分析表,例：U::xyz=============*/