grammer.cpp

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

/********************************* grammer.CPP *************************************/
/*
    本程序要求用户在控制台里输入非终极符，终结符与产生式，然后对用户输入的文法进行分析，
得出first集 与follow 集，并打印出预测分析表用户决定是否继续进行句型分析，如继续则给
出符号分析栈的实现，从而判断刚输入的句子是否为符合该文法的句子。
例：
输入非终极符：SHMA#
输入终极符：adbe# 
输入产生式个数：7
输入产生式：
 S->aH
 H->aMd
 H->d
 M->Ab
 M->
 A->aM
 A->e
 分析例句：aaabd#  


*/
#include "grammer.h"
/*-------------------主函数--------------------*/
void main(void)
{
	char todo,ch;
 	Init();
	menu();
	InputVn();
	InputVt();
	InputP();
	getchar();
	FirstFollow();
	printf("该文法的first集为：");
	ShowCollect(first);
	printf("该文法的follow集为：");
	ShowCollect(follow);
	CreateAT();
	ShowAT();

	todo = 'y';
	while('y' == todo)
	{
		printf("\n是否继续进行句型分析？(y / n):");
		todo = getchar();
		while('y' != todo && 'n' != todo)
		{
			printf("\n(y / n)? ");
			todo = getchar();
		}
		if('y' == todo)
		{
			int i;
			InitStack();
			printf("请输入待测试符号串(以#结束) : ");
			ch = getchar();
			i = 0;
			while('#' != ch && i < MaxStLength)
			{
				if(' ' != ch && '\n' != ch)
				{
					st[i++] = ch;
				}
				ch = getchar();
			}
			if('#' == ch && i < MaxStLength)
			{
				st[i] = ch;
				Identify(st);
			}
			else 
				printf("输入出错！\n");
		}
	}

	getchar();
}
/*---------------各函数定义------------------*/

/*函数功能：对各表，栈进行初始化*/
void Init()
{
	int i,j;
	vnNum = 0;
	vtNum = 0;
	PNum = 0;
	for(i = 0; i <= MaxVnNum; i++)
	Vn[i] = '\0';  //初始化非终极符数组
	for(i = 0; i <= MaxVtNum; i++)
		Vt[i] = '\0';//初始化非终极符数组
	for(i = 0; i < MaxRuleNum; i++)
	{
		P[i].lCursor = NULL;
		P[i].rHead = NULL;
		P[i].rLength = 0;
	}
	PNum = 0;
	for(i = 0; i <= MaxPLength; i++)
		buffer[i] = '\0';
	for(i = 0; i < MaxVnNum; i++)
	{
		first[i] = NULL;
		follow[i] = NULL;
	}
	for(i = 0; i <= MaxVnNum; i++)
	{
		for(j = 0; j <= MaxVnNum + 1; j++)
			analyseTable[i][j] = -1;
	}
}

/*函数功能：返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
int IndexCh(char ch) 
{
	int n;
	n = 0; /*is Vn?*/
	while(ch != Vn[n] && '\0' != Vn[n])
	n++;
	if('\0' != Vn[n])
	return 100 + n;
	n = 0; /*is Vt?*/
	while(ch != Vt[n] && '\0' != Vt[n])
	n++;
	if('\0' != Vt[n])
	return n;
	return -1;
}

/*函数功能：输出Vn或Vt的内容*/
void ShowChArray(char* collect)
{
	int k = 0;
	while('\0' != collect[k])
	{
		printf(" %c ", collect[k++]);
	}
	printf("\n");
}

/*函数功能：输入非终结符*/
void InputVn()
{
	int inErr = 1;
	int n,k;
	char ch;
	while(inErr)
	{
		printf("\n请输入文法所用的非终结符，注意：");
		printf("一定要将开始符放在第一位，并以#号结束:\n"); 
		ch = ' ';
		n = 0;
		/*初始化数组*/
		while(n < MaxVnNum)
		{
			Vn[n++] = '\0';
		}
		n = 0;
		while(('#' != ch) && (n < MaxVnNum))
		{
			if(' ' != ch && '\n' != ch && -1 == IndexCh(ch))
			{
				Vn[n++] = ch;
				vnNum++;
			}
			ch = getchar();
		}
		Vn[n] = '#'; /*以“#”标志结束用于判断长度是否合法*/
		k = n; /*k用于记录n以便改Vn[n]='\0'*/
		if('#' != ch)
		{
			if( '#' != (ch = getchar()))
			{
				while('#' != (ch = getchar()))
					;//什么都不做
				printf("\n符号数目超过限制！\n");
				inErr = 1;
				continue;
			}
		}
  /*正确性确认，正确则，执行下下面，否则重新输入*/
		Vn[k] = '\0';
		ShowChArray(Vn);
		ch = ' ';
		while('y' != ch && 'n' != ch)
		{
			if('\n' != ch)
			{
				printf("输入正确确认?(y/n):");
			}
			scanf("%c", &ch);
		}
		if('n' == ch)
		{
			printf("录入错误重新输入！\n");
			inErr = 1;
		}
		else
		{
			inErr = 0;
		}
	}
}

