step2_clae_first_follow_select.c

功能基本实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEBUG 1

#define MAX_SETENCE_LEN  2000
#define MAX_GRAM_LEN     255
#define MAX_ELE_NUM      40
#define MAX_GRAM_ELE_NUM 300

//--IO FILES--
FILE* grammerFile,* setenceFile;
char* grammerFileName="grammer.txt";
char* setenceFileName="setence.txt";

FILE* testFile;
char* testFileName="outputData.txt";


//---GLOBAL VARIABLES---
//--GRAMMER STRUCT --
typedef struct
{
		char mSetence[MAX_GRAM_LEN];		
}grammerElement;

grammerElement GrammerSet[MAX_GRAM_ELE_NUM];
grammerElement TmpGrammerSet[MAX_GRAM_ELE_NUM];

typedef struct
{
		int  len;
		char ele[MAX_ELE_NUM];
}simpleGroup;

simpleGroup groupFirst[MAX_ELE_NUM];
simpleGroup groupFollow[MAX_ELE_NUM];
simpleGroup groupSelect[MAX_GRAM_LEN];

char analyseTable[MAX_ELE_NUM][MAX_ELE_NUM][MAX_GRAM_LEN];

char parseSetence[MAX_SETENCE_LEN];
int grammerNum;

char VTSet[MAX_ELE_NUM];
char VNSet[MAX_ELE_NUM];
int  VNProduceZ[MAX_ELE_NUM];

int vtSetLen;
int vnSetLen;

void	readInSetence();
void	readInGrammer();

//---1. ELEMINATE LEFT RECURSIVE--
void    outputGrammer();
void    outputTmpGrammer(int len);
int     hasLeftRecursive();
int     eleminateLeftRecursive();
void    bubbleSort();

//2.CAL INSIDUCE E,FIRST SET,FOLLOW SET,SELECT
void    cal_ProductE();
void    cal_first_set();
void    cal_follow_set();
void    cal_select_set();
int     checkLL1_consTable();

//3.CONSTRUCT ANALYSE DIAGRAM,YOU CAN SAVE THIS DIAGRAM FOR LATER USE

//4.PARSE THE SETENCE.
void    parsingSetence();

void    topologySort(int** inMatrix,int* topSeqArr,int row,int col);

//STARTED SIGN
char    startedSign;

void main()
{
		int i;
		//0.OPEN FILE ,READ IN SETENCE ,READING SETENCE AND REGISTER DATA.
		if((grammerFile=fopen(grammerFileName,"rb"))==NULL)
			{
				fprintf(stderr,"open file:grammerFile error.\n");
				return;	
			}
		if((setenceFile=fopen(setenceFileName,"rb"))==NULL)
			{
				fprintf(stderr,"open file:setenceFile error.\n");
				return;	
			}
		if((testFile=fopen(testFileName,"wb"))==NULL)
			{
				fprintf(stderr,"open file:testFile error.\n");
				return;	
			}
		


		readInSetence();
		readInGrammer();
		
		printf("input grammer.\n");
		outputGrammer();

		bubbleSort();
		printf("after bubble sort.\n");	
		outputGrammer();
			
		fclose(grammerFile);
		fclose(setenceFile);
	
		//1.ELEMINATE LEFT RECURSIVE
		if(hasLeftRecursive())
		{
			if(eleminateLeftRecursive()==-1)
					return;
			else
			{
				printf("\nafter eleminate left recursiv.\n");
				outputGrammer();
			}
		}
	
		//ADDED CODE
		bubbleSort();
		printf("after bubble sort.\n");	
		outputGrammer();
		for(i=0;i<grammerNum;i++)
			strcpy(TmpGrammerSet[i].mSetence,GrammerSet[i].mSetence);
		//END OF ADDED CODE

		//2.CAL INSIDUCE E,FIRST SET,FOLLOW SET,SELECT
		cal_ProductE();		//TmpGrammerSet
		cal_first_set();	//GrammerSet
		cal_follow_set();	//GrammerSet
		cal_select_set();	//GrammerSet
		//3.CONSTRUCT ANALYSE DIAGRAM,YOU CAN SAVE THIS DIAGRAM FOR LATER USE
		if(checkLL1_consTable())
		{	
			//4.PARSE THE SETENCE.
			parsingSetence();
		}
		
		
		fclose(testFile);
		getchar();
}

