step2_clae_first_follow_select.c

功能基本实现

	if(i==vtSetLen)//if 'z' not appear in pre grammer,then add it
	{
		VTSet[vtSetLen]='z';
		vtSetLen++;
	}

	//COPY TmpGrammerSet to GrammerSet
	grammerNum=GrammerSetIndex;
	
	for(i=0;i<grammerNum;i++)
		strcpy(GrammerSet[i].mSetence,TmpGrammerSet[i].mSetence);
	
	return 0;
}


void    cal_ProductE()
{
	int i,j,k,l,m,vnIndex;
	int noE,labeledNum,flag;

	for(i=0;i<vnSetLen;i++)
		VNProduceZ[i]=-1;	//stands for unlabeled.

	//ASSERT: TmpTmpGrammerSet equals to TmpGrammerSet
	labeledNum=0;

//	outputTmpGrammer(grammerNum);

	while(labeledNum!=vnSetLen)
	{
		noE=1;
		
		vnIndex=0;
	
		for(i=0;i<grammerNum;i++)
		{		
			//synchronization TmpGrammerSet's VN index with VNSet's VN index.
			if(TmpGrammerSet[i].mSetence[0]!=VNSet[vnIndex])
				vnIndex++;
		
			if(VNProduceZ[vnIndex]==-1)
			{
				flag=1;
				j=1;
			
				//Check Whether A[vnIndex]->e
				while(TmpGrammerSet[i].mSetence[j]!='\0')
				{
					if(TmpGrammerSet[i].mSetence[j]!='z')
					{
						flag=0;
						break;
					}	
					j++;
				}
			
				if(flag)//A[vnIndex]->e can be done
				{
					VNProduceZ[vnIndex]=1;
					labeledNum++;
					noE=0;
					
					l=0;
					for(k=0;k<grammerNum;k++)
					{
							//synchronization TmpGrammerSet's VN index with VNSet's VN index.
							if(TmpGrammerSet[k].mSetence[0]!=VNSet[l])
								l++;

							//CORRECT->VNProduceZ[vnIndex]!=-1
							if(VNProduceZ[l]==-1)
							{
								m=1;
								while(TmpGrammerSet[k].mSetence[m]!='\0')
								{
									if(TmpGrammerSet[k].mSetence[m]==VNSet[vnIndex])
										TmpGrammerSet[k].mSetence[m]='z';
									m++;
								}
							}
					}
				}
			}
		}
		
		if(noE)
		{
			for(j=0;j<vnSetLen;j++)
				if(VNProduceZ[j]==-1)
				{
					VNProduceZ[j]=0;
					labeledNum++;
				}

			if(DEBUG)
				printf("labeledNum==vnSetLen:%d\n",labeledNum==vnSetLen);
		}
	}

	if(DEBUG)
	{
		printf("in cal prodce e:\n");
		for(i=0;i<vnSetLen;i++)
			printf("%c %d\n",VNSet[i],VNProduceZ[i]);
	}
}

