#include "shuzu.h"
#include "stack.h"
#include <iostream>
using namespace std;
//類的開(kāi)始
class csshi
{
private:
	char prochar[20][20];
	char first[20][20];
	char follow[20][20];
	char select[20][20];
    char chart[30][30];
	int intunsamech;//不同的非終結(jié)字符個(gè)數(shù)
	int intpro;//產(chǎn)生式個(gè)數(shù)
	char bgchar;//開(kāi)始字符
//......................................
	char string[20];
public:
csshi()
{
	intpro=0;
	intunsamech=0;
}
//輸入輸出產(chǎn)生式:
	void input();//
	void output();//
////////////////////////////////////////////////////////////////////////////////////////////
	int getpro();//
	char getbgch();//
	char getlch(int );//
	shuzu getrch(int );//
	bool inUnEndchar(char );//判斷是否字符為非終結(jié)字符
	shuzu getEndch();//
	shuzu getunEndch();//
/////////////////////////////////////////////////////////////////
	bool infirst(char );//判斷是否first集合中有空'&'
	void copyfirst(char ,char );//把前者的first集合并到后者中
	void inputfirst(char,int);//把前者字符添加到后面那行的first集合中，他能自動(dòng)消除重復(fù)
	void getfirst();//
	void outfirst();//
///////////////////////////////////////////////////////////////////	
	void inputfollow(char,int );//把前者字符添加到后者那行的follow集合中，它能自動(dòng)消除重復(fù)
	void copyfollow(char ,char );//把前者的follow集合并到后者中
	void firsttofollow(char ,char );//把前者的first除去非空元素并到后者的follow集合中
	void getfollow();//
	void outfollow();//
///////////////////////////////////////////////////////////////////////////////
	void inputselect(char ,int );//把這個(gè)字符添加到后者的select集合中
	void firsttoselect(char ,int );//把前者的first去空元素并到后面的select集合中
	void followtoselect(char ,int );//把前者的follow集合并到后者的select集合中
	void getselect();//
	void outselect();//
////////////////////////////////////////////////////////////////////////////////
	void getchart();//
	void outchart();//顯示預(yù)測(cè)分析表
///////////////////////////////////////////////////////////////////////////////
	void mainfuction();
};
void csshi::input()
{
	cout<<"---------------------------------說(shuō)明------------------------------------"<<endl;
	cout<<"版本：maXs   日期：2007-6-28  題目：LL(1)文法分析器"<<endl;
	cout<<"流程說(shuō)明:1.輸入產(chǎn)生式個(gè)數(shù),(如6 回車)"<<endl;
	cout<<"         2.輸入產(chǎn)生式,每行以'#'結(jié)束,(如E->ST#代表E->ST這條產(chǎn)生式)"<<endl;
	cout<<"         3.輸入開(kāi)始字符,如(E 回車)"<<endl;
	cout<<"         4.輸入要測(cè)試的句子,以'#'結(jié)束,如(a,a,a)#"<<endl;
	cout<<"         5.輸入是否要繼續(xù),(y or n)"<<endl;
	cout<<"使用說(shuō)明:1.在產(chǎn)生式中,如果要輸入E->空,就輸入E->#這樣就可以了。"<<endl;
	cout<<"         2.預(yù)測(cè)分析表里的數(shù)字代表產(chǎn)生式所對(duì)應(yīng)的條數(shù)，按輸入時(shí)的順序排序。"<<endl;
	cout<<"-------------------------------------------------------------------------"<<endl;

	cout<<"*please input the number of chanshengshi:";
	cin>>csshi::intpro;
	cout<<"*please input the chanshengshi,use '#' end the line:"<<endl;;
	for (int i=1;i<=csshi::intpro;i++)
	{
		bool pd=true;
		int j=1;
		while(pd)
		{
			cin>>csshi::prochar[i][j];
			if (csshi::prochar[i][j]=='#')
				pd=false;
			j=j+1;
		}
	}
	cout<<"*please input the begin char:";
	cin>>csshi::bgchar;
}
void csshi::output()
{
	for (int i=1;i<=csshi::intpro;i++)
	{
		bool pd=true;
		int j=1;
		while(pd)
		{

			if (csshi::prochar[i][j]=='#')
				pd=false;
			else
			{
			cout<<csshi::prochar[i][j];
			j=j+1;
			}
		}
	cout<<endl;
	}
}
int csshi::getpro()
{
	return csshi::intpro;
}
char csshi::getbgch()
{
	return csshi::bgchar;
}
char csshi::getlch(int i)//得到第i條產(chǎn)生式的左部如"E->i*F:E"
{
	return csshi::prochar[i][1];
}
shuzu csshi::getrch(int i)//得到第i條產(chǎn)生式的右部如"E->(F+i):E(F+i)"
{
	shuzu sz;
	initshuzu(sz);
	sz.ch[1]=csshi::prochar[i][1];
	int j=4;
	while (csshi::prochar[i][j]!='#')
	{
	sz.ch[j-2]=csshi::prochar[i][j];
	j++;
	}
	if (j==4)
		sz.ch[2]='&';//&代表空
	sz.chang =j-4;//sz.chang存放的是右部字符的長(zhǎng)度
	return sz;
}
shuzu csshi::getEndch()//得到的格式如"E->i*E:i*"
{
	shuzu sz,szR;
	initshuzu(sz);
	initshuzu(szR);
	for (int i=1;i<=csshi::intpro;i++)
	{
		szR=csshi::getrch(i);
		for (int j=2;j<=szR.chang+1;j++)
			if (szR.ch[j]>'Z' || szR.ch[j]<'A')
            {
				sz.ch[sz.chang]=szR.ch[j];
				sz.chang ++;
			}
	}
	sz.chang--;
	cutsamech(sz);
	return sz;
}
shuzu csshi::getunEndch()//得到的格式如"E->i*T:ET"
{//其中的非終結(jié)字符包括為空的元素&
	shuzu sz,szR;
	initshuzu(sz);
	initshuzu(szR);
	for (int i=1;i<=csshi::intpro;i++)
	{
		szR=csshi::getrch(i);
		for (int j=1;j<=szR.chang;j++)
			if (szR.ch[j]<='Z' && szR.ch[j]>='A')
            {
				sz.ch[sz.chang]=szR.ch[j];
				sz.chang ++;
			}
	}
	sz.chang--;	
	cutsamech(sz);
	return sz;
}

