step2_clae_first_follow_select.c

功能基本实现

		for(i=0;i<vnSetLen;i++)
		{
			for(j=0;j<matrixSize;j++)
			{
				printf("%d,",relationMatrix[i][j]);
				fprintf(testFile,"%d,",relationMatrix[i][j]);
			}
			printf("\n");
			fprintf(testFile,"\r\n");
		}

		for(i=0;i<vnSetLen;i++)
		{
			printf("group %c:",VNSet[i]);
			fprintf(testFile,"group %c:",VNSet[i]);
			for(j=0;j<groupFollow[i].len;j++)
			{
					printf("%c,",groupFollow[i].ele[j]);
					fprintf(testFile,"%c",groupFollow[i].ele[j]);
			}
			printf("\n");
			fprintf(testFile,"\r\n");
		}
		printf("======================\n");
		fprintf(testFile,"======================\r\n");
	}

	//free mem
	for(i=0;i<matrixSize;i++)
		free(relationMatrix[i]);
	free(relationMatrix);
	free(firstGroupFlagArr);
}

void    cal_select_set()
{
	int i,j,k,l,m;
	int vnIndex;
	char tmpChar;

	vnIndex=0;
	for(i=0;i<grammerNum;i++)
	{
		if(GrammerSet[i].mSetence[0]!=VNSet[vnIndex])
			vnIndex++;

		j=1;
		groupSelect[i].len=0;
		while(GrammerSet[i].mSetence[j]!='\0')
		{
			if(!(GrammerSet[i].mSetence[j]>=65&&GrammerSet[i].mSetence[j]<=90))
			{
				if(GrammerSet[i].mSetence[j]!='z')
				{
					groupSelect[i].ele[groupSelect[i].len]=GrammerSet[i].mSetence[j];
					groupSelect[i].len++;
					goto sel_cond2;
				}
				else //if vt is 'z'
				if(GrammerSet[i].mSetence[j+1]=='\0')	//ADDED
					goto sel_cond3;
				else
					goto sel_cond1;
			}
			else	//it is a vn
			{
					for(k=0;k<vnSetLen;k++)//Finding corresponding vn
						if(VNSet[k]==GrammerSet[i].mSetence[j])
							break;

					//ASSERTION
					if(k==vnSetLen)
					{
						printf("in cal_select ,error happen.\n");
						return;
					}
				
				if(VNProduceZ[k]==0)
				{	//add its first group's element
					for(l=0;l<groupFirst[k].len;l++)
					{
						tmpChar=groupFirst[k].ele[l];
						
						if(tmpChar=='z')
						{
							printf("in cal select ,error happen.\n");
							return;
						}

							for(m=0;m<groupSelect[i].len;m++)
							{
								if(groupSelect[i].ele[m]==tmpChar)
									break;
							}
							if(m==groupSelect[i].len)
							{
								groupSelect[i].ele[groupSelect[i].len]=tmpChar;
								groupSelect[i].len++;
							}	
					}
					goto sel_cond2;
				}
				else	//VN COULD PRODUCE z
				{
					for(l=0;l<groupFirst[k].len;l++)
					{
						tmpChar=groupFirst[k].ele[l];
						if(tmpChar!='z')
						{
							for(m=0;m<groupSelect[i].len;m++)
							{
								if(groupSelect[i].ele[m]==tmpChar)
									break;
							}

							if(m==groupSelect[i].len)//if tmpChar is new
							{
								groupSelect[i].ele[groupSelect[i].len]=tmpChar;
								groupSelect[i].len++;
							}
						}
					}

					if(GrammerSet[i].mSetence[j+1]=='\0')
					{
						
sel_cond3:				for(l=0;l<groupFollow[vnIndex].len;l++)
						{
							tmpChar=groupFollow[vnIndex].ele[l];
						
							for(m=0;m<groupSelect[i].len;m++)
							{
								if(groupSelect[i].ele[m]==tmpChar)
									break;
							}

							if(m==groupSelect[i].len)//if tmpChar is new
							{
								groupSelect[i].ele[groupSelect[i].len]=tmpChar;
								groupSelect[i].len++;
							}
						
						}
						goto sel_cond2;
					}
					else
					{
						goto sel_cond1;
					}
				}

			}
sel_cond1:	j++;
		}
sel_cond2:;
	}
	
	if(DEBUG)
	{
		printf("\noutput of group select:\n");
		fprintf(testFile,"\r\noutput of group select:\r\n");
		for(i=0;i<grammerNum;i++)
		{
			printf("%s ",GrammerSet[i].mSetence);
			fprintf(testFile,"%s ",GrammerSet[i].mSetence);

			for(l=0;l<groupSelect[i].len;l++)
			{
				printf("%c,",groupSelect[i].ele[l]);
				fprintf(testFile,"%c,",groupSelect[i].ele[l]);
			}
			printf("\n");
			fprintf(testFile,"\r\n");
		}
		printf("=====================\n");
		fprintf(testFile,"================\r\n");
	}
}


