#include<iostream.h>
#include<string.h>
#include<stdio.h>   //以上為三個頭文件
typedef struct       //定義數據類型array
{char R;           //變量R為char型
char r;             //變量 r為char型
int flag;            //變量flag為int型
}array;
typedef struct       //定義數據類型charLode
{char E;           //變量E為char型
char e;            //變量e為char型
}charLode;
typedef struct       //定義數據類型charstack棧
{ charLode *base;   //字符指針base為棧底
    int top;        //變量tor為int型，為棧頂
}charstack;
char str[80][80],arr[80][80],brr[80][80];//定義三個字符數組
array F[20];       //定義一個數組array
int m,kk,p,ppp,FF=1;//定義四個int型變量，其中FF初值為1
char r[10];        //定義字符數組r[]
int crr[20][20],FLAG=0;//定義二維數組crr[][],并定義FLAG初值為1
char ccrr1[1][20],ccrr2[20][1];      //字符型二維數組crr1[][]和crr2[][]
void Initstack(charstack &s)        //定義一個空棧charstack
{s.base=new charLode[20];
    s.top=-1;}
void push(charstack &s,charLode w)    //入棧，插入元素w為棧頂元素
{s.top++;                          //棧頂地址+1
   s.base[s.top].E=w.E;
   s.base[s.top].e=w.e;}
void pop(charstack &s,charLode &w)   //出棧，刪除棧頂元素w
{ w.E=s.base[s.top].E;
   w.e=s.base[s.top].e;
   s.top--;                //棧頂地址-1
}
int IsEmpty(charstack s)     //定棧是否為空
{if(s.top==-1) return 1; //若棧空，返回1
else return 0;        //若棧不為空，返回0
}
int IsLetter(char ch)//函數IsLetter是用來判斷一個字符是否為非終結符
{ if(ch>='A'&&ch<='Z')
     return 1;    //若字符為非終結符，則返回1
 else return 0;    //否則返回0
}
int judge1(int n)        //judge1是判斷文法是否是算符文法：若產生式中含有兩個相繼的非終結符則不是算符文法
{int j=3,flag=0;  //定義兩個int型變量j,flag,并分別定義初值為3和0
for(int i=0;i<=n;i++)    //循環條件
   while(str[i][j]!='\0')  //字符不為空
   {char a=str[i][j];    //把str[i][j]的值賦給變量a
   char b=str[i][j+1];   //把str[i][j+1]的值賦給變量b
   if(IsLetter(a)&&IsLetter(b))  //若a,b都為非終結符
{flag=1;break;}
else j++;}
   if(flag==1)
   return 0;
   else
   return 1;}
void judge2(int n)    //judge2是判斷文法G是否為算符優先文法：若不是算符文法或若文法中含空字或終結符的優先級不唯一則不是算符優先文法
{for(int i=0;i<=n;i++)          //循環條件
   if(str[i][3]=='~'||judge1(n)==0||FLAG==1)//'~'代表空字
   {cout<<"文法G不是算符優先文法!"<<endl;FF=0;break;}
   if(i>n)
   cout<<"文法G是算符優先文法!"<<endl;
}
int search1(char r[],int kk,char a)     //search1是查看存放終結符的數組r中是否含有重復的終結符
{for(int i=0;i<kk;i++)            //循環條件
   if(r[i]==a) break;
   if(i==kk) return 0;
   else  return 1;}
void createF(int n)    //createF函數是用F數組存放每個終結符與非終結符和組合，并且值每隊的標志位為0;F數組是一個結構體
{int k=0,i=1;char g;   //定義兩個int型變量，其中初值為k=0,i=1，一個型char變量g
char t[10];          //t數組用來存放非終結符
t[0]=str[0][0];       //把str[0][0]的值賦給變量t[0]
while(i<=n)         //判斷條件
{ if(t[k]!=str[i][0])
   {k++;t[k]=str[i][0];g=t[k];i++;}
   else i++;
}
kk=0;
    char c;
for(i=0;i<=n;i++)      //循環條件
{ int j=3;
   while(str[i][j]!='\0') //判斷條件
   { c=str[i][j];
    if(IsLetter(c)==0)
    {if(!search1(r,kk,c))
     r[kk]=c;kk++;         //r數組用來存放終結符
    }
    j++;
   } }
m=0;
for(i=0;i<k;i++)
   for(int j=0;j<kk-1;j++)     //循環條件
   { F[m].R=t[i];
    F[m].r=r[j];
    F[m].flag=0;
    m++;
   }}