/*函数功能：输入终结符*/
void InputVt()
{
	int inErr = 1;
	int n,k;
	char ch;
	while(inErr)
	{
		printf("\n请输入文法所用的终结符，注意：");
		printf("以#号结束:\n"); 
		ch = ' ';
		n = 0;
		 /*初始化数组*/
		while(n < MaxVtNum)
		{
			Vt[n++] = '\0';
		}
		n = 0;
		while(('#' != ch) && (n < MaxVtNum))
		{
			if(' ' != ch && '\n' != ch && -1 == IndexCh(ch))
			{
				Vt[n++] = ch;
				vtNum++;
			}
			ch = getchar();
		}
		Vt[n] = '#'; /*以“#”标志结束*/
		k = n; /*k用于记录n以便改Vt[n]='\0'*/
		if('#' != ch)
		{
			if( '#' != (ch = getchar()))
			{
				while('#' != (ch = getchar()))
					;
				printf("\n符号数目超过限制！\n");
				inErr = 1;
				continue;
			}
		}
  /*正确性确认，正确则，执行下下面，否则重新输入*/
		Vt[k] = '\0';
		ShowChArray(Vt);
		ch = ' ';
		while('y' != ch && 'n' != ch)
		{
			if('\n' != ch)
			{
				printf("输入正确确认?(y/n):");
			}
			scanf("%c", &ch);
		}
		if('n' == ch)
		{
			printf("录入错误重新输入！\n");
			inErr = 1;
		}
		else
		{
			inErr = 0;
		}
	}
}
/*函数功能：产生式输入*/
void InputP()
{
	char ch;
	int i = 0, n,num;
	printf("请输入文法产生式的个数：");
	scanf("%d", &num);
	PNum = num;
	getchar(); /*消除回车符*/
	printf("\n请输入文法的%d个产生式,并以回车分隔每个产生式：", num);
	printf("\n");
	while(i < num)
	{
		printf("第%d个：", i);
		/*初始化*/
		for(n =0; n < MaxPLength; n++)
			buffer[n] = '\0';
		/*输入产生式串*/
		ch = ' ';
		n = 0;
		while('\n' != (ch = getchar()) && n < MaxPLength)
		{
			if(' ' != ch)
			buffer[n++] = ch;    
		}
		buffer[n] = '\0';
		/*  printf("%s", buffer);*/
		if(CheckP(buffer))
		{
		/*填写入产生式结构体*/
			pRNode *pt, *qt;
			P[i].lCursor = IndexCh(buffer[0]);
			pt = (pRNode*)malloc(sizeof(pRNode));
			pt->rCursor = IndexCh(buffer[3]);
			pt->next = NULL;
			P[i].rHead = pt;
			n = 4;
			while('\0' != buffer[n])
			{
				qt = (pRNode*)malloc(sizeof(pRNode));
				qt->rCursor = IndexCh(buffer[n]);
				qt->next = NULL;
				pt->next = qt;
				pt = qt;
				n++;
			}
			P[i].rLength = n - 3;
			i++;
   /*调试时使用*/
		}
		else
			printf("输入符号含非法在成分，请重新输入！\n");
	}
}

/*函数功能：判断产生式正确性*/
bool CheckP(char * st)
{
	int n;
	if(100 > IndexCh(st[0]))
	return false;
	if('-' != st[1])
	return false;
	if('>' != st[2])
	return false;
	for(n = 3; '\0' != st[n]; n ++)
	{
		if(-1 == IndexCh(st[n]))
		return false;
	}
	return true;
}
/*====================first & follow======================*/

/*函数功能：计算first集,U->xx...*/
void First(int U)
{
	int i,j;
	for(i = 0; i < PNum; i++)
	{
		if(P[i].lCursor == U)
		{
			struct pRNode* pt;
			pt = P[i].rHead;
			j = 0;
			while(j < P[i].rLength)
			{
				if(100 > pt->rCursor)
				{
				/*注:此处因编程出错,使空产生式时
				rlength同样是1,故此处同样可处理空产生式*/
					AddFirst(U, pt->rCursor);
					break;
				}
				else
				{
					if(NULL == first[pt->rCursor - 100])
					{
						First(pt->rCursor);
					}     
					AddFirst(U, pt->rCursor);
					if(!HaveEmpty(pt->rCursor))
					{
						break;
					}
					else
					{
						pt = pt->next;
					}
				}
				j++;
			}
			if(j >= P[i].rLength) /*当产生式右部都能推出空时*/
				AddFirst(U, -1);
		}
	}
}

/*函数功能：加入first集*/
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;