int checkLL1_consTable()
{

	int signedList[MAX_ELE_NUM];
	int i,j,k,l,m;
	int vnIndex,tmpIndex;
	
	//INIT
	for(i=0;i<vnSetLen;i++)
		for(j=0;j<vtSetLen+1;j++)
			analyseTable[i][j][0]='\0';
	
	vnIndex=0;
	tmpIndex=0;
	for(k=0;k<vtSetLen+1;k++)
		signedList[k]=0;
    i=0;



	while(i<grammerNum)
	{
		//FIND vnIndex whether collide.
		//IF collide,break and return 0
		if(GrammerSet[i].mSetence[0]==VNSet[vnIndex])
		{

cons_cond1:
				k=0;
			while(k<groupSelect[i].len)
			{
				l=0;
				while(l<vtSetLen&&groupSelect[i].ele[k]!=VTSet[l])
					l++;
				
				if(l==vtSetLen)
				{
					if(groupSelect[i].ele[k]!='#')
					{
						printf("in check LL1,error happen.\n");
						return 0;
					}
				}
			
				if(signedList[l]==1)
				{	//collide,exit
					printf("in check LL1,this grammer is not a LL1.\n");
					return 0;
				}
				else
				{
					signedList[l]=1;
					
					m=1;
					while(GrammerSet[i].mSetence[m]!='\0')
					{
						analyseTable[vnIndex][l][m-1]=GrammerSet[i].mSetence[m];
						m++;
					}
					analyseTable[vnIndex][l][m-1]='\0';
				}
				k++;
			}
		}
		else			//NEW VN OCCUR
		{
			vnIndex++;
		
			for(k=0;k<vtSetLen+1;k++)
				signedList[k]=0;

			goto cons_cond1;
		}

		i++;
	}

	if(DEBUG)
	{
		//output analyse table
		fprintf(stdout,"==output analyse table.==\n");
		fprintf(testFile,"==output analyse table.==\r\n");
		fprintf(stdout,"  ");
		fprintf(testFile,"  ");
		
		for(i=0;i<vtSetLen;i++)
		{
			fprintf(stdout,"%c        ",VTSet[i]);
			fprintf(testFile,"%c        ",VTSet[i]);
		}
			fprintf(stdout,"%c        \n",'#');
			fprintf(testFile,"%c        \r\n",'#');
			

		
		for(i=0;i<vnSetLen;i++)
		{	
			fprintf(stdout,"%c ",VNSet[i]);
			fprintf(testFile,"%c ",VNSet[i]);
			
			for(j=0;j<vtSetLen+1;j++)
			{
				fprintf(stdout,"%s",analyseTable[i][j]);
				fprintf(testFile,"%s",analyseTable[i][j]);
				
				l=strlen(analyseTable[i][j]);
				
				l=8-l;
				while(l>=0)	//CORRECTED if(l>=1)
				{
					fprintf(stdout,"%c",' ');
					fprintf(testFile,"%c",' ');
					l--;
				}		
			}
			fprintf(stdout,"\n");
			fprintf(testFile,"\r\n");
		}
	}

	return 1;
}