void search(charLode w)      //search函數是將在F數組中尋找到的終結符與非終結符對的標志位值為1
{for(int i=0;i<m;i++)
   if(F[i].R==w.E&&F[i].r==w.e)
   {F[i].flag=1;break;}
}
void FirstVT(int n)//求FirstVT
{charstack sta;
charLode w;
int i=0;
Initstack(sta);
while(i<=n)
{  int k=3;
   w.E=str[i][0];
   char a=str[i][k];
   char b=str[i][k+1];
   if(!IsLetter(a))  //產生式的后選式的第一個字符就是終結符的情況
   { w.e=a;
    push(sta,w);
    search(w);
    i++;
   }
   else if(IsLetter(a)&&b!='\0'&&!IsLetter(b))    //產生式的后選式的第一個字符是非終結符的情況
   {w.e=b;
    push(sta,w);
    search(w);
    i++;
   }
   else i++;
}
charLode ww;
while(!IsEmpty(sta))
{ pop(sta,ww);
   for(i=0;i<=n;i++)
   {w.E=str[i][0];
    if(str[i][3]==ww.E&&str[i][4]=='\0')
    {w.e=ww.e;
     push(sta,w);
     search(w);
     break;
    }}}
p=0;int k=1;i=1;
while(i<m)
{ if(F[i-1].flag==1)
   { arr[p][0]=F[i-1].R;
    arr[p][k]=F[i-1].r;}
   while(F[i].flag==0&&i<m)
    i++;
   if(F[i].flag==1)
   {if(F[i].R==arr[p][0])
     k++;
      else {arr[p][k+1]='\0';p++;k=1;}
    i++;
   }}   
}
void LastVT(int n)//求LastVT
{charstack sta;
charLode w;
for(int i=0;i<m;i++)
   F[i].flag=0;
i=0;
Initstack(sta);
while(i<=n)
{ int k=strlen(str[i]);
   w.E=str[i][0];
   char a=str[i][k-1];
   char b=str[i][k-2];
   if(!IsLetter(a))
   { w.e=a;
    push(sta,w);
    search(w);
    i++;
   }
   else if(IsLetter(a)&&!IsLetter(b))
   { w.e=b;
    push(sta,w);
    search(w);
    i++;
   }
   else i++;
}
charLode ee;
while(!IsEmpty(sta))
{ pop(sta,ee);
   for(i=0;i<=n;i++)
   {w.E=str[i][0];
    if(str[i][3]==ee.E&&str[i][4]=='\0')
    {w.e=ee.e;
     push(sta,w);
     search(w);
    }}
}
int k=1;i=1;
ppp=0;
while(i<m)
{if(F[i-1].flag==1)
   { brr[ppp][0]=F[i-1].R;
    brr[ppp][k]=F[i-1].r;}
   while(F[i].flag==0&&i<m)
    i++;
   if(F[i].flag==1)
   { if(F[i].R==arr[ppp][0])
     k++;
      else {brr[ppp][k+1]='\0';ppp++;k=1;}
    i++; }
} }
void createYXB(int n)      //構造優先表
{int i,j;
    for(j=1;j<=kk;j++)
        ccrr1[0][j]=r[j-1];
for( i=1;i<=kk;i++)
   ccrr2[i][0]=r[i-1];
for(i=1;i<=kk;i++)
   for(j=1;j<=kk;j++)
    crr[i][j]=0;
   int I=0,J=3;
   while(I<=n)
   { if(str[I][J+1]=='\0')
    {I++;J=3;}
    else
    { while(str[I][J+1]!='\0')
     {char aa=str[I][J];
      char bb=str[I][J+1];
 if(!IsLetter(aa)&&!IsLetter(bb)) //優先及等于的情況，用1值表示等于
        {  for(i=1;i<=kk;i++)
         {  if(ccrr2[i][0]==aa)
            break; }
      for(j=1;j<=kk;j++)
        { if(ccrr1[0][j]==bb)
            break;}  
       if(crr[i][j]==0)
        crr[i][j]=1;
       else {FLAG=1;I=n+1;}
       J++;
      }
if(!IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]!='\0'&&!IsLetter(str[I][J+2]))                     //優先及等于的情況
      { for(i=1;i<=kk;i++)
       { if(ccrr2[i][0]==aa)
          break;}
      for(int j=1;j<=kk;j++)
       {  if(ccrr1[0][j]==str[I][J+2])
             break;}
       if(crr[i][j]==0)
        crr[i][j]=1;
       else {FLAG=1;I=n+1;}
      }
if(!IsLetter(aa)&&IsLetter(bb)) //優先及小于的情況，用2值表示小于
      { for(i=1;i<=kk;i++)
       { if(aa==ccrr2[i][0])
            break;}
        for(j=0;j<=p;j++)
        { if(bb==arr[j][0])
           break;}
        for(int mm=1;arr[j][mm]!='\0';mm++)
         { for(int pp=1;pp<=kk;pp++)
          {if(ccrr1[0][pp]==arr[j][mm])
                  break;}
         if(crr[i][pp]==0)
          crr[i][pp]=2;
         else {FLAG=1;I=n+1;}
         }
         J++;
      }
  if(IsLetter(aa)&&!IsLetter(bb)) //優先及大于的情況，用3值表示大于
      { for(i=1;i<=kk;i++)
       { if(ccrr1[0][i]==bb)
         break;}
        for(j=0;j<=ppp;j++)
       {if(aa==brr[j][0])
         break;}
       for(int mm=1;brr[j][mm]!='\0';mm++)
       {  for(int pp=1;pp<=kk;pp++)
        { if(ccrr2[pp][0]==brr[j][mm])
               break;}
        if(crr[pp][i]==0)
          crr[pp][i]=3;
        else {FLAG=1;I=n+1;}
       }
       J++;}
     }}
   }}
