opf.h

用C++做的firstVT和lastVT

//对算符优先关系的约定
//=0
//>1
//<2
int locate(grammer *g,char ch);
void insert(grammer *g,int **VT,stack *s,char A,char a);
void getOPRlist(grammer *g,int **FVT,int **LVT,int **OPlist);
void anerlizeIt(grammer *g,int **OPList,char *str);
int VTorVN(char a);
void printList(char *r,char *c,int **list);
void OPFAnerlizer(grammer *g,char *str)
{
	int **FVT,**LVT,**OPlist,i,j,glen;
	char A,a;
	stack fs,ls;
	printf("请输入字符串：");
	scanf("%s",str);
	str[strlen(str)]='#';
	initStack(&fs);
	initStack(&ls);
	FVT=(int **)malloc(g->vn[0]*sizeof(int *));
	LVT=(int **)malloc(g->vn[0]*sizeof(int *));
	OPlist=(int **)malloc((g->vt[0]+1)*sizeof(int *));
	for(i=0;i<g->vn[0];i++)
	{
		FVT[i]=(int *)malloc(g->vt[0]*sizeof(int));
		LVT[i]=(int *)malloc(g->vt[0]*sizeof(int));
		for(j=0;j<g->vt[0];j++)
		{
			FVT[i][j]=LVT[i][j]=0;
		}
	}
	for(i=0;i<g->vt[0];i++)
	{
		OPlist[i]=(int *)malloc((g->vt[0]+1)*sizeof(int));
		for(j=0;j<g->vt[0];j++)
		{
			OPlist[i][j]=-1;
		}
	}
	for(i=0;i<g->genNum;i++)
	{
		glen=strlen(g->generator[i]);
//		printf("%d\n",glen);
		if(glen!=0)
		{
			
			if(!(g->generator[i][3]>='A'&&g->generator[i][3]<='Z'))
			{
				insert(g,FVT,&fs,g->generator[i][0],g->generator[i][3]);
			}
			else if(glen>=5&&!(g->generator[i][4]>='A'&&g->generator[i][4]<='Z'))
			{
				insert(g,FVT,&fs,g->generator[i][0],g->generator[i][4]);
			}
			
			if(!(g->generator[i][glen-1]>='A'&&g->generator[i][glen-1]<='Z'))
			{
				insert(g,LVT,&ls,g->generator[i][0],g->generator[i][glen-1]);
			}
			else if(glen>=5&&!(g->generator[i][glen-2]>='A'&&g->generator[i][glen-2]<='Z'))
			{
				insert(g,LVT,&ls,g->generator[i][0],g->generator[i][glen-2]);
			}
		}
	}
	while(!stackEmpty(&fs))
	{
		a=pop(&fs);
		A=pop(&fs);
		for(i=0;i<g->genNum;i++)
		if((glen=strlen(g->generator[i]))!=0)
		{
			if(A==g->generator[i][3])
				insert(g,FVT,&fs,g->generator[i][0],a);
		}
	}
	while(!stackEmpty(&ls))
	{
		a=pop(&ls);
		A=pop(&ls);
		for(i=0;i<g->genNum;i++)
		if((glen=strlen(g->generator[i]))!=0)
		{
			if(A==g->generator[i][strlen(g->generator[i])-1])
				insert(g,LVT,&ls,g->generator[i][0],a);
		}
	}
	printf("\n该文法的FIRSTVT表如下\n");
	printList(g->vn,g->vt,FVT);
	printf("\n该文法的LASTVT表如下\n");
	printList(g->vn,g->vt,LVT);
	getOPRlist(g,FVT,LVT,OPlist);
    printf("\n该文法的算法优先关系表如下\n");
	printList(g->vt,g->vt,OPlist);
	anerlizeIt(g,OPlist,str);
}
int locate(grammer *g,char ch)
{
	int i;
	if(ch>='A'&&ch<='Z')
		for(i=1;i<=g->vn[0];i++)
		{
			if(ch==g->vn[i]) return i;
		}
	else
		for(i=1;i<=g->vt[0];i++)
		{
			if(ch==g->vt[i]) return i;
		}
	return 0;
}