void    parsingSetence()
{
	int rowIndex,colIndex;
	int analyseStackIndex,setenceIndex;
	int i,l,k,count;
	int printSelect;
	char analyseStack[MAX_SETENCE_LEN];
	
	if(parseSetence==NULL)
	{
		printf("in parsing setence,setence is null.\n");
		return;
	}

	i=0;
	while(parseSetence[i]!='\0')
	{
		if(parseSetence[i]>=65&&parseSetence[i]<=90)
		{
			printf("parse setence has vn sign,can't parse.\n");
			return;
		}
		i++;
	}

	printf("\nparseSetence: %s\n",parseSetence);

	//INIT
	analyseStackIndex=0;
	setenceIndex=0;
	count=0;
	//
	analyseStack[0]='#';
	analyseStack[1]=startedSign;
	analyseStackIndex=1;


	fprintf(stdout,"==parse setence : %s ==\n",parseSetence);
	fprintf(testFile,"==parse setence : %s ==\r\n",parseSetence);

	fprintf(stdout,"s   analyseStack   unParseSetence op    \n");
	fprintf(testFile,"s   analyseStack   unParseSetence op    \r\n");

	while(!(analyseStackIndex==0&&parseSetence[setenceIndex]=='#'))
	{
			//OUTPUT THE RESULT
			fprintf(stdout,"%3d ",count);
			fprintf(testFile,"%3d ",count);
			
			l=0;
			while(l<=analyseStackIndex&&l<=14)
			{
				fprintf(stdout,"%c",analyseStack[l]);
				fprintf(testFile,"%c",analyseStack[l]);
				l++;
			}

			l++;
			if(l<15)
				l=15-l;

			while(l>=1)
			{
				fprintf(stdout,"%c",32);
				fprintf(testFile,"%c",32);
				l--;
			}

			k=setenceIndex;
			l=0;
			while(parseSetence[k]!='\0'&&l<=14)
			{
				fprintf(stdout,"%c",parseSetence[k]);
				fprintf(testFile,"%c",parseSetence[k]);
				
				k++;
				l++;
			}

			l++;
			if(l<15)
				l=15-l;
			while(l>=1)
			{
				fprintf(stdout,"%c",32);
				fprintf(testFile,"%c",32);
				l--;
			}
			count++;


		if(analyseStack[analyseStackIndex]==parseSetence[setenceIndex])
		{	
			//'match'
			//pop analyse stack
			analyseStackIndex--;
			//setence index forward.
			setenceIndex++;
			printSelect=1;
		}
		else	//find produce exp
		{
			if(!(analyseStack[analyseStackIndex]>=65&&analyseStack[analyseStackIndex]<=90))
			{
				printf("in parse setence,can't match.\n");
				return;
			}

			rowIndex=0;
			while(rowIndex<vnSetLen&&VNSet[rowIndex]!=analyseStack[analyseStackIndex])
				rowIndex++;

			if(rowIndex==vnSetLen)
			{
				printf("in parse setence, rowIndex==vnSetLen.\n");
				return;
			}
		
			colIndex=0;
			while(colIndex<vtSetLen&&VTSet[colIndex]!=parseSetence[setenceIndex])
				colIndex++;

			if(colIndex==vtSetLen)
			{
				if(parseSetence[setenceIndex]!='#')
				{
					printf("in parse setence, colIndex==vtSetLen.\n");
					return;
				}
			}

			if(analyseTable[rowIndex][colIndex][0]=='\0')
			{
				printf("in parse setence,can't find produce exp.");
				return;
			}
			else if(analyseTable[rowIndex][colIndex][0]=='z')
			{
				analyseStackIndex--;
				printSelect=2;
			}
			else
			{
				l=0;
				while(analyseTable[rowIndex][colIndex][l]!='\0')
					l++;
				l--;

				//push the produce exp reverse seq to stack.
				analyseStackIndex--;//an operation as pop
				while(l>=0)
				{
					analyseStackIndex++;
					analyseStack[analyseStackIndex]=analyseTable[rowIndex][colIndex][l];
					l--;
				}	

				printSelect=2;
			}
		}

			//ANALYSE RESULT
			if(printSelect==1)
			 {
				fprintf(stdout,"%c matched.\n",parseSetence[setenceIndex-1]);
				fprintf(testFile,"%c matched.\r\n",parseSetence[setenceIndex-1]);
			 }
			 else if(printSelect==2)
			 {
				fprintf(stdout,"%c->%s\n",VNSet[rowIndex],analyseTable[rowIndex][colIndex]);
				fprintf(testFile,"%c->%s\r\n",VNSet[rowIndex],analyseTable[rowIndex][colIndex]);
			 }
	}

	fprintf(stdout,"parse successfully.\n");
	fprintf(testFile,"parse successfully.\r\n");
}

void    topologySort(int** inMatrix,int* topSeqArr,int row,int col)
{
	int i,j;
	int* labeledRow;
	int labeledNum;
	unsigned noFirstNode;
	
	if(inMatrix==NULL||topSeqArr==NULL)
	{
		printf("in topologySort ,pass in matrix or topSeqArr is null\n");
		return;
	}
	
	labeledRow=(int*)malloc(sizeof(int)*row);
	if(labeledRow==NULL)
	{
		printf("in topologySort, mem apply failure.\n");
		return;
	}
	

	for(i=0;i<row;i++)
		labeledRow[i]=0;

	labeledNum=0;
	while(labeledNum!=row)
	{
		noFirstNode=1;
		
		for(j=0;j<col;j++)
		{
			if(!labeledRow[j])	//forget this line.
			{
				for(i=0;i<row;i++)
				{
					if(!labeledRow[i])
					{	//j is not a first node
						if(i!=j&&inMatrix[i][j]==1)
						{
							break;	
						}
					}
				}
			
				if(i==row)//j is a first node,note it ,del from the graph
				{
					topSeqArr[labeledNum]=j;
					labeledRow[j]=1;	//CORRECT->labeledRow[labeledNum]=1
					labeledNum++;
					noFirstNode=0;
				}
			}
		}

		if(noFirstNode)
		{
			printf("can't arrange a toplogy sort.\n");
			return;
		}
	}
	
	if(DEBUG)
	{
		printf("topsort result:\n");
		for(i=0;i<row;i++)
			printf("%d ",topSeqArr[i]);
		printf("\n");
	}
	
	free(labeledRow);

}