sffxq.cpp

算符优先语法分析器.

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define MAX 50
char TR[MAX];
char S[MAX],vn[MAX],vt[MAX],s1[MAX];
/*
int Input(FILE *fp,char *s);
void init(int **m,int n);
int gramer(char *s);
void grammar(char *vn,char *vt,char *s1);
int exchang(char p);
int vntcount(char *s,char *vn,char *vt,int len);
void equal(char *s,int **m1);
void first(char *s,int **m2);
void firstterm(char *s,int **m);
 void last(char *s,int **m3);
 void lastterm(char *s,int **m);
 void warchall(int **M,int n);
 void change(int **M,int n);
 void first1(int **M,int n);
 void multi(int **M1,int **M2,int **M3,int n);
 int requirm(int **M1,int **M2,int **M3,int **M,int n);
 void print(int i,int j,int **M);
 int left(int s1,int tr1,int **M);
 int analysis(int **M);
*/

//********************************************************************************************
int Input(FILE *fp,char *s)
{ char c;
 int i=0,length;
 while((c=fgetc(fp))!=EOF)
 {
	 s[i++]=c;
 }
  s[i]='$';
  length=i;
  return length;
}
//********************************************************************************************
void init(int **m,int n)
{
	int i,j;
   for(i=0;i<n;i++)
	   for(j=0;j<n;j++)
		   m[i][j]=0;

}
//********************************************************************************************
int gramer(char *s)//记录终结符和非终结符的个数；
{  int i,k;
   i=0; k=0;
   while(s[i]!='$')
   { 
	   if((s[i]!=':')&&(s[i]!='=')&&(s[i]!='|')&&(s[i]!='\n')&&(s[i]!='\0')) 
      k++;
      i++;
   }
   return k;
}

//******************************************************************************************** 
void grammar(char *vn,char *vt,char *s1)
{   int k;
	char s[MAX];
	strcpy(s,vn);
	strcat(s,vt);
	strcpy(s1,s);
    k=strlen(s1);	
//	for(i=0;i<k;i++)
//	printf("s1[%d]=%c ",i,s1[i]);
} 
//********************************************************************************************
int exchang(char p)//终结符
{   int i=0;
	while(s1[i]!='#')
	{ if(p==s1[i]) return i;
	  i++;
	}
  if(p=='#') return -2;
  else return -1;
 
}
//********************************************************************************************
int vntcount(char *s,char *vn,char *vt,int len)//找出终结符和非终结符
{
	int i=0,k1=0,k2=0,flag=0,t;
	
    while(s[i]!='$')
	{   	     
	   if((s[i]>='A')&&(s[i]<='Z'))
	   {   
		   if(k1==0)  vn[k1++]=s[i];
		   else
		   {   
			     for(t=0;t<k1;t++)
					 if(vn[t]==s[i]) flag=1;
				 if(flag==0) vn[k1++]=s[i];
				 flag=0;
		   }
	   }
	   else{  
		      if((s[i]=='\n')||(s[i]=='|')||s[i]==':'||s[i]=='=') goto w;
		      if(k2==0)  vt[k2++]=s[i];
		      else
			  {
			        for(t=0;t<k2;t++)
					  if(vt[t]==s[i]) flag=1;
				    if(flag==0) vt[k2++]=s[i];
				 flag=0;
			  } 
	   }
w:     i++;
	}
	vt[k2]='#';
	return (k1+k2);
}
//*********************************************************************************************
void equal(char *s,int **m1)
{   int i,a,b;
	i=0;
	while(s[i]!='$')
	{ if((s[i]!='\n'&&s[i]!='|'&&s[i]!=':'&&s[i]!='=')&&(s[i+1]!='\n'&&s[i+1]!='|'&&s[i+1]!=':'&&s[i+1]!='='))
	{  a=exchang(s[i]);
	   b=exchang(s[i+1]);
	  m1[a][b]=1;
	}
	i++;
	}
}
//*********************************************************************************************
void equal1(char *s,int **m1)
{   int i,a,b;
	i=0;
	while(s[i]!='$')
	{ if(isupper(s[i])&&i>0)
	{   if(!isupper(s[i-1])&&!isupper(s[i+1]))
	   if(s[i-1]!='\n'&&s[i-1]!='|'&&s[i-1]!=':'&&s[i-1]!='='&&s[i+1]!='\n'&&s[i+1]!='|'&&s[i+1]!=':'&&s[i+1]!='=')
	   {	a=exchang(s[i-1]);
	   b=exchang(s[i+1]);
	   m1[a][b]=1;}
	}
	i++;
	}
}
//*********************************************************************************************
void first(char *s,int **m2)
{
	int flag=0;
	int a,b;
	
	int i=0;
	while(s[i]!='$')
	{ if((s[i]!='\n'&&s[i]!='|'&&s[i]!=':'&&s[i]!='=')&&(flag==0))
	{	a=exchang(s[i]); flag=1; }

		if(s[i]=='\n') flag=0;
		if(s[i]=='=') {b=exchang(s[i+1]); m2[a][b]=1;}
		if(s[i]=='|') {b=exchang(s[i+1]);  m2[a][b]=1;}
		i++;
	}
}
//*******************************************************************************************
void firstterm(char *s,int **m)
{
	int flag=0;
	int a,b,k=0;
    int i=0;
	while(s[i]!='$')
	{
		if((s[i]!='\n'&&s[i]!='|'&&s[i]!=':'&&s[i]!='=')&&(flag==0))
		{	a=exchang(s[i]); flag=1; }
		if(s[i]=='\n') {flag=0; k=0;}
		if(s[i]=='|') k=0;
         if(flag==1&&k==0)
		 { if((s[i]!='\n'&&s[i]!='|'&&s[i]!=':'&&s[i]!='='))
		 	 {  if(!isupper(s[i]))
		 {    b=exchang(s[i]);
		      m[a][b]=1;
			  k=1; 
		 }
		 }
		 }
		 i++;
	}

}

