zhuchengxu.cpp

该程序的主要功能是要实现算符优先算法

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<fstream.h>
char str[8][20]={"\0"};
char FIRSTVT[8][10]={"\0"};
char LASTVT[8][10]={"\0"};
char Table[8][10]={"\0"};
char VT[10]="\0";int num=0;
typedef struct{
	char s[20];
	int k;
}Stack;
void InitStack(Stack &s)
{
 s.s[1]='#';
 for(int i=2;i<20;i++)
	 s.s[i]='\0';
 s.k=1;
}
void CompareG()
{
 char ch;int i=0,j=0,k=0,t=0;k=1;
 ifstream input("试验测试数据3-1.txt");
 if(!input)
 {
  cerr<<"cannot open the file!"<<endl;
  exit(1);
 }
 input.get(ch);
 while(!input.eof())
 {
  str[i][j++]=ch;
  if(ch>='A'&&ch<='Z'&&ch!='\n')
  {
   input.get(ch);	  
   if(ch>='A'&&ch<='Z')
   {
    cout<<"The G[x] are not a correct!"<<endl;
	exit(0);
   }
   if(!(ch>='A'&&ch<='Z')&&ch!='\n')  str[i][j++]=ch;
  }
  if(ch=='\n') 
  {
   str[i][j]='\0';i++;j=0;
  }
  input.get(ch);
 }
 num=i;cout<<"文法为："<<endl;
 for(k=0;k<=i;k++)
 {t=0;
  while(str[k][t]!='\0')
  {
   cout<<str[k][t];
   t++;
  }
  cout<<endl;
 }
  input.close();
}
void  QFirstvt()
{
 int i=0,j=0,k=0,s,t=0,a,b=1,flag=0;
 for(i=0;i<=num;i++)
 {
  j=0;k=0;
  FIRSTVT[i][k++]=str[i][j];j=3;
  while(str[i][j]!='\0')
  {
   if(str[i][j]>='A'&&str[i][j]<='Z')
   {
	j++;
	if(!(str[i][j]>='A'&&str[i][j]<='Z')&&str[i][j]!='|'&&str[i][j]!='\0')
	{
	 for(t=0;t<k;t++)
        if(str[i][j]!=FIRSTVT[i][t]) flag=1;
		else flag=0;
	 if(flag==1) FIRSTVT[i][k++]=str[i][j];
	}
	if(str[i][j]=='\0')
	{
	 j--;
     for(t=1;t<k;t++)
        if(str[i][j]!=FIRSTVT[i][t]) flag=1;
		else flag=0;
	 if(flag==1) FIRSTVT[i][k++]=str[i][j];
	}
	j++;
	while(str[i][j]!='|'&&str[i][j]!='\0') j++;
   }
   else if(str[i][j]=='|')    j++;
   else {
	   for(t=0;t<k;t++)
        if(str[i][j]!=FIRSTVT[i][t]) flag=1;
		else flag=0;
	   if(flag==1) FIRSTVT[i][k++]=str[i][j];
       while(str[i][j]!='|'&&str[i][j]!='\0') j++;
   }
  }
 }
t=0;k=1;
while(t<i)
{
 if(FIRSTVT[t][k]=='\0') {t++;k=1;}
 else  if(!(FIRSTVT[t][k]>='A'&&FIRSTVT[t][k]<='Z')) k++;
 else
 {
   for(a=0;a<i;a++)
   {   
	   b=1;
	   if(FIRSTVT[a][0]==FIRSTVT[t][k]&&t!=a)
		{
		 while(FIRSTVT[a][b]!='\0')
		 {
		  for(s=1;s<k;s++)
			  if(FIRSTVT[a][b]==FIRSTVT[t][s])  flag=1;
			  else flag=0;
		  if(flag==1) b++;
		  else 
		  {
		    FIRSTVT[t][k]=FIRSTVT[a][b];
		    b++;k++;
		  }
		  if(FIRSTVT[a][b-1]>='A'&&FIRSTVT[a][b-1]<='Z') k--;
		 }
		}
	 }
 }
}
cout<<"FIRSTVT为："<<endl;
for(t=0;t<i;t++)
{k=0;
 while(FIRSTVT[t][k]!='\0')
 {
  cout<<FIRSTVT[t][k];
  k++;
  if(k==1) cout<<":";
 }
 cout<<endl;
}
}
void  QLastvt()
{
 int i=0,j=0,k=0,s,t=0,a,b=1,flag=0;
 for(i=0;i<=num;i++)
 {
  j=0;k=0;
  LASTVT[i][k++]=str[i][j];
  j=3;
  while(str[i][j]!='\0'||str[i][j-1]!='\0')
  {
   if(str[i][j]>='A'&&str[i][j]<='Z')	j++;
   else if(str[i][j]=='|'||str[i][j]=='\0')    
   {
    if((str[i][j-1]>='A'&&str[i][j-1]<='Z')&&str[i][j-2]=='|') 
	{
	 for(t=0;t<k;t++)
        if(str[i][j-2]!=LASTVT[i][t]) flag=1;
		else flag=0;
	   if(flag==1) LASTVT[i][k++]=str[i][j-1];
	}
    if((str[i][j-1]>='A'&&str[i][j-1]<='Z')&&str[i][j-2]!='\0'&&str[i][j-2]!='|') 
	{
	 for(t=0;t<k;t++)
        if(str[i][j-2]!=LASTVT[i][t]) flag=1;
		else flag=0;
	   if(flag==1) LASTVT[i][k++]=str[i][j-2];
	}
	if(!(str[i][j-1]>='A'&&str[i][j-1]<='Z'))	
	{
	 for(t=0;t<k;t++)
        if(str[i][j-1]!=LASTVT[i][t]) flag=1;
		else flag=0;
	   if(flag==1) LASTVT[i][k++]=str[i][j-1];
	}
	j++;
   }
   else    j++;
  }
 }
t=0;k=1;
while(t<i)
{
 if(LASTVT[t][k]=='\0') {t++;k=1;}
 else  if(!(LASTVT[t][k]>='A'&&LASTVT[t][k]<='Z')) k++;
 else
 {
   for(a=0;a<i;a++)
   {   
	   b=1;
	   if(LASTVT[a][0]==LASTVT[t][k]&&t!=a)
		{
		 while(LASTVT[a][b]!='\0')
		 {
		  for(s=1;s<k;s++)
			  if(LASTVT[a][b]==LASTVT[t][s])  flag=1;
			  else flag=0;
		  if(flag==1) b++;
		  else 
		  {
		    LASTVT[t][k]=LASTVT[a][b];
		    b++;k++;
		  }
		  if(LASTVT[a][b-1]>='A'&&LASTVT[a][b-1]) k--;
		 }
		}
	 }
 }
}
cout<<"LASTVT为："<<endl;
for(t=0;t<i;t++)
{k=0;
 while(LASTVT[t][k]!='\0')
 {
  cout<<LASTVT[t][k];
  k++;
  if(k==1) cout<<":";
 }
 cout<<endl;
}
}
int Compare(char a,char b)
{
 int i=1,j=0,s=0,t=0;char ch;
 while(Table[i][j]!=a)
	 i++;
 s=i;i=0;j=1;
 while(Table[i][j]!=b)
	 j++;
 t=j;ch=Table[s][t];
 if(ch=='\0')  return -1;
 if(ch=='>') return 1;
 else  return 0;
}
void CreatTable()
{
 int i=0,s,a=0,t,k1=1,k2=1,k=1,col=0,row=0,j=0,num1=0;
 for(i=0;i<=num;i++)
 {j=3;
  while(str[i][j]!='\n'&&str[i][j]!='\0')
  {
   if(!(str[i][j]>='A'&&str[i][j]<='Z')&&str[i][j]!='|')  	
   {
	num1++;VT[k++]=str[i][j];
   }
   j++;
  }
 }
 i=0;VT[k++]='#';num1++;
 for(j=1;j<num1;j++)
   Table[i][j]=VT[j];
 Table[i][j]=VT[j];j=0;
 for(i=1;i<num1;i++)
	 Table[i][j]=VT[i];
 Table[i][j]=VT[i];
 for(i=0;i<=num;i++)
 {
  j=3;
  while(str[i][j]!='\0')
  {
   if(str[i][j]=='|')  j++;
   if(!(str[i][j]>='A'&&str[i][j]<='Z')&&!(str[i][j+1]>='A'&&str[i][j+1]<='Z')&&str[i][j+1]!='|'&&str[i][j+1]!='\0')
   {
	t=0;
	for(s=1;s<=num1;s++)
	  if(Table[s][t]==str[i][j]) col=s;
	s=0;
	for(t=1;t<=num1;t++)
		if(Table[s][t]==str[i][j+1]) row=t;
	Table[col][row]='=';
   }
   if(!(str[i][j]>='A'&&str[i][j]<='Z')&&!(str[i][j+2]>='A'&&str[i][j+2]<='Z')&&(str[i][j+1]>='A'&&str[i][j+1]<='Z')&&str[i][j+2]!='|'&&str[i][j+2]!='\0'&&str[i][j+1]!='|'&&str[i][j+1]!='\0')
   {
	t=0;
	for(s=1;s<=num1;s++)
	  if(Table[s][t]==str[i][j]) col=s;
	s=0;
	for(t=1;t<=num1;t++)
		if(Table[s][t]==str[i][j+2]) row=t;
	Table[col][row]='=';
   }
   if((!(str[i][j]>='A'&&str[i][j]<='Z'))&&(str[i][j+1]>='A'&&str[i][j+1]<='Z')&&str[i][j+1]!='|'&&str[i][j+1]!='\0')
   {
	t=0;a=0;k1=1;
	for(s=1;s<=num1;s++)
	  if(Table[s][t]==str[i][j]) col=s;
	while(str[i][j+1]!=FIRSTVT[a][0])
	    a++;
	 while(FIRSTVT[a][k1]!='\0')
	 {
	  s=0;
	  for(t=1;t<=num1;t++)
		if(Table[s][t]==FIRSTVT[a][k1]) row=t;
	  Table[col][row]='<';k1++;
     }
	}
   if((str[i][j]>='A'&&str[i][j]<='Z')&&(!(str[i][j+1]>='A'&&str[i][j+1]<='Z'))&&str[i][j+1]!='|'&&str[i][j+1]!='\0')
   {a=0;k2=1;
	while(str[i][j]!=LASTVT[a][0])
		a++;
	 while(LASTVT[a][k2]!='\0')
	 {
	  t=0;
	  for(s=1;s<=num1;s++)
	    if(Table[s][t]==LASTVT[a][k2]) col=s;
	  s=0;
	  for(t=1;t<=num1;t++)
		if(Table[s][t]==str[i][j+1]) row=t;
	  Table[col][row]='>';k2++;
     }
	}
   j++;
  }
 }
  s=num1;
  for(t=1;t<num1;t++)
     Table[s][t]='<';
  for(s=1;s<num1;s++)
     Table[s][t]='>';
  Table[num1][num1]='=';
  cout<<"分析表为："<<endl;
  for(i=0;i<=num1;i++)
  {
   for(j=0;j<=num1;j++)
      cout<<Table[i][j]<<" ";
   cout<<endl;
  }
}
void error()
{
 cout<<"不能够生成这样的句型！"<<endl;
 exit(0);
}
int Stringcompare(char a[])
{
 int i=0,j=0,k=0,num2=0,num1=0;
 while(a[k]!='\0')
 {
  num2++;
  k++;
 }
 k=0; j=3;
 while(i<=num)
 {
  if(!(str[i][j]>='A'&&str[i][j]<='Z')&&!(a[k]>='A'&&a[k]<='Z')&&str[i][j]==a[k]&&str[i][j]!='\0'&&a[k]!='\0')
  {
   while(str[i][j]!='\0'&&str[i][j]!='|')
   {
    if(!(str[i][j]>='A'&&str[i][j]<='Z')&&!(a[k]>='A'&&a[k]<='Z')&&str[i][j]==a[k])
    {
     k++;j++;num1++;
    }
	else if(!(str[i][j]>='A'&&str[i][j]<='Z')&&!(a[k]>='A'&&a[k]<='Z')&&str[i][j]!=a[k])
	{num1=0;j++;k=0;}
	else if(str[i][j]>='A'&&str[i][j]<='Z'&&a[k]>='A'&&a[k]<='Z')
	{
	 k++;j++;num1++;
	}
	else{num1=0;j++;k=0;}
   }
  }
  else if(str[i][j]=='|'||str[i][j]=='\0')
  {
    if(num2==num1) 	return i;
    else {k=0;
	      if(str[i][j]=='|') {j++;num1=0;}
		  else {i++;j=3;num1=0;}
	}
  }
  else if(str[i][j]>='A'&&str[i][j]<='Z'&&a[k]>='A'&&a[k]<='Z')   {j++;k++;num1++;}
  else	{k=0;num1=0;
         while(str[i][j]!='\0'&&str[i][j]!='|')
              j++;
  }
 }
 return -1;
}