void    cal_first_set()
{
	int i,j,k;
	int** relationMatrix;
	int matrixSize;
	int vnIndex;
	int rowIndex,colIndex;

	matrixSize=vnSetLen+vtSetLen;
	relationMatrix=(int**)malloc(sizeof(int*)*matrixSize);
	for(i=0;i<matrixSize;i++)
		relationMatrix[i]=(int*)malloc(sizeof(int)*matrixSize);
	if(relationMatrix==NULL)
	{
		printf("in cal_first_set,mem apply failure.\n");
		return;
	}

	for(i=0;i<matrixSize;i++)
		for(j=0;j<matrixSize;j++)
			relationMatrix[i][j]=0;

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

		j=1;
		while(GrammerSet[i].mSetence[j]!='\0')
		{
			/*Correct.
			if(GrammerSet[i].mSetence[j]=='z')
				goto fir_cond2;
			*/
			if(GrammerSet[i].mSetence[j]>=65&&GrammerSet[i].mSetence[j]<=90)//A->Beta , Beta is a unterminated char
			{
				
				for(k=0;k<vnSetLen;k++)//Finding corresponding vn
					if(VNSet[k]==GrammerSet[i].mSetence[j])
						break;

				//ASSERTION
				if(k==vnSetLen)
				{
					printf("in cal_first ,error happen 0.\n");
					return;
				}
				
				colIndex=k;
				rowIndex=vnIndex;
				relationMatrix[rowIndex][colIndex]=1;

				//Correct:if(VNProduceZ[vnIndex])
				if(VNProduceZ[k])//A->Beta ,Beta->z
					goto fir_cond1;
				else					//A->Beta,Beta->!z
					goto fir_cond2;

			}
			else	//A->Beta,Beta is a terminate char and not z
			{
				for(k=0;k<vtSetLen;k++)
					if(VTSet[k]==GrammerSet[i].mSetence[j])
						break;

				//ASSERTION
				if(k==vtSetLen)
				{
					
					printf("in cal_first ,error happen 1.\n");
					return;
				}
				
				if(VTSet[k]=='z')
				{
					goto fir_cond1;
				}
				else
				{
					colIndex=vnSetLen+k;
					rowIndex=vnIndex;
					relationMatrix[rowIndex][colIndex]=1;
					goto fir_cond2;
				}
			}

fir_cond1:
			j++;
		}
fir_cond2:;
	}

	//USE FLOYD ALGO TO CAL CONNECTIVE
	for(k=0;k<matrixSize;k++)
		for(i=0;i<matrixSize;i++)
			for(j=0;j<matrixSize;j++)
			{
				//->Corrected if(relationMatrix[i][j]!=0) !!!
				if(relationMatrix[i][j]==0)
				{
					if(relationMatrix[i][k]==1&&relationMatrix[k][j]==1)
						relationMatrix[i][j]=1;
				}
			}

	//NOTE THE FIRST SET.

	for(i=0;i<vnSetLen;i++)
	{
		groupFirst[i].len=0;
		for(j=vnSetLen;j<matrixSize;j++)
		{
			//Corrected->VTSet[j]
									//->AddED:relationMatrix[i][j]==1
			if(VTSet[j-vnSetLen]!='z'&&relationMatrix[i][j]==1)
			{										//Corrected:relationMatrix[i][j]
				groupFirst[i].ele[groupFirst[i].len]=VTSet[j-vnSetLen];
				groupFirst[i].len++;
			}
		}

		if(VNProduceZ[i]==1)
		{
				groupFirst[i].ele[groupFirst[i].len]='z';
				groupFirst[i].len++;
		}
	}



	if(DEBUG)
	{
		printf("\n==fisrt group condition==:\n");
		fprintf(testFile,"\r\n==fisrt group condition==:\r\n");

		for(i=0;i<vnSetLen;i++)
		{
			printf("group %c:",VNSet[i]);
			fprintf(testFile,"group %c:",VNSet[i]);

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

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

void    cal_follow_set()
{
	int i,j,k,l;
	int** relationMatrix;
	int matrixSize;
	int vnIndex;
	int rowIndex,colIndex;
	char curVn,tmpChar,tmpChar2;
	int* firstGroupFlagArr;
	int  gFirstIndex;
	matrixSize=2*vnSetLen+vtSetLen+1;

	relationMatrix=(int**)malloc(sizeof(int*)*matrixSize);
	for(i=0;i<matrixSize;i++)
		relationMatrix[i]=(int*)malloc(sizeof(int)*matrixSize);
	
	firstGroupFlagArr=(int*)malloc(sizeof(int)*vnSetLen);

	if(relationMatrix==NULL||firstGroupFlagArr==NULL)
	{
		printf("in cal_follow_set,mem apply failure.\n");
		return;
	}

	for(i=0;i<matrixSize;i++)
		for(j=0;j<matrixSize;j++)
			relationMatrix[i][j]=0;
	
	for(i=0;i<vnSetLen;i++)
		firstGroupFlagArr[i]=0;

	//1 point S or first sign to '#'
	//ASSERT
	//DELETE AS SOME GRAMMER NOT USE S AS A INIT SIGN
	
	if(VNSet[0]!=startedSign)
		{
			printf("StartedSign element not in the front.\n");
			return;	
		}

	relationMatrix[0][2*vnSetLen]=1;
	
		
	//2.SET UP THE GRAPH
	vnIndex=0;
	for(i=0;i<grammerNum;i++)
	{
		if(GrammerSet[i].mSetence[0]!=VNSet[vnIndex])
				vnIndex++;

		j=1;
		while(GrammerSet[i].mSetence[j]!='\0')
		{
				//get a new sign
COND1:			tmpChar=GrammerSet[i].mSetence[j];
				j++;
								
				if(tmpChar=='\0')
				{
					goto COND3;
				}
				else if(!(tmpChar>=65&&tmpChar<=90))//tmpchar is vt
				{
					goto COND1;
				}
				else
				{
					curVn=tmpChar;
					goto COND2;
				}

COND2:			//tmpChar is a vn
				tmpChar=GrammerSet[i].mSetence[j];
				j++;
				
				if(tmpChar=='z')
				{
					goto COND2;
				}
				else if(tmpChar=='\0')
				{
					goto COND4;
				}
				else if(!(tmpChar>=65&&tmpChar<=90))//tmpchar is vt && vt is not 'z'
				{
					//tmpChar is in follow(curVn)
					for(k=0;k<vnSetLen;k++)//Finding corresponding vn
						if(VNSet[k]==curVn)
							break;

					//ASSERTION
					if(k==vnSetLen)
					{
						printf("in cal_follow ,error happen.\n");
						return;
					}
					rowIndex=k;

					for(k=0;k<vtSetLen;k++)//Finding corresponding vt
						if(VTSet[k]==tmpChar)
							break;

					//ASSERTION
					if(k==vtSetLen)
					{
						printf("in cal_follow ,error happen.\n");
						return;
					}
					colIndex=2*vnSetLen+1+k;

					relationMatrix[rowIndex][colIndex]=1;
					goto COND1;

				}
				else	//tmpChar is Vn
				{
					for(k=0;k<vnSetLen;k++)//Finding corresponding vn
						if(VNSet[k]==curVn)
							break;

					//ASSERTION
					if(k==vnSetLen)
					{
						printf("in cal_follow ,error happen.\n");
						return;
					}
					rowIndex=k;
					
					for(k=0;k<vnSetLen;k++)//Finding corresponding vn
						if(VNSet[k]==tmpChar)
							break;

					//ASSERTION
					if(k==vnSetLen)
					{
						printf("in cal_follow ,error happen.\n");
						return;
					}
					
					colIndex=vnSetLen+k;
					gFirstIndex=k;

							//follow(rowIndex)->first(colIndex)
					relationMatrix[rowIndex][colIndex]=1;
			//		firstGroupFlagArr[k]=1;		//ADDED HERE //DELETED
					//ADDED FIRST RELATION.
					k=0;
					for(k=0;k<groupFirst[gFirstIndex].len;k++)
					{
						for(l=0;l<vtSetLen;l++)//Finding corresponding vt
							if(VTSet[l]==groupFirst[gFirstIndex].ele[k])
								break;

							//ASSERTION
							if(l==vtSetLen)
							{
								printf("in cal_follow ,error happen.\n");
								return;
							}

						relationMatrix[rowIndex][2*vnSetLen+1+l]=1;
					}
					//END OF ADDED CODE.
										
					tmpChar2=tmpChar;

					//ADDED if A->BC if C->z THEN FOLLOW(B)->FOLLOW(A)
					l=j;
					while(GrammerSet[i].mSetence[l]!='\0')
					{
						if(!(GrammerSet[i].mSetence[l]>=65&&GrammerSet[i].mSetence[l]<=90))//if it is a vt
						{
							if(GrammerSet[i].mSetence[l]!='z')
							{
								break;
							}
						}
						else	//it is a vn
						{
								for(k=0;k<vnSetLen;k++)//Finding corresponding vn
									if(VNSet[k]==GrammerSet[i].mSetence[l])
										break;

								//ASSERTION
								if(k==vnSetLen)
								{
									printf("in cal_follow ,error happen.\n");
									return;
								}	

								if(VNProduceZ[k]!=1)
									break;
						}
						l++;
					}
					
					if(GrammerSet[i].mSetence[l]=='\0')	//
					{
					
						//rowIndex ,not changed.

						colIndex=vnIndex;

						//follow(rowIndex)->follow(colIndex);
						relationMatrix[rowIndex][colIndex]=1;
					}
					//END OF ADDED
					curVn=tmpChar2;

					goto COND2;
				}


COND3:				//tmpChar is vt and reach end.
					break;

COND4:			 					
					for(k=0;k<vnSetLen;k++)//Finding corresponding vn
						if(VNSet[k]==curVn)
							break;

					//ASSERTION
					if(k==vnSetLen)
					{
						printf("in cal_follow ,error happen.\n");
						return;
					}
					rowIndex=k;

					//Correct->:colIndex=i;
					colIndex=vnIndex;
			
							 //follow(curVn)->follow(vnIndex);				
					relationMatrix[rowIndex][colIndex]=1;
					break;
		}
	}
	
	//DEBUG CODE
	printf("relation matrix.\n");
	for(i=0;i<vnSetLen;i++)
		{
			for(j=0;j<matrixSize;j++)
				printf("%d,",relationMatrix[i][j]);
			printf("\n");
		}

	//USE FLOYD ALGO TO CAL CONNECTIVE
	for(k=0;k<matrixSize;k++)
		for(i=0;i<matrixSize;i++)
			for(j=0;j<matrixSize;j++)
			{
				//->Corrected if(relationMatrix[i][j]!=0) !!!
				if(relationMatrix[i][j]==0)
				{
					if(relationMatrix[i][k]==1&&relationMatrix[k][j]==1)
						relationMatrix[i][j]=1;
				}
			}

	//NOTE THE FOLLOW SET.
	for(i=0;i<vnSetLen;i++)
	{
		groupFollow[i].len=0;
		for(j=2*vnSetLen+1;j<matrixSize;j++)
		{
			
			if(VTSet[j-(2*vnSetLen+1)]!='z'&&relationMatrix[i][j]==1)
			{									
				groupFollow[i].ele[groupFollow[i].len]=VTSet[j-(2*vnSetLen+1)];
				groupFollow[i].len++;
			}
		}

		if(relationMatrix[i][2*vnSetLen]==1)//check whether include '#'
		{
			groupFollow[i].ele[groupFollow[i].len]='#';
			groupFollow[i].len++;
		}
	}

	if(DEBUG)
	{
		printf("\n==follow group condition==:\n");	
		fprintf(testFile,"\r\n==follow group condition==:\r\n");