#include<stdio.h>
#include<string.h>



char fenxibiao[8][8]={{'#','#','#','#','#','#','#','>'},{'#','#','=','<','#','<','#','>'},{'#',
'=','#','#','#','=','#','>'},{'#','#','<','<','=','<','#','>'},{'#','>','#','#','#','>','#','>'},
{'#','>','#','#','#','>','=','>'},{'#','>','#','#','#','>','#','>'},{'<','<','<','<','<','<','<',
'='}};



typedef struct
{char L[10];
 int top;
}zhan;



char chanshengshi[4][5]={"bAb","(B","a","Aa)"};



void zhichuzhan(zhan *t)
{t->top=0;
 t->L[t->top]='$';
}



int panduan1(zhan *p,char L[10],int t)
{char shunxu[8]={'s','b','A','(','B','a',')','$'};
 int i=0,j=0;
 while(i<8)
 {
	 if(p->L[p->top]==shunxu[i])
		 break;
	 else
		 i=i+1;
 }
 while(j<8)
 {
	 if(L[t]==shunxu[j])
		 break;
	 else
		 j=j+1;
 }
 if(fenxibiao[i][j]=='#')
	 return 0;
 else
	 if(fenxibiao[i][j]=='<')
		 return 1;
	 else
		 if(fenxibiao[i][j]=='=')
			 return 2;
		 else
			 return 3;
}




int panduan2(zhan *p)
{char shunxu[8]={'s','b','A','(','B','a',')','$'};
 int i=0,j=0;
 while(i<8)
 {
	 if(p->L[p->top-1]==shunxu[i])
		 break;
	 else
		 i=i+1;
 }
 while(j<8)
 {
	 if(p->L[p->top]==shunxu[j])
		 break;
	 else
		 j=j+1;
 }
 if(fenxibiao[i][j]=='#')
	 return 0;
 else
	 if(fenxibiao[i][j]=='<')
		 return 1;
	 else
		 if(fenxibiao[i][j]=='=')
			 return 2;
		 else
			 return 3;
}




void print(zhan *p,char L[10],int t)
{int i,j;
 printf("\n");
 for(i=0;i<=p->top;i++)
	 printf("%c",p->L[i]);
 printf("       ");
 for(j=t;L[j]!='\0';j++)
	 printf("%c",L[j]);
}





void main()
{zhan fenxizhan;
 zhan *s;
 s=&fenxizhan;
 zhichuzhan(s);
 char shuruliu[10];
 printf("請(qǐng)輸入要分析的語(yǔ)句(以'$'結(jié)束): ");
 scanf("%s",shuruliu);
 int ip=0;
 print(s,shuruliu,ip);/////////
 int k;
 char L1[10],L2[10];
 while(shuruliu[ip]!='\0')
 {
	 if(s->top==1&&s->L[s->top]=='S'&&shuruliu[ip]=='$')
	 {//print(s,shuruliu,ip);////////
	  printf("\n分析完成,您輸入的語(yǔ)句符合文法\n");
	  break;
	 }
	 else
	 {k=panduan1(s,shuruliu,ip);//
      if(k==0)
	  {printf("\n您輸入的語(yǔ)句不符合文法\n");
       break;
	  }
      if(k==1||k==2)
	  {s->top=s->top+1;
       s->L[s->top]=shuruliu[ip];
	   ip=ip+1;
	   print(s,shuruliu,ip);////////
	   continue;
	  }
	  if(k==3)
	  {   int i=0,j=0,t=0;
		  while(1)
		  {k=panduan2(s);//
		   if(k==1)
		   {L1[i]=s->L[s->top];
		    L1[i+1]='\0';
			break;
		   }
		   else
		   {L1[i]=s->L[s->top];
            i=i+1;
			s->top=s->top-1;
		   }    
		  }
		  while(i>=0)
		  {L2[j]=L1[i];
		   j=j+1;
		   i=i-1;
		  }
		  L2[j]='\0';
          while(t<4)
		  {
			  if(strcmp(chanshengshi[t],L2)==0)
				  break;
			  else
				  t=t+1;
		  }
		  if(t==0)
		  {s->L[s->top]='S';
		   print(s,shuruliu,ip);////////
		   printf("      S->%s",&L2);
		  }
		  else
			  if(t==1||t==2)
			  {s->L[s->top]='A';
			   print(s,shuruliu,ip);////////
			   printf("      A->%s",&L2);
			  }
			  else
				  if(t==3)
				  {s->L[s->top]='B';
				   print(s,shuruliu,ip);////////
				   printf("      B->%s",&L2);
				  }
				  else
				  {printf("\n您輸入的語(yǔ)句不符合文法\n");
				   break;
				  }
	  }
	 }
  
 }
 if(shuruliu[ip]=='\0')
	 printf("\n您輸入的語(yǔ)句不符合文法\n");
}