void 	readInSetence()
	{
		fscanf(setenceFile,"%s\r\n",&parseSetence);
	}
	
void readInGrammer()
{
	char tmpChar;
	char tmpStr[MAX_GRAM_LEN];
	int tmpIndex;
	int vtIndex,vnIndex;
	int i,j;
	
	tmpIndex=0;vtIndex=0;vnIndex=0;

	fscanf(grammerFile,"%c\r\n",&startedSign);

	while(!feof(grammerFile))
	{
		if(fscanf(grammerFile,"%c->%s\r\n",&tmpChar,&tmpStr)!=2)
			break;
			
		GrammerSet[tmpIndex].mSetence[0]=tmpChar;
		GrammerSet[tmpIndex].mSetence[1]='\0';
		strcat(GrammerSet[tmpIndex].mSetence,tmpStr);
		tmpIndex++;
		
		for(i=0;i<vnIndex;i++)
			if(tmpChar==VNSet[i])
				break;
		if(i==vnIndex)//new VT SIGN;
		{
				VNSet[vnIndex]=tmpChar;
				vnIndex++;
		}
		
		i=0;
		while(tmpStr[i]!='\0')
		{
			if(!(tmpStr[i]>=65&&tmpStr[i]<=90))//NOT UPCASE CHAR(NOT Vn)
				{
							for(j=0;j<vtIndex;j++)
								if(tmpStr[i]==VTSet[j])
									break;
							
							if(j==vtIndex)//new VT SIGN;
							{
								VTSet[vtIndex]=tmpStr[i];
								vtIndex++;
							}
				}
			i++;	
		}		
	}	
	
	VTSet[vtIndex]='\0';
	VNSet[vnIndex]='\0';
	vtSetLen=vtIndex;
	vnSetLen=vnIndex;
	
	grammerNum=tmpIndex;
}

void    outputGrammer()
{
	int i;
	for(i=0;i<grammerNum;i++)
		fprintf(stdout,"%s\n",GrammerSet[i].mSetence);
	
	fprintf(stdout,"%s %d\n",VTSet,vtSetLen);
	fprintf(stdout,"%s %d\n",VNSet,vnSetLen);

}

void    outputTmpGrammer(int len)
{
	int i;

	for(i=0;i<len;i++)
		fprintf(stdout,"%s\n",TmpGrammerSet[i].mSetence);
	
}

void    bubbleSort()
{
	int i,j;
	char tmpChar;
	char tmpStr[MAX_GRAM_LEN];
	int flag;

	//SORT VT
	flag=0;
	for(i=0;i<vtSetLen-1;i++)
	{
		for(j=0;j<vtSetLen-i-1;j++)
			if(VTSet[j]>VTSet[j+1])
			{
					tmpChar=VTSet[j];
					VTSet[j]=VTSet[j+1];
					VTSet[j+1]=tmpChar;
					flag=1;
			}
		if(flag==0)break;
	}

	//SORT VN
	flag=0;
	for(i=0;i<vnSetLen-1;i++)
	{
		for(j=0;j<vnSetLen-i-1;j++)//-->ADD ON startedSign's priority sort.
			if((VNSet[j]>VNSet[j+1]||(VNSet[j]!=startedSign&&VNSet[j+1]==startedSign))&&VNSet[j]!=startedSign)
			{
					tmpChar=VNSet[j];
					VNSet[j]=VNSet[j+1];
					VNSet[j+1]=tmpChar;	
					flag=1;
			}
		if(flag==0)break;
	}

	//SORT GRAMMER	
	flag=0;
	for(i=0;i<grammerNum-1;i++)
	{
		for(j=0;j<grammerNum-i-1;j++)
		if((GrammerSet[j].mSetence[0]>GrammerSet[j+1].mSetence[0]||(GrammerSet[j].mSetence[0]!=startedSign&&GrammerSet[j+1].mSetence[0]==startedSign))&&GrammerSet[j].mSetence[0]!=startedSign)
		{
			strcpy(tmpStr,GrammerSet[j].mSetence);
			strcpy(GrammerSet[j].mSetence,GrammerSet[j+1].mSetence);
			strcpy(GrammerSet[j+1].mSetence,tmpStr);
			flag=1;
		}
		if(flag==0)break;
	}
}

