grammer.cpp

本程序要求用户在控制台里输入非终极符

		}
	}
}

/*函数功能: 判断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.(注：初始符必含#——"-1")*/
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("\n%c:\t", Vn[i]);
		while(NULL != pt)
		{
			if(-1 != pt->nVt)
			{
				printf(" %c", Vt[pt->nVt]);
			}
			else
				printf(" #");
			pt = pt->next;
		}
		i++;
	}
	printf("\n");
}

/*计算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=============*/
void CreateAT()
{
	int i;
	struct pRNode *pt;
	struct collectNode *ct;
	for(i = 0; i < PNum; i++)
	{
		pt = P[i].rHead;
		while(NULL != pt && HaveEmpty(pt->rCursor)) 
		{
		/*处理非终结符，当为终结符时，定含空为假跳出*/
			ct = first[pt->rCursor - 100];
			while(NULL != ct)
			{
				if(-1 != ct->nVt)
				analyseTable[P[i].lCursor - 100][ct->nVt] = i;
				ct = ct->next;
			}
			pt = pt->next;
		}
		if(NULL == pt)
		{
			/*NULL == pt，说明xyz->,用到follow中的符号*/
			ct = follow[P[i].lCursor - 100];
			while(NULL != ct)
			{
				if(-1 != ct->nVt)
					analyseTable[P[i].lCursor - 100][ct->nVt] = i;
				else /*当含有#号时*/
					analyseTable[P[i].lCursor - 100][vtNum] = i;
				ct = ct->next;
			}
		}
		else
		{
			if(100 <= pt->rCursor) /*不含空的非终结符*/
			{
				ct = first[pt->rCursor - 100];
				while(NULL != ct)
				{
					analyseTable[P[i].lCursor - 100][ct->nVt] = i;
					ct = ct->next;
				}
			}
			else /*终结符或者空*/
			{
				if(-1 == pt->rCursor) /*-1为空产生式时*/
				{
					ct = follow[P[i].lCursor - 100];
					while(NULL != ct)
					{
						if(-1 != ct->nVt)
							analyseTable[P[i].lCursor - 100][ct->nVt] = i;
						else /*当含有#号时*/
							analyseTable[P[i].lCursor - 100][vtNum] = i;
						ct = ct->next;
					}
				}
				else /*为终结符*/
				{
					analyseTable[P[i].lCursor - 100][pt->rCursor] = i;
				}
			}
		}
	}
}

/*函数功能：输出分析表*/
void ShowAT()
{
	int i,j;

	printf("构造预测分析表如下：\n");
	printf("\t|\t");
	for(i = 0; i < vtNum; i++)
	{
		printf("%c\t", Vt[i]);
	}
	printf("#\t\n");
	printf("- - -\t|- - -\t");
	for(i = 0; i <= vtNum; i++)
		 printf("- - -\t");
	printf("\n");
	for(i = 0; i < vnNum; i++)
	{
		printf("%c\t|\t", Vn[i]);
		for(j = 0; j <= vtNum; j++)
		{
			if(-1 != analyseTable[i][j])
				printf("R(%d)\t", analyseTable[i][j]);
			else
				printf("error\t");
		}
		printf("\n");
	}
}

/*=================主控程序=====================*/
void Identify(char *st)
{
	int current,step,r; /*r表使用的产生式的序号*/
	printf("\n%s的分析过程：\n", st);
	printf("步骤\t分析符号栈\t当前指示字符\t使用产生式序号\n");
	step = 0;
	current = 0; /*符号串指示器*/
	printf("%d\t",step);
	ShowStack();
	printf("\t\t%c\t\t- -\n", st[current]);
	while('#' != st[current])
	{
		if(100 > analyseStack[topAnalyse]) /*当为终结符时*/
		{
			if(analyseStack[topAnalyse] == IndexCh(st[current]))
			{
				/*匹配出栈，指示器后移*/
				Pop();
				current++;
				step++;
				printf("%d\t", step);
				ShowStack();
				printf("\t\t%c\t\t出栈、后移\n", st[current]);
			}
			else
			{
				printf("%c-%c不匹配！", analyseStack[topAnalyse], st[current]);
				printf("此串不是此文法的句子！\n");
				return;
			}
		}
		else /*当为非终结符时*/
		{
			r = analyseTable[analyseStack[topAnalyse] - 100][IndexCh(st[current])];
			if(-1 != r)
			{
				Push(r); /*产生式右部代替左部，指示器不移动*/
				step++;
				printf("%d\t", step);
				ShowStack();
				printf("\t\t%c\t\t%d\n", st[current], r);
			}
			else
			{
				printf("无可用产生式，此串不是此文法的句子！\n");
				return;
			}
		}
	}
	if('#' == st[current])
	{
		if(0 == topAnalyse && '#' == st[current])
		{
			step++;
			printf("%d\t", step);
			ShowStack();
			printf("\t\t%c\t\t分析成功！\n", st[current]);
			printf("%s是给定文法的句子！\n", st);
		}
		else
		{
			while(topAnalyse > 0)
			{
				if(100 > analyseStack[topAnalyse]) /*当为终结符时*/
				{
					printf("无可用产生式，此串不是此文法的句子！\n");
					return;
				}
				else
				{
					r = analyseTable[analyseStack[topAnalyse] - 100][vtNum];
					if(-1 != r)
					{
						Push(r); /*产生式右部代替左部，指示器不移动*/
						step++;
						printf("%d\t", step);
						ShowStack();
						if(0 == topAnalyse && '#' == st[current])
						{
							printf("\t\t%c\t\t分析成功！\n", st[current]);
							printf("%s是给定文法的句子！\n", st);
						}
						else      
							printf("\t\t%c\t\t%d\n", st[current], r);
					}
					else
					{
						printf("无可用产生式，此串不是此文法的句子！\n");
						return;
					}
				}
			}
		}
	}
}

/*初始化栈及符号串*/
void InitStack()
{
	int i;
	/*分析栈的初始化*/
	for(i = 0; i < MaxStLength; i++)
	st[i] = '\0';
	analyseStack[0] = -1; /*#(-1)入栈*/
	analyseStack[1] = 100; /*初始符入栈*/
	topAnalyse = 1;
}

/*显示符号栈中内容*/
void ShowStack()
{
	int i;
	for(i = 0; i <= topAnalyse; i++)
	{
		if(100 <= analyseStack[i])
		printf("%c", Vn[analyseStack[i] - 100]);
		else
		{
			if(-1 != analyseStack[i])
				printf("%c", Vt[analyseStack[i]]);
			else 
				printf("#");
		}
	}
}

/*栈顶出栈*/
void Pop()
{
	topAnalyse--;
}

/*使用产生式入栈操作*/
void Push(int r)
{
	int i;
	struct pRNode *pt;
	Pop();
	pt = P[r].rHead;
	if(-1 == pt->rCursor) /*为空产生式时*/
	return;
	topAnalyse += P[r].rLength;
	for(i = 0; i < P[r].rLength; i++)
	{
		/*不为空产生式时*/
		analyseStack[topAnalyse - i] = pt->rCursor;/*逆序入栈*/
		pt = pt->next;
	}/*循环未完时pt为空，则说明rLength记录等出错*/
}
void menu()
{
	printf("------------------------语法分析器-------------------\n");
    printf("							   ---姓名: 刘志兵\n");
	printf("                               ---学号 :  2004551614\n");
}