//*******************************************************************************************
 void last(char *s,int **m3)
{
	int flag=0;
    int a,b,i=0;
	while(s[i]!='$')
	{ if((s[i]!='\n'&&s[i]!='|'&&s[i]!=':'&&s[i]!='=')&&(flag==0))
	{	a=exchang(s[i]); flag=1; }
	if(s[i]=='\n'&&flag==1) { b=exchang(s[i-1]);m3[a][b]=1;flag=0;}
    		if(s[i]=='|') 
		{b=exchang(s[i-1]);
		m3[a][b]=1;}
		i++;
	}
}     

//*********************************************************************************************
void warchall(int **M,int n)//m+
{int i,j,k;
 for(i=0;i<n;i++)
	 for(j=0;j<n;j++)
		 if(M[j][i]!=0)
		 {for(k=0;k<n;k++)
		    if(M[i][k]!=0)
				M[j][k]=1;
		 }
}
//********************************************************************************************
void change(int **M,int n)
{int i,j;
 int N[MAX][MAX];
 for(i=0;i<n;i++)
	 for(j=0;j<n;j++)
	   N[i][j]=M[j][i]; 
 for(i=0;i<n;i++)
	 for(j=0;j<n;j++)
	   M[i][j]=N[i][j];

}
//********************************************************************************************
void first1(int **M,int n)
{int i;
 for(i=0;i<n;i++)
	 M[i][i]=1;
}
//********************************************************************************************
void multi(int **M1,int **M2,int **M3,int n)//
{int i,j,k;
/* for(i=0;i<n;i++)
	 for(j=0;j<n;j++)
      M3[i][j]=0;*/
 for(i=0;i<n;i++)
	 for(j=0;j<n;j++)
	 {for(k=0;k<n;k++)
	     M3[i][j]+=(M1[i][k]*M2[k][j]);
	  if(M3[i][j]!=0) M3[i][j]=1;
	 }
}
//********************************************************************************************
int requirm(int **M1,int **M2,int **M3,int **M,int n)//得到M[][]
{
int i,j;
	 for(i=0;i<n;i++)
	  for(j=0;j<n;j++)
        M[i][j]=-2;
     for(i=0;i<n;i++)
	  for(j=0;j<n;j++)
	  {
	   if(M[i][j]>1)
	   {
		   printf("此文法错误!!!!!!!!!!!!\n");
	       return 1;
	   }
	   if(M1[i][j]==1) M[i][j]=0;//=
	   if(M2[i][j]==1) M[i][j]=-1;//<
	   if(M3[i][j]==1) M[i][j]=1;//>
	   
	  }
     return 0; 

}
//********************************************************************************************
void print(int i,int j,int **M)
{
	int x,y,len;
	len=strlen(TR);
	for(x=0;x<=i;x++)
		printf("%c",S[x]);
	while(x<8){ printf(" "); x++; }
	 x=exchang(S[i]);
	 y=exchang(TR[j]);
	 if(x==-1) x=exchang(S[i-1]);
	 if(x==-2) 
	 {
		 if(y==-2)printf("OK    ");
		 else printf("<·   ");
	 }
	 else if(y==-2) printf("·>   ");
	 else 
	 {
		 switch(M[x][y])
		 {
	      case -1:printf("<·   ");break;
	      case 0: printf("≡   ");break;
          case 1: printf("·>   ");break;
		  default :printf("     ");
		 }
	 }
	 for(x=j;x<len;x++)
		 printf("%c",TR[x]);
	 while((x-j)<8){printf(" ");x++;}
}
//********************************************************************************************
int left(int s2,int tr1,int **M)/*找最左素短语*/
{
	int i,j;
    s2=s2-1;
	j=exchang(TR[tr1]);
	if(j!=-2)
	{
      while(S[s2]!='#')
	  {
	    i=exchang(S[s2]);
		if(i==-1)
		{
			i=exchang(S[s2-1]);
			if(M[i][j]==-1){ return s2-1;}
			if(i==-2)    return 1;
			else if(M[i][j]==0){return s2;}
			else {s2--;continue;}
		}
			
	    else
		{
		    if(M[i][j]==-1) 
			{
			 
			  return s2+1;
			}
		    else if(M[i][j]==0){s2--;continue;}
		    else { return s2+1;}
		}
	  }
	  if(S[s2]=='#')
	  {
		  S[1]='V';
		  return 1;
	  }
	  else return -1;
	}
	else 
	{
		while(S[s2]!='#')
		{
			i=exchang(S[s2]);
			if(i==-1){S[s2]='V';return s2;}
		    else 
			{
			  S[s2+1]='V';
			  return s2+1;
			}
		}
		if(S[s2]=='#'){return 1;}
		else return -1;
	}
}
//********************************************************************************************
int analysis(int **M)//分析过程
{
	int i=0,j=0,k=0,sh,trl,len,buf,fale=0;
	if(TR[j]=='#') {printf("该句子不能被识别\n");return 0;}
    print(i,j,M);
	printf("    \n");
	S[++i]=TR[j];
	len=strlen(TR);
	for(j=1;j<len;j++)
	{