int hasLeftRecursive()
{
	int i,j;
	
	for(i=0;i<grammerNum;i++)
	{
		if(GrammerSet[i].mSetence[0]==GrammerSet[i].mSetence[1])
			break;

	}
	
	if(i<grammerNum)
	{
		printf("===grammer has left recursive.===\n");
		return 1;
	}
	else
	{
		printf("===grammer has no left recursive===\n");
		for(j=0;j<grammerNum;j++)
			strcpy(TmpGrammerSet[j].mSetence,GrammerSet[j].mSetence);
		return 0;
	}
}

int 	eleminateLeftRecursive()
{
	int i,j,k,l,m,n;
	int GroupL[MAX_ELE_NUM],GroupT[MAX_ELE_NUM];
	int GroupLLen,GroupTLen;

	int GrammerSetIndex,preGrammerSetIndex;
	char tmpNewSign;
	int  tmpIndex;
	int dealed[MAX_GRAM_LEN];
	int tmpVNLen;
	int preVNSetLen;

	char tweenGrammerSet[MAX_GRAM_ELE_NUM][MAX_GRAM_LEN];
	int  tweenIndex;//tweenArrLen;

	//INIT	
	GrammerSetIndex=0;
	preGrammerSetIndex=0;
	tweenIndex=0;

	for(i=0;i<MAX_GRAM_LEN;i++)
		dealed[i]=0;

	preVNSetLen=vnSetLen;
	for(i=0;i<preVNSetLen;i++)//->Correct: for(i=0;i<vnSetLen;i++)
	{
		//To cal the Ai-> group len;
		tmpVNLen=0;
	
		for(j=preGrammerSetIndex;j<grammerNum;j++)
		{
			if(GrammerSet[j].mSetence[0]!=VNSet[i])
				break;
			else
				tmpVNLen++;
		}

		//Replace Aj in all Ai->AjBeta
		tweenIndex=0;
		for(j=0;j<i;j++)
		{
			for(k=preGrammerSetIndex;k<grammerNum;k++)
			{
				//Exit control
				if(GrammerSet[k].mSetence[0]!=VNSet[i])
					break;
				
				// if Has Ai->AjBeta ASSERT GrammerSet[k].mSetence[0]==VNSet[i]
				if(GrammerSet[k].mSetence[1]==VNSet[j])
				{
					for(l=0;l<GrammerSetIndex;l++)
						if(TmpGrammerSet[l].mSetence[0]==VNSet[j])
							break;

					//ASSERTION
					if(l==GrammerSetIndex)
					{
						printf("error in eleminate l:replace part.\n");
						return -1;
					}
					
					while(l<GrammerSetIndex&&TmpGrammerSet[l].mSetence[0]==VNSet[j])
					{
						//VNSet[i]->TmpGrammerSet[l].mSetence[1..end]+GrammerSet[i].mSetence[2..end];
						tweenGrammerSet[tweenIndex][0]=VNSet[i];
					
						m=1;
						while(TmpGrammerSet[l].mSetence[m]!='\0')
						{
							tweenGrammerSet[tweenIndex][m]=TmpGrammerSet[l].mSetence[m];
							m++;
						}

						n=2;
						while(GrammerSet[k].mSetence[n]!='\0')
						{
							//->COREECT:GrammerSet[tmpIndex] -> GrammerSet[k]
							tweenGrammerSet[tweenIndex][m]=GrammerSet[k].mSetence[n];
							m++;
							n++;
						}
						tweenGrammerSet[tweenIndex][m]='\0';	

						tweenIndex++;
						l++;	//->error correct,forget.
					}
			
					dealed[k]=1;
				}
			}
		}
	
		//-->ADDED : TO ELIMINATE THE NEW LEFT SELF RECURSIVE
		//NO NEED ,USE A TWEEN STR DB IS OK

		//if has Ai->AiBeta Ai->c,Replace it with:
		//Ai->cAi'	Ai'->BetaAi'|z;
		
		//0 GET GroupL,GroupLLen,GroupT,GroupTLen;	
	
			 //starting pos
		for(k=preGrammerSetIndex;k<grammerNum;k++)//ASSUME GRAMMER SET HAS BEEN SORTED
		{
				                        //end pos
				if(GrammerSet[k].mSetence[0]!=VNSet[i])
					break;

				if(!dealed[k])
				{
					strcpy(tweenGrammerSet[tweenIndex],GrammerSet[k].mSetence);
					tweenIndex++;
				}
		}
		
		GroupLLen=0;
		GroupTLen=0;
		
		for(k=0;k<tweenIndex;k++)//ASSUME GRAMMER SET HAS BEEN SORTED
		{
			//-->CORRECT :tweenGrammer[tweenIndex][0]
				if(tweenGrammerSet[k][0]==tweenGrammerSet[k][1])	//GROUP	L
				{
							GroupL[GroupLLen]=k;
							GroupLLen++;
				}
				else //GROUP T
				{
							GroupT[GroupTLen]=k;
							GroupTLen++;
				}
		}
		
		if(GroupTLen==0)
		{
			printf("abort: illegal grammer.\n");
			return -1;
		}

		if(GroupLLen>0)
		{
			//1.FIND NEW VN SIGN 
			for(k=65;k<=90;k++)
			{
				for(l=0;l<vnSetLen;l++)
				{
					if(VNSet[l]==k)
						break;
				}

				if(l==vnSetLen)// k is a new ascii sign.
				{
					VNSet[vnSetLen]=k;
					tmpNewSign=k;
					vnSetLen++;
					break;		//-->CORRECT FORGET THIS
				}
			}
			
			if(k==91)
			{
				printf("in ele left recursive,not enough new sign\n");
				return -1;
			}

			//2.Replace  : A->Ab ,A->a ==>A->aD ,D->bD ,D->z
			//2.0 A->aD
		

			for(k=0;k<GroupTLen;k++)
			{	//VNSet[i]->GrammerSet[GroupT[k]].mSetemce[1 to n]+newSign;
				TmpGrammerSet[GrammerSetIndex].mSetence[0]=VNSet[i];
				tmpIndex=1;

				while(tweenGrammerSet[GroupT[k]][tmpIndex]!='\0')
				{
					TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex]=tweenGrammerSet[GroupT[k]][tmpIndex];
					tmpIndex++;
				}

				TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex]=tmpNewSign;
				TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex+1]='\0';
				
				GrammerSetIndex++;
			}
		

			//2.1 D->bD
			for(k=0;k<GroupLLen;k++)
			{
				//NewSign->GrammerSet[GroupL[k]].mSetence[2 to n]+NewSign
				TmpGrammerSet[GrammerSetIndex].mSetence[0]=tmpNewSign;
				
				tmpIndex=2;
				while(tweenGrammerSet[GroupL[k]][tmpIndex]!='\0')
				{
					TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex-1]=tweenGrammerSet[GroupL[k]][tmpIndex];
					tmpIndex++;
				}

				TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex-1]=tmpNewSign;
				TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex]='\0';
				
				GrammerSetIndex++;
			}

			//2.2 D->z
			TmpGrammerSet[GrammerSetIndex].mSetence[0]=tmpNewSign;
			TmpGrammerSet[GrammerSetIndex].mSetence[1]='z';
			TmpGrammerSet[GrammerSetIndex].mSetence[2]='\0';

			GrammerSetIndex++;
		}
		else 
		{		
			//ASSERT GroupLLen==0
		
			for(k=0;k<GroupTLen;k++)
			{
				strcpy(TmpGrammerSet[GrammerSetIndex].mSetence,tweenGrammerSet[k]);		
		      	GrammerSetIndex++;	
			}
		}
	

		if(DEBUG)
		{
			printf("\n====\n");
			outputTmpGrammer(GrammerSetIndex);
		}
		//-->CORRECT preGrammerSetIndex+=GroupLLen+GroupTLen;
		preGrammerSetIndex+=tmpVNLen;
	}

	//ADDED: IF Pre Grammer can't =>e
	//After left recursive ,it should be can
	for(i=0;i<vtSetLen;i++)
	{
		if(VTSet[i]=='z')
		{
			break;
		}
	}