void main()
{
 int i=0,j,x=1,t=1,n=1,p,p1=0,flag=0,number,m=0;
 char string[20]="\0",strToken[10]="\0",ch,Q;Stack s;
 CompareG();
 QFirstvt();
 QLastvt();
 CreatTable();
 cout<<"请输入一个句型："<<endl;
 cin>>string;
 while(string[i]!='\0')
 {
  j=1;
  while(VT[j]!='\0')
  {
   if(VT[j]==string[i]) flag=1;
   j++;
  }
  if(flag==0) 
  {
   cout<<"这个句型不正确！请重新输入："<<endl;
   cin>>string;
   i=0;
  }
  i++;
 }
 i=0;j=0;number=0;InitStack(s);
 cout<<"步骤"<<" 栈 "<<"  输入串 "<<"  动作  "<<endl;
 cout<<"  "<<number<<"  ";
 t=1;
 while(t<=s.k)
 {
  cout<<s.s[t];
  t++;
 }
 cout<<"  "<<string;number++;
 cout<<"    预备："<<endl;
 do{
    ch=string[i];
	if(!(s.s[s.k]>='A'&&s.s[s.k]<='Z')) x=s.k;//k指栈顶终结符，任何两终结符之间最多只有一个非终结符
	else x=s.k-1;
	m=Compare(s.s[x],ch);
	if(m==-1) {cout<<"句型错误！"<<endl;exit(0);}
    while(m)
	{
		do{
           Q=s.s[x];
	       if(!(s.s[x-1]>='A'&&s.s[x-1]<='Z')) x=x-1;
		   else x=x-2;
		}while(Compare(s.s[x],Q));
	 if(s.s[x]=='('&&s.s[s.k]==')')  t=x;
	 else t=x+1;p=0;p1=t;
     while(t<=s.k)
	 {
	  strToken[p]=s.s[t];
	  t++;p++;
	 }
     n=Stringcompare(strToken);
	 s.k=p1;s.s[s.k]=str[n][0];cout<<"  ";
	 cout<<number<<"  ";number++;t=1;
	 while(t<=s.k)
	 {
	  cout<<s.s[t];t++;
	 }
	 cout<<"  "<<string<<"   ";ch=string[i];
	 cout<<" 规约：";cout<<str[n][0]<<"->"<<strToken;
	 p=0;
     while(strToken[p]!='\0')
	 {
	  strToken[p]='\0';
	  p++;
	 }
	 cout<<endl;
	 if(s.s[x]>='A'&&s.s[x]<='Z'&&ch=='#')  x=x-1;
     m=Compare(s.s[x],ch);
     if(m==-1) {cout<<"句型错误！"<<endl;exit(0);}
	}
	if(!Compare(s.s[x],ch))
	{
	 cout<<"  "<<number<<"  ";
	 number++;
	 t=1;
	 s.k=s.k+1;s.s[s.k]=ch;
	 while(t<=s.k)
	 {
	  cout<<s.s[t];t++;
	 }
	 string[i]=' ';
	 cout<<"  "<<string;i++;
	 if(s.s[s.k]=='#')  cout<<"    接受"<<endl;
	 else cout<<"    移进"<<endl;
	}
	else error();
 }while(ch!='#');
}