//(1)S->aAcBe 
//(2)A->b 
//(3)A->Ab 
//(4)B->d 
#include <stdio.h> 
#include <iostream.h> 
#include <stdlib.h> 
#define stack_size 20 
#define stackincrement 10 
int p=0,q=0,zh,sh,x; 
char Vn[3]={'S','A','B'};   //非終結符 
char Vt[6]={'a','c','e','b','d','#'};   //終結符 
typedef struct { 
    char *bottom; 
    char *top; 
    int size; 
// char data[stack_size]; 
}stack; 
int Initstack(stack &s)        //初始化棧 
{ 
   s.bottom=(char *)malloc(stack_size*sizeof(char)); 
   if(!s.bottom) exit(-1); 
   s.top=s.bottom; 
   s.size=stack_size; 
   return(1); 
} 
int push(stack &s,char e)      //入棧 
{ 
 //int i; 
   if(s.top-s.bottom>=s.size){ 
      s.bottom=(char *)realloc(s.bottom,(stack_size+stackincrement)*sizeof(char)); 
      if(!s.bottom) exit(-1); 
      s.top=s.bottom+s.size; 
      s.size+=stackincrement; 
    
   } 
   *s.top++=e; 
     
    cout<<e<<"進s棧"; 
  //  s.data[x]=e;      //  
// x++; 
//輸出所有元素 
 //  for(i=0;i<x;i++)cout<<s.data[x]; 
   return(1); 
} 
int push2(stack &s,int e)      //入棧 
{ 
 //int i; 
   if(s.top-s.bottom>=s.size){ 
      s.bottom=(char *)realloc(s.bottom,(stack_size+stackincrement)*sizeof(char)); 
      if(!s.bottom) exit(-1); 
      s.top=s.bottom+s.size; 
      s.size+=stackincrement; 
    
   } 
   *s.top++=e; 
     
    cout<<e<<"進t棧"; 
   return(1); 
} 
int pop(stack &s,char *e)       //出棧 
{ 
   if(s.top==s.bottom) return(0); 
   *e=*--s.top; 
   cout<<*e<<"出s棧"<<"        "; 
   return(1); 
} 
int pop2(stack &s,int *e)       //出棧 
{ 
   if(s.top==s.bottom) return(0); 
   *e=*--s.top; 
  
   cout<<*e<<"出t棧"<<"        "; 
   return(1); 
} 

int action(int m,int n,char a)    //ACTION表 
{ 
  int i; 
  int act[10][6]={{2,0,0,0,0,0},{0,0,0,0,0,20}, 
  {0,0,0,4,0,0},{0,5,0,6,0,0},{12,12,12,12,12,12}, 
  {0,0,0,0,8,0},{13,13,13,13,13,13},{0,0,9,0,0,0}, 
  {14,14,14,14,14,14},{11,11,11,11,11,11 } }; 
  for(i=0; i<n; i++) 
     if(a==Vt[i]) 
     break; 
  if(i==n&&a!=Vt[n-1])return(0); 
  else  
  {zh=act[m][i]; 
   //if(zh==0)cout<<"出錯"<<endl; 
   //else return(zh);   
   return(zh); 
  } 
} 
int go(int m,int n,char a)    //goto表 
{ 
 int i; 
 int go[10][3]={{1,0,0},{0,0,0},{0,3,0},{0,0,0}, 
 {0,0,0},{0,0,7},{0,0,0},{0,0,0},{0,0,0} }; 
  for(i=0; i<n; i++) 
     if(a==Vn[i]) 
   break; 
  if(i==n&&a!=Vn[n-1])return(0); 
  else  
  {sh=go[m][i]; 
   //if(sh==0)cout<<"出錯"; 
   //else return(sh);   
    return(sh); 
  } 
} 

void main() 
{   
   char ch,y; 
   int x,v,e,u;
   int ok=1; 
   int i=0;
   int index=0;
   int k; 
   char st[20]; 
   stack s; 
   stack t; 
   
   cout<<" 輸入要分析的字符串(end by ';'):"<<endl; 
   cin>>st[0]; 
   while(st[i]!=';')
   { 
      i++; 
      cin>>st[i]; 
   }   
   Initstack(s); 
   Initstack(t); 
   push(s,'#'); 
   push2(t,0); 
   cout<<"\t"; 
   while(ok==1)
   { 
     ch=st[index]; 
     index++; 
     cout<<endl<<ch<<"分析"; 
     if(ch==';') 
     {
		 ok=0;
		 break; 
     } 
       
      y=ch; 
      cout<<"y="<<y<<"\t";  //y是終結符 
      pop2(t,&q);   //這兩句主要是為了得到當前的q值 
      push2(t,q); 
      cout<<"q="<<q<<"\t";   //q是0~9的數字 
      u=action(q,6,y); 
      cout<<"u="<<u<<"\t"; 
      if(action(q,6,y)>0&&action(q,6,y)<10)
	  { 
          push(s,ch); 
          push2(t,zh); 
         // q=zh; 
      } 
       if(action(q,6,y)>10&&action(q,6,y)<20)
	   { 
          switch(zh) 
          { 
		     case 11: 
	    	 for(i=0;i<5;i++)
			 {
				 pop(s,&y);pop2(t,&x);
			 } 
          push(s,'S'); 
            
          pop2(t,&e); 
          push2(t,e); 
          go(e,3,'S');  //查詢GOTO表 
          push2(t,sh);  //替換后的數字 
          index--; 
          break; 
          case 12: pop(s,&y);pop2(t,&x); 
          push(s,'A'); 
          pop2(t,&e); 
          push2(t,e); 
          go(e,3,'A'); 
          push2(t,sh); 
          index--; 
          break; 
          case 13:
				 pop(s,&y); 
                 pop(s,&y); 
                 pop2(t,&x); 
                 pop2(t,&x); 
                 push(s,'A'); 
                 pop2(t,&e); 
                 push2(t,e); 
                 go(e,3,'A'); 
                 push2(t,sh); 
                 index--; 
                 break; 
           case 14: 
				  pop(s,&y);
				  pop2(t,&x); 
                  push(s,'B');   
			      pop2(t,&e); 
                  push2(t,e); 
                  go(e,3,'B'); 
                  push2(t,sh); 
                  index--; 
                  break; 
           } 
	   } 
  if(action(q,6,y)==20) 
  {
	  cout<<"分析成功"<<endl; 
      ok=0; 
  } 
  else if(u==0)
  {
	  cout<<"出錯"<<endl;
      break;
  } 
  } 
}