void insert(grammer *g,int **VT,stack *s,char A,char a)
{
	int r=locate(g,A)-1,c=locate(g,a)-1;
	if(!VT[r][c])
	{
		VT[r][c]=1;
		push(s,A);
		push(s,a);
	}
}
void getOPRlist(grammer *g,int **FVT,int **LVT,int **OPlist)
{
	int i,j,k;
	char temp1,temp2,temp3;
	for(i=0;i<g->genNum;i++)
	if(strlen(g->generator[i])!=0)
	{
		for(j=3;j<=strlen(g->generator[i])-2;j++)
		{
			temp1=g->generator[i][j];
			temp2=g->generator[i][j+1];
			temp3=g->generator[i][j+2];
			if(VTorVN(temp1)==1&&VTorVN(temp2)==1)//temp1和temp2均为非终结符
				OPlist[locate(g,temp1)-1][locate(g,temp2)-1]=0;
			if(j<=strlen(g->generator[i]-3)&&(VTorVN(temp1)==1&&VTorVN(temp3)==1&&VTorVN(temp2)==0))
				OPlist[locate(g,temp1)-1][locate(g,temp3)-1]=0;
			if(VTorVN(temp1)==1&&VTorVN(temp2)==0)
				for(k=1;k<=g->vt[0];k++)
					if(1==FVT[locate(g,temp2)-1][locate(g,g->vt[k])-1])
						OPlist[locate(g,temp1)-1][locate(g,g->vt[k])-1]=2;
					if(VTorVN(temp1)==0&&VTorVN(temp2)==1)
						for(k=1;k<=g->vt[0];k++)
							if(1==LVT[locate(g,temp1)-1][locate(g,g->vt[k])-1])
								OPlist[locate(g,g->vt[k])-1][locate(g,temp2)-1]=1;
		}
	}
}

int VTorVN(char a)
{//VN返回0，VT返回1
	if(a>='A'&&a<='Z') return 0;
	return 1;
}
void error(char *str)
{
	printf("\n失败! 输入串不是指定文法的句子~o~\n");
}
void success(char *str)
{
	printf("\n成功! 输入串是指定文法的句子^=^ \n");
}
void anerlizeIt(grammer *g,int **OPlist,char *str)
{
	char S[50],*strp=str;
	int i,j,k=1;
	char a,Q;
	
	S[k]='#';
	a=*strp;
	while(*(strp-1)!='#')
	{		
		if(VTorVN(S[k])==1) j=k;
		else j=k-1;
		if(OPlist[locate(g,S[j])-1][locate(g,a)-1]==1)
		{//S[j]>a
			do
			{
				Q=S[j];
				if(VTorVN(S[j-1])==1) j=j-1;
				else j=j-2;
			}while(OPlist[locate(g,S[j])-1][locate(g,Q)-1]!=2);
			k=j+1;
			S[k]='N';
			continue;
		}
		else if(OPlist[locate(g,S[j])-1][locate(g,a)-1]==2)
		{
			k=k+1;
			S[k]=a;
			a=*(++strp);
			continue;
		}
		else if(OPlist[locate(g,S[j])-1][locate(g,a)-1]==0)
		{
			if(OPlist[locate(g,S[j])-1][locate(g,'#')-1]==0)
			{
				success(str);
				break;//成功
			}
			else
			{
				k=k+1;
				S[k]=a;
				a=*(++strp);
				continue;
			}
		}
		error(str);//失败
		break;
	}
}
void printList(char *r,char *c,int **list)
{
	int i,j;
	for(i=0;i<5*(c[0])+3;i++)
		printf("-");
	printf("\n     ");
	for(i=1;i<=c[0];i++)
		printf("%-5c",c[i]);
	printf("\n");
	for(i=1;i<=r[0];i++)
	{
		printf("%-5c",r[i]);
		for(j=1;j<=c[0];j++)
			printf("%-5d",list[i-1][j-1]);
		printf("\n");
	}
	for(i=0;i<5*(c[0])+3;i++)
		printf("-");
}