bool csshi::inUnEndchar(char c)
{
	bool jg=true;
	shuzu Unsz;
	initshuzu(Unsz);
	Unsz=csshi::getunEndch();
	for (int i=1;i<=Unsz.chang;i++)
		if (c!=Unsz.ch[i])
			jg=false;
	return jg;
}
bool csshi::infirst(char c)
{
	bool jg=false;
	for (int i=1;i<=csshi::intunsamech;i++)
		if (c==csshi::first[i][1])
		{
			int firstchang=int(csshi::first[i][2]-'a');
			for (int k=1;k<=firstchang;k++)
				if ('&'==csshi::first[i][k+2])
					jg=true;
		}
	return jg;
		
}
void csshi::inputfirst(char c,int i)
{
	int firstchang=int(csshi::first[i][2]-'a');
	bool pd=true;
	for (int j=3;j<=2+firstchang;j++)
		if (csshi::first[i][j]==c)
			pd=false;
	if(pd)
	{
		csshi::first[i][3+firstchang]=c;
		csshi::first[i][2]++;
	//	cout<<"添加一個(gè)"<<c<<"給"<<csshi::first[i][1]<<endl;
	}
}
void csshi::copyfirst(char c,char c1)
{
	if (c!=c1) 
	for (int i=1;i<=csshi::intunsamech;i++)
		if (csshi::first[i][1]==c)
			for (int j=1;j<=csshi::intunsamech;j++)	
				if (csshi::first[j][1]==c1)
				{
					int firstchang=int(csshi::first[i][2]-'a');
					int firstchang1=int(csshi::first[j][2]-'a');
					for (int k=1;k<=firstchang;k++)
					{
						bool pd=true;
						for (int tempi=3;tempi<=2+firstchang1;tempi++)
							if (csshi::first[j][tempi]==csshi::first[i][2+k])
								pd=false;
						if(pd)
						{
						csshi::first[j][3+firstchang1]=csshi::first[i][2+k];
						csshi::first[j][2]++;
					//	cout<<"添加一個(gè)"<<csshi::first[i][2+k]<<"給"<<c1<<endl;
						firstchang1++;
						}
					}
				}
}
void csshi::getfirst()//得到的格式如"E->i*E:Ebi"
//說(shuō)明,這里的a代表這個(gè)E的first集的元素個(gè)數(shù),如果有2個(gè)就是c,如果有25個(gè),就是z
{
	shuzu Unsz,szR;
//..........................................................
//get the unsame chars's number
	initshuzu(Unsz);
	Unsz=csshi::getunEndch();
	csshi::intunsamech=Unsz.chang;//**********
//..........................................................
	initshuzu(szR);
//把first集合這個(gè)2維數(shù)組的每行左段標(biāo)示對(duì)應(yīng)的元素
	for (int i=1;i<=csshi::intunsamech;i++)
	{
		csshi::first[i][1]=Unsz.ch[i];
		csshi::first[i][2]='a';
	}
//主算法程序開(kāi)始:
	int intunsame;
	int tempf;char tempc;//標(biāo)記要求誰(shuí)的first的集合
for(int xh=1;xh<=csshi::intunsamech;xh++)
{   intunsame=0;
	while (intunsame<=csshi::intunsamech)
	{
		intunsame++;
		for (int i=1;i<=csshi::intunsamech;i++)
			if (csshi::first[i][1]==Unsz.ch[intunsame])
			{	//標(biāo)記要求誰(shuí)的first集合
				tempc=csshi::first[i][1];
				tempf=i;
			}
		for (i=1;i<=csshi::intpro;i++)
			if (tempc==csshi::prochar[i][1])//找到對(duì)應(yīng)的產(chǎn)生式i
			{
				szR=csshi::getrch(i);

				bool pd=true;
				int firstch=2;
				while (pd)
				if(szR.ch[firstch]>'Z' || szR.ch[firstch]<'A')
				{	
					//如果為終結(jié)符，直接添加到first集合中
					csshi::inputfirst(szR.ch[firstch],tempf);
					pd=false;
				}
				else//如果是非終結(jié)元素
				{
					csshi::copyfirst(szR.ch[firstch],tempc);
					if (csshi::infirst(szR.ch[firstch]))//如果這個(gè)字符的first集合中有空
					{
						if (firstch<=szR.chang)//如果沒(méi)有到產(chǎn)生式右部的尾端
							firstch++;
						else
						{
							pd=false;
							csshi::inputfirst('&',tempf);
						}
					}//if (csshi::infirst(szR.ch[firstch]))
					else
						pd=false;
				}//else
			}
	}//while(intunsame<=csshi::intunsamech)
}//for(xh)
}//end getfirst fuction
void csshi::outfirst()
{
	cout<<".............................................................."<<endl;	
	for (int i=1;i<=csshi::intunsamech;i++)
	{
		cout<<csshi::first[i][1]<<"'s first:";
		if (csshi::first[i][2]=='a')
			cout<<"empty";
		else
		{
			bool pd=true;
			char c='a';int j=3;
			while(pd)
			{
				if (c==csshi::first[i][2])
					pd=false;
				else
				{
				cout<<csshi::first[i][j];
				j=j+1;
				c++;
				}
			}
		}
   	cout<<endl<<csshi::first[i][1]<<"'s number:"<<int(csshi::first[i][2]-'a');
	cout<<endl;
	}
	cout<<".............................................................."<<endl;
}
void csshi::inputfollow(char c,int i)
{
	int followchang=int(csshi::follow[i][2]-'a');
	bool pd=true;
	for (int j=3;j<=2+followchang;j++)
		if (csshi::follow[i][j]==c)
			pd=false;
	if(pd)
	{
		csshi::follow[i][3+followchang]=c;
		csshi::follow[i][2]++;
	//	cout<<"添加一個(gè)"<<c<<"給"<<csshi::follow[i][1]<<endl;
	}
}
void csshi::copyfollow(char c,char c1)
{
if (c!=c1) 
	for (int i=1;i<=csshi::intunsamech;i++)
		if (csshi::follow[i][1]==c)
			for (int j=1;j<=csshi::intunsamech;j++)	
				if (csshi::follow[j][1]==c1)
				{
					int followchang=int(csshi::follow[i][2]-'a');
					int followchang1=int(csshi::follow[j][2]-'a');
					for (int k=1;k<=followchang;k++)
					{
						bool pd=true;
						for (int tempi=3;tempi<=2+followchang1;tempi++)
							if (csshi::follow[j][tempi]==csshi::follow[i][2+k])
								pd=false;
						if(pd)
						{
						csshi::follow[j][3+followchang1]=csshi::follow[i][2+k];
						csshi::follow[j][2]++;
					//	cout<<"添加一個(gè)"<<csshi::follow[i][2+k]<<"給"<<c1<<endl;
						followchang1++;
						}
					}
				}
}
void csshi::firsttofollow(char cfs,char cfl)
{
	for (int i=1;i<=csshi::intunsamech;i++)
		if (csshi::first[i][1]==cfs)
			for (int j=1;j<=csshi::intunsamech;j++)	
				if (csshi::follow[j][1]==cfl)//找到對(duì)應(yīng)的first集合與follow集合i,j
				{
					int firstchang=int(csshi::first[i][2]-'a');
					int followchang=int(csshi::follow[j][2]-'a');
					for (int k=1;k<=firstchang;k++)
					{
						bool pd=true;
						for (int tempi=3;tempi<=2+followchang;tempi++)
							if (csshi::follow[j][tempi]==csshi::first[i][2+k])
								pd=false;
						if(pd && csshi::first[i][2+k]!='&')