#include<iostream>
#include<cstdlib>
#include<string>
#include<cctype>
#include<iomanip>
using std::setw;
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::right;
//using std::left;
const int count=10;//記錄產生式 的最大條數
const int size=20; //每條產生式 的最大長度
int pos=0;         //指示空字符的位置
int num=0;          //記錄當前輸入文法的產生式條數
string gene[count];//保存輸入的產生式
string vt;          //保存終結符
string left;         //保存非終結符
int first[count][size]; //記錄first表的值
int follow[count][size];//記錄follow表的值
//設置first表的值
void ff(const string &str,int n)
{
	size_t start=2;
	size_t index=0;
	size_t count1=0;
	do
	{
		start++;
		//如果該條產生式是以終結符開頭
		if(!isupper(str[start]))
		{//將該終結符添加到對應的first中
			index=vt.find(str[start]);
			first[n][index]=count1;
			count1++;
		}
		else
		{
			size_t s=start;
			int m;
			//是以非終結符開頭
			do
			{
				m=count-1;	
				while(m>=0&&str[s]!=gene[m][0])m--;//找到該非終結符對應的索引號
				if(first[m][0]==-1)//如果沒查找過m條產生式的first則查找
				{
					ff(gene[m],m);
				}
				for(int i=1;i<size;i++)//將該非終結符的first/^添加到當前產生式的first中
				{
					if(first[m][i]!=-1&&i!=pos)
						first[n][i]=count1;
				}
				s++;
				//若該終結符包含空字^且后接非終結符
			}while(first[m][pos]!=-1&&isupper(str[s]));
			if(first[m][pos]!=-1&&str[s]=='|')//如果前面的非終結符都包含^且后面沒有字符
				first[n][pos]=count1;          //將^包含到當前產生式的first中
			else if(first[m][pos]!=-1&&!isupper(str[s]))//如果前面的非終結符都包含^且后面接終結符
				first[n][vt.find(str[s])]=count1;//將該終結符添到first中
			count1++;
		}
		start=str.find_first_of('|',start);
	}while(start!=string::npos);
	first[n][0]=1;
}
void ll(const char ch)
{
	
	int m=num-1;
	while(m>=0&&gene[m][0]!=ch)m--;//m確定ch所在gene的索引
	follow[m][0]=1;
	if(m<0)return ;
	for(int i=0;i<num;i++)//檢查每條產生式的右部
	{
		
		size_t j=3;
		size_t index=0;
		size_t cc=0;
		while(1)
		{
			
			size_t dex=gene[i].find_first_of(ch,j);//找到i條產生式右部出現ch的位置
			if(dex==string::npos)break ;//沒找到ch則找下一條產生式
			dex++;
			//cout<<gene[i][dex]<<endl;
			//getchar();
			if(dex==gene[i].length())//如果ch位于該條產生式的末尾
			{
				if(follow[i][0]==-1)
				{
					ll(gene[i][0]);
				}
				for(int l=1;l<size;l++)//將該條產生式左部所對應的follow加到m的follow中
					if(follow[i][l]!=-1)
						follow[m][l]=1;
					break;                   //檢查下一條
			}
			//如果是終結符
			else if(cc=vt.find(gene[i][dex]),cc!=string::npos&&cc!=pos)
			{
				follow[m][cc]=1;
			}
			//如果是非終結符
			else if(cc=left.find(gene[i][dex]),cc!=string::npos)
			{	
				int kk;
				do
				{
					kk=num-1;
					//cout<<"i="<<i<<" dex="<<dex<<' ';
					//cout<<"gene[i][dex]="<<gene[i][dex]<<endl;
					while(kk>=0&&gene[kk][0]!=gene[i][dex])kk--;
					//把該非終結符所對應的first/^加到follow中
					if(kk<0)break;
					for(int ii=1;ii<size;ii++)
					{
						if(first[kk][ii]!=-1&&ii!=pos)
						{
							follow[m][ii]=1;
						}
					}
					dex++;
					if(dex==gene[i].length())break;
					//getchar();
					//cout<<"kk="<<kk<<' ';
					//cout<<"first[kk][pos]="<<first[kk][pos]<<endl;
					
					//如果該非終結符的first包含^且后面是非終結符，繼續循環
				}while(first[kk][pos]!=-1&&left.find(gene[i][dex])!=string::npos);
				//如果前面的非終結符都可推出^且已達本條產生式的末尾
				if(first[kk][pos]!=-1&&dex==gene[i].length())
				{
					if(follow[i][0]==-1)
					{
						ll(gene[i][0]);
					}
					for(int l=1;l<size;l++)//將該條產生式左部所對應的follow加到m的follow中
						if(follow[i][l]!=-1)
							follow[m][l]=1;
						break;
				}
				//如果前面的非終結符都可推出^且后面是|
				else if(first[kk][pos]!=-1&&gene[i][dex]=='|')
				{
					if(follow[i][0]==-1)
					{
						ll(gene[i][0]);
					}
					for(int l=1;l<size;l++)//將該條產生式左部所對應的follow加到m的follow中
						if(follow[i][l]!=-1)
							follow[m][l]=1;
						
				}
				//如果前面的非終結符都可推出^且當前為終結符
				else if(first[kk][pos]!=-1&&vt.find(gene[i][dex])!=string::npos&&vt.find(gene[i][dex])!=pos)
				{
					follow[m][vt.find(gene[i][dex])]=1;
				}
				
			}
			j=dex+1;
		}
	}
	
}
void foutputtable()
{
	int first1[count][size];
	for(int  i=0;i<count;i++)
		for(int j=0;j<size;j++)
			first1[i][j]=first[i][j];
		for( i=0;i<num;i++)
		{
			if(first1[i][pos]!=-1)
			{
				for(int j=0;j<size;j++)
					if(follow[i][j]!=-1)
						first1[i][j]=-2;
			}
		}
		cout<<"預測分析表的內容為："<<endl;
		cout<<"        ";
		for(i=1;i<vt.length();i++)
			if(i!=pos)
				cout<<vt[i]<<"       ";
			cout<<endl;
			for( i=0;i<num;i++)
			{
				cout<<gene[i][0]<<"       ";
				for(int j=1;j<size;j++)
				{
					if(j==pos)continue;
					if(first1[i][j]!=-1)
					{
						if(first1[i][j]==-2)
						{
							cout<<gene[i][0]<<"->^"<<"    ";
						}
						else
						{
							int c=first1[i][j];
							size_t start=3;
							size_t end=0;
							c++;
							string tt;
							while(c--)
							{
								end=gene[i].find_first_of('|',start+1);
								if(end==string::npos)end=gene[i].length();
								tt=gene[i].substr(start,end-start);
								start=end+1;
							}
							cout<<gene[i][0]<<"->"<<tt;
							for(int k=0;k<(8-tt.length()-3);k++)cout<<' ';
						}
						//cout<<setw(8-tt.length()-3);
					}
					else
					{
						cout<<"        ";
					}
					
				}
				cout<<endl;
			}
			
}
void foutput()
{
	cout<<"first表的內容為："<<endl;
	for(int i=0;i<num;i++)
	{
		cout<<gene[i][0]<<"        ";
		for(int j=1;j<size;j++)
		{
			if(first[i][j]!=-1)
				cout<<vt[j]<<' ';
		}
		cout<<endl;
	}
}
void loutput()
{
	cout<<"follow表的內容為："<<endl;
	for(int i=0;i<num;i++)
	{
		cout<<gene[i][0]<<"        ";
		for(int j=1;j<count;j++)
		{
			if(follow[i][j]!=-1)
				cout<<vt[j]<<' ';
		}
		cout<<endl;
	}
	
}
int main(int argc,char * argv[])
{
	
	int i=0,j=0;
	for(;i<count;i++)
		for(j=0;j<size;j++)
		{
			first[i][j]=-1;
			follow[i][j]=-1;
		}
		cout<<"請輸入文法的條數:";
		
		cin>>num;
		cout<<"請輸入文法:"<<endl;
		for(i=0;i<num;i++)
			cin>>gene[i];
		//for(i=0;i<num;i++)	cout<<endl<<gene[i]<<endl;
		
		for(i=0;i<count;i++)
		{
			left+=gene[i][0];
		}
		//cout<<"left="<<left<<endl;
		size_t index=0;
		vt+='@';
		for(i=0;i<num;i++)
		{
			index=2;
			while(index!=string::npos)
			{
				index++;
				index=gene[i].find_first_not_of(left,index);
				if(index==string::npos)break;
				if(gene[i][index]=='|'||vt.find(gene[i][index])!=string::npos)continue;
				vt+=gene[i][index];
			}
		}
		vt+='#';
		follow[0][vt.find('#')]=1;
		pos=vt.find('^');
		//cout<<"pos="<<pos<<endl;
		//cout<<"vt="<<vt<<endl;
		for(i=0;i<num;i++)
		{
			if(first[i][0]==-1)
			{
				ff(gene[i],i);
			}
		}
		foutput();
		
		for(i=0;i<num;i++)
		{
			if(follow[i][0]==-1)
				ll(gene[i][0]);
		}
		loutput();
		foutputtable();	
		return 0;
}