csshi.h

一个LL1分析器,可以输入产生式的条数,以及产生式,开始符号 结束符号 可以输出堆栈的运行情况

#include "shuzu.h"
#include "stack.h"
#include <iostream>
using namespace std;
//类的开始
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;//不同的非终结字符个数
	int intpro;//产生式个数
	char bgchar;//开始字符
//......................................
	char string[20];
public:
csshi()
{
	intpro=0;
	intunsamech=0;
}
//输入输出产生式:
	void input();//
	void output();//
////////////////////////////////////////////////////////////////////////////////////////////
	int getpro();//
	char getbgch();//
	char getlch(int );//
	shuzu getrch(int );//
	bool inUnEndchar(char );//判断是否字符为非终结字符
	shuzu getEndch();//
	shuzu getunEndch();//
/////////////////////////////////////////////////////////////////
	bool infirst(char );//判断是否first集合中有空'&'
	void copyfirst(char ,char );//把前者的first集合并到后者中
	void inputfirst(char,int);//把前者字符添加到后面那行的first集合中，他能自动消除重复
	void getfirst();//
	void outfirst();//
///////////////////////////////////////////////////////////////////	
	void inputfollow(char,int );//把前者字符添加到后者那行的follow集合中，它能自动消除重复
	void copyfollow(char ,char );//把前者的follow集合并到后者中
	void firsttofollow(char ,char );//把前者的first除去非空元素并到后者的follow集合中
	void getfollow();//
	void outfollow();//
///////////////////////////////////////////////////////////////////////////////
	void inputselect(char ,int );//把这个字符添加到后者的select集合中
	void firsttoselect(char ,int );//把前者的first去空元素并到后面的select集合中
	void followtoselect(char ,int );//把前者的follow集合并到后者的select集合中
	void getselect();//
	void outselect();//
////////////////////////////////////////////////////////////////////////////////
	void getchart();//
	void outchart();//显示预测分析表
///////////////////////////////////////////////////////////////////////////////
	void mainfuction();
};
void csshi::input()
{
	cout<<"---------------------------------说明------------------------------------"<<endl;
	cout<<"版本：maXs   日期：2007-6-28  题目：LL(1)文法分析器"<<endl;
	cout<<"流程说明:1.输入产生式个数,(如6 回车)"<<endl;
	cout<<"         2.输入产生式,每行以'#'结束,(如E->ST#代表E->ST这条产生式)"<<endl;
	cout<<"         3.输入开始字符,如(E 回车)"<<endl;
	cout<<"         4.输入要测试的句子,以'#'结束,如(a,a,a)#"<<endl;
	cout<<"         5.输入是否要继续,(y or n)"<<endl;
	cout<<"使用说明:1.在产生式中,如果要输入E->空,就输入E->#这样就可以了。"<<endl;
	cout<<"         2.预测分析表里的数字代表产生式所对应的条数，按输入时的顺序排序。"<<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条产生式的左部如"E->i*F:E"
{
	return csshi::prochar[i][1];
}
shuzu csshi::getrch(int i)//得到第i条产生式的右部如"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存放的是右部字符的长度
	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"
{//其中的非终结字符包括为空的元素&
	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<<"添加一个"<<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<<"添加一个"<<csshi::first[i][2+k]<<"给"<<c1<<endl;
						firstchang1++;
						}
					}
				}
}
void csshi::getfirst()//得到的格式如"E->i*E:Ebi"
//说明,这里的a代表这个E的first集的元素个数,如果有2个就是c,如果有25个,就是z
{
	shuzu Unsz,szR;
//..........................................................
//get the unsame chars's number
	initshuzu(Unsz);
	Unsz=csshi::getunEndch();
	csshi::intunsamech=Unsz.chang;//**********
//..........................................................
	initshuzu(szR);
//把first集合这个2维数组的每行左段标示对应的元素
	for (int i=1;i<=csshi::intunsamech;i++)
	{
		csshi::first[i][1]=Unsz.ch[i];
		csshi::first[i][2]='a';
	}
//主算法程序开始:
	int intunsame;
	int tempf;char tempc;//标记要求谁的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])
			{	//标记要求谁的first集合
				tempc=csshi::first[i][1];
				tempf=i;
			}
		for (i=1;i<=csshi::intpro;i++)
			if (tempc==csshi::prochar[i][1])//找到对应的产生式i
			{
				szR=csshi::getrch(i);

				bool pd=true;
				int firstch=2;
				while (pd)
				if(szR.ch[firstch]>'Z' || szR.ch[firstch]<'A')
				{	
					//如果为终结符，直接添加到first集合中
					csshi::inputfirst(szR.ch[firstch],tempf);
					pd=false;
				}
				else//如果是非终结元素
				{
					csshi::copyfirst(szR.ch[firstch],tempc);
					if (csshi::infirst(szR.ch[firstch]))//如果这个字符的first集合中有空
					{
						if (firstch<=szR.chang)//如果没有到产生式右部的尾端
							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<<"添加一个"<<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<<"添加一个"<<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)//找到对应的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]!='&')