#include<iostream>
#include<string>
using namespace std;
const int length=10;
const int max=20;
typedef struct
{
	char gzl;
	char gzr[length];
	string firstl;
	string firstr;
	string follow;
	int  rvt;
}guize;
class wenfa
{
  private:
	  char (*s)[max];
	  char *vn;
	  char *vt;
	  int counter;
	  guize *gz;
      char sbf;
  public:
	  wenfa();
	  ~wenfa();
	  bool input();
	  void v();//分別裝入終結(jié)符和非終結(jié)符
	  void output();
	  void printf();
	  string first_l(char c);
	  string first_r(char c);
	  string follow(char c);
	  void process(int n,int n1);
	  void ff();
};
wenfa::wenfa()
{
	s=new char[length][max];
	vn=new char[length];
	vt=new char[length];
	gz=new guize[1];
	counter=0;
}
wenfa::~wenfa()
{
	delete []gz;
	delete []s;
	delete []vn;
	delete []vt;
}
bool wenfa::input()
{
	int hang=0;//文法的行數(shù)
	int pointer=0;
	int i,j;
	cout<<"輸入你要輸入文法的行數(shù) hang：";
	cin>>hang;
	cout<<"輸入你將要輸入的文法 ："<<endl;
	for(i=0;i<hang;i++)
	{
		cin>>s[i];
		for(j=0;j<strlen(s[i]);j++)
			if(s[i][j]=='|')pointer++;
	}
	if(hang>0){process(hang,pointer);return true;}
	else {cout<<"請輸入文法"<<endl;return false;}
}
void wenfa::process(int n,int n1)
{
		int i,j,k,hang=0,m=0,hang1=0;
		char *t=new char[length];
		counter=n+n1;
		gz=new guize[counter];
        for(i=0;i<n;i++)
		{
			m=0;
	        for(j=4;j<strlen(s[i]);j++)
			{
				if(s[i][j]=='|')
				{
				    gz[hang].gzl=s[i][0];
			        t[m]=0;
					m=0;
                    gz[hang].rvt=0;
					strcpy(gz[hang].gzr,t);
					for(k=0;k<strlen(t);k++)
					{
					    if(t[k]>='A'&&t[k]<='Z')
						 gz[hang].rvt++;
					}
			        hang++;
				}                    	
				else 
				{
					t[m++]=s[i][j];
				}
			}
	           gz[hang].gzl=s[i][0];
               t[m]=0;m=0;
               gz[hang].rvt=0;		  
       	       strcpy(gz[hang].gzr,t);
			   for(k=0;k<strlen(t);k++)
				{
					if(t[k]>='A'&&t[k]<='Z')
					gz[hang].rvt++;
				}
	           hang++;
		}
	    if(hang==counter) 
		{
		  cout<<"文法存入成功！"<<endl;
		  v();
		}
	    else cout<<"未成功存放!"<<endl;
        delete []t;
}
void wenfa::output()
{
		 int hang=0,i;
		 for( i=0;i<counter;i++)
		 {
		      cout<<gz[i].gzl<<"::="<<gz[i].gzr<<"     ";hang++;
			  if(hang%2==0)cout<<endl;
		 }
	     cout<<endl;
	     cout<<"非終結(jié)符Vn={ ";
	     for(i=0;vn[i]!='\0';i++)
		 cout<<vn[i]<<"、";
	     cout<<'\b'<<" }共有:"<<strlen(vn)<<"個;"<<endl;
         cout<<"終結(jié)符vt={ ";
	     for(i=0;vt[i]!='\0';i++)
		  cout<<vt[i]<<"、";
	     cout<<'\b'<<" }共有:"<<strlen(vt)<<"個;"<<endl;
}
void wenfa::v()
 {
     int i,j,k,c1=0,c2=0;
     bool bool1,bool2;
     for(i=0;i<counter;i++)
	 {
         bool1=false;
         for(j=0;j<c1;j++)
           if(vn[j]==gz[i].gzl) {bool1=true;break;}
         if(!bool1) vn[c1++]=gz[i].gzl;
         for(j=0;j<strlen(gz[i].gzr);j++){
			if(!(gz[i].gzr[j]>='A'&&gz[i].gzr[j]<='Z'))
			{
                bool2=false;
                for(k=0;vt[k]!='\0';k++)
                     if(vt[k]==gz[i].gzr[j]){bool2=true;break;}
					 if(bool2==false)vt[c2++]=gz[i].gzr[j];
			}
		 }
	 }
    vn[c1]=vt[c2]=0;
    cout<<endl;
}
string wenfa::first_l(char c)
{
	string f;
	for(int i=0;i<counter;i++)
	{
		if(gz[i].gzl==c)
		{
			if(gz[i].gzr[0]=='3'||(gz[i].gzr[0]<'A'&&gz[i].gzr[0]>'Z'))
			{
				gz[i].firstl=gz[i].firstl+gz[i].firstr[0];
			}
			else f=first_l(gz[i].gzr[0]);
			gz[i].firstl=gz[i].firstl+f;
		}
	}
	return gz[i].firstl;
}
string wenfa::first_r(char c)
{
	string f;
	for(int i=0;i<counter;i++)
	{
		if(gz[i].gzl==c)
		{
			if(gz[i].gzr[0]=='3'||(gz[i].gzr[0]<'A'&&gz[i].gzr[0]>'Z'))
			{
				gz[i].firstr=gz[i].firstr+gz[i].firstr[0];
			}
			else f=first_r(gz[i].gzr[0]);
				gz[i].firstr=gz[i].firstr+f;
		}
	}
	return gz[i].firstr;
}
string wenfa::follow(char c)
{
	string f;bool biaozhi=true;
	for(int i=0;i<counter;i++)
	{
		if(i==0)gz[i].follow="#";
		for(int j=0;j<counter;j++)
			for(int k=0;k<strlen(gz[j].gzr);k++)
				if(gz[j].gzr[k]==gz[i].gzl)
				{
					if(gz[j].gzr[k+1]<'A'&&gz[j].gzr[k+1]>'Z')
					{
						gz[i].follow=gz[i].follow+gz[j].gzr[k+1];
					}
					else
					{
						biaozhi=true;
						if(gz[j].gzr[k+1]!='\0')
						{
							for(int m=0;m<counter;m++)
							{
							 if(gz[j].gzr[k+1]==gz[m].gzl)
							 {
								if(gz[m].gzr[0]=='3')
								{
									biaozhi=false;
									break;
								}
								else continue;
							 }
							}
						    if (!biaozhi)f=follow(gz[j].gzl);
						    else f=gz[j].firstr[k];
						    gz[i].follow=gz[i].follow+f;
						}
						else
						{
							f=follow(gz[j].gzl);
							gz[i].follow=gz[i].follow+f;
						}
					}
				}
	}
	return gz[i].follow;

}
void wenfa::printf()
{
	cout<<"現(xiàn)在將輸出first和follow: "<<endl;
	for(int i=0;i<counter;i++)
	{
		cout<<"First("<<gz[i].gzl<<")={"<<gz[i].firstl<<"}"<<"  "
			<<"First("<<gz[i].firstr<<")={"<<gz[i].firstr<<"}"<<endl;
	}
	cout<<"顯示操作結(jié)束"<<endl;
}
void wenfa::ff()
{
	for(int i=0;i<counter;i++)
	{
		first_l(gz[i].gzl);
		first_r(gz[i].gzl);
		follow(gz[i].gzl);
	}
}
void main()
{
		wenfa wf;
		int m;
		bool boole,boolee=false;
		cout<<"0--退出            1--輸入規(guī)則"<<endl
			<<"2--顯示文法        3--顯示first和follow"<<endl
			<<"4--執(zhí)行first和follow算法"<<endl;
		while(1){
			    
				cout<<"輸入操作"<<endl;
				cin>>m;
				boole=false;
				switch(m){
				case 0:{boole=true;break;}
				case 1:{if(wf.input())
						   boolee=true;
					    
					    break;}
				case 2:{if(boolee) {wf.output();}
					      else cout<<"規(guī)則尚未輸入，請輸入后重試！"<<endl;
						break;
					   }
			
				case 3:{if(boolee) wf.printf();
					     else cout<<"規(guī)則尚未輸入，請輸入后重試！"<<endl;
						break;
					   }
				case 4:
					{
						if(boolee)wf.ff();
						break;
					}
				default : cout<<"輸入命令錯誤!!!"<<endl;
				}
				if(boole) break;
			}
}