int judge3(char s,char a)   //search函數是將在F數組中尋找到的終結符與非終結符對的標志位值為1
{int i=1,j=1;
while(ccrr2[i][0]!=s)  i++;
while(ccrr1[0][j]!=a)  j++;
if(crr[i][j]==3) return 3;
else if(crr[i][j]==2) 
   return 2;
else if(crr[i][j]==1)
   return 1;
else return 0;
}
void print(char s[],char STR[][20],int q,int u,int ii,int k)//打印歸約的過程
{cout<<u<<"        ";
for(int i=0;i<=k;i++)
   cout<<s[i];
cout<<"         ";
for(i=q;i<=ii;i++)
   cout<<STR[0][i];
cout<<"        ";
}
void process(char STR[][20],int ii)//對輸入的字符串進行歸約的過程
{ cout<<"步驟"<<"    "<<"符號棧"<<"    "<<"輸入串"<<"       "<<"動作"<<endl;
int k=0,q=0,u=0,b,i,j;
char s[40],a;
s[k]='#';
print(s,STR,q,u,ii,k);
cout<<"預備"<<endl;
k++;u++;
 s[k]=STR[0][q];
q++;
print(s,STR,q,u,ii,k);
cout<<"移進"<<endl;
while(q<=ii)
{a=STR[0][q];
   if(!IsLetter(s[k])) j=k;
   else j=k-1;
   b=judge3(s[j],a);
   if(b==3)     //大于的情況進行歸約
   { while(IsLetter(s[j-1]))
     j--;
    for(i=j;i<=k;i++)
     s[i]='\0';
    k=j;s[k]='N';u++;
    print(s,STR,q,u,ii,k);
    cout<<"歸約"<<endl;
   }
   else if(b==2||b==1)    //小于或等于的情況移進
   {k++;
    s[k]=a;
    u++;
    q++;
    print(s,STR,q,u,ii,k);
    if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')
        cout<<"接受"<<endl;
    else cout<<"移進"<<endl;
   }
   else  {cout<<"出錯"<<endl;break;}
}
if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')
   cout<<"歸約成功"<<endl;
else cout<<"歸約失敗"<<endl;
}
void main()    //主函數
{int n,i,j;
cout<<"請輸入你要定義的文法G的產生式的個數n:";
cin>>n;
for(i=0;i<n;i++)
{gets(str[i]);
   j=strlen(str[i]);
   str[i][j]='\0';}
str[i][0]='Q';
str[i][1]='-';
str[i][2]='>';
str[i][3]='#';
str[i][4]=str[0][0];
str[i][5]='#';
str[i][6]='\0';
cout<<"你定義的產生式如下:"<<endl;
    for(i=0;i<=n;i++)
   cout<<str[i]<<endl;
if(judge1(n)==0)//判斷文法G是否為算符文法
   cout<<"文法G不是算符文法!"<<endl;
if(judge1(n)==1)
{cout<<"文法G是算符文法!"<<endl;
     createF(n);
FirstVT(n);
LastVT(n);
createYXB(n);
}
judge2(n);//判斷文法G是否為算符優先文法
   if(FLAG==0)
   {for(i=0;i<=p;i++)//打印FirstVT
    {cout<<"FirstVT("<<arr[i][0]<<")={";
       for(int l=1;arr[i][l+1]!='\0';l++)
    cout<<arr[i][l]<<",";
    cout<<arr[i][l]<<"}"<<endl;
    }
       cout<<"FirstVT(Q)={#}"<<endl; 
   for(i=0;i<=ppp;i++)//打印LastVT
   {cout<<"LastVT("<<arr[i][0]<<")={";
         for(int l=1;brr[i][l+1]!='\0';l++)
         cout<<brr[i][l]<<",";
      cout<<brr[i][l]<<"}"<<endl;
   }
       cout<<"LastVT(Q)={#}"<<endl;
   cout<<"優先表如下:"<<endl;
   for(i=1;i<kk;i++)//打印優先關系表
   {cout<<"   ";
    cout<<ccrr1[0][i];
   }
   cout<<endl;
   for(i=1;i<kk;i++)
   { cout<<ccrr2[i][0]<<" ";
    for(j=1;j<kk;j++)
    {if(crr[i][j]==0)
     cout<<" ";
    else if(crr[i][j]==1)
     cout<<"=";
    else if(crr[i][j]==2)
     cout<<"<";
    else if(crr[i][j]==3)
     cout<<">";
    cout<<"   ";
    }
    cout<<endl;
   }
}
if(FF==1)
{char STR[1][20];
cout<<"請輸入要規約的字符串:"<<endl;
gets(STR[0]);
   int ii=strlen(STR[0]);
STR[0][ii]='#';
   cout<<"下面是規約的過程:"<<endl;
process(STR,ii);   //歸約成功
}
}