yacc.cpp

实现编译器的YACC的LR1分析表自动的生成。

 //*************************构造LR1分析表***********************************************//
//*在判断两个状态是否相同时，严格的应该将formula,follow排序,但实际状态生成时是按顺序的，***//
//*所以似乎没影响，复杂情况未检测***//
//***************************周勇琦 2007年6月**********************//
#include<iostream.h>
#include<fstream.h>
#include <string>
    
 
ifstream syntaxIn("syntax.txt");                 //读入文法，注意文法格式，
ofstream analyseTableOut("analyseTable.txt"); 
    
//***********保存输入的文法************//          
struct setOfFormula                          //式子集
{
	char non_end;            //非终结符
	int numofformula;        //保存式子的个数
	char** formula;     
};
setOfFormula setofformula[100];            //分配空间

//**************保存状态***************//
int last=0;                       //记录上次调用newState()的State的编号
struct stateFormula                 
{
	char* formula;                 //记录式子
	int formulaid1,formulaid2;	   //记录式子的编号，由于第一个符号相同的式子组成一个集合，
								   //所以要两个值，一个表示式子集的号码，第二个表示式子在集合中的号码
	char* follow;                  //记录FOLLOW
	int position;				   //记录位置
	int numoffollow;               //记录FOLLOW的终结符的个数
};
struct Produce
{
	char sign;                   //产生新状态的终结符或非终结符
	int nextstate;               //新状态的编码,或式子的号码
};

class State
{
private:
	int IDofstate;                   //状态编号
	stateFormula*  stateformula;      //记录状态类中的式子，含FOLLOW          
	int numofformula;               //记录式子的个数,stateformula
	Produce*  produce;              //保存新状态的产生过程
	int numofproduce;
	
public:
	State(){};                       // 不可缺省，不然分配数组空间时会出错
	State(setOfFormula*);            //重载构造函数，生成第一个状态，下一个函数生成其余的状态
	State(State*,char);
	void addformula(stateFormula&,setOfFormula*);   //每个状态的起始的式子的当前位置为非终结符，
													//则应生成新的式子
	int alreadyExist();              //判断状态是否已经存在
	void newState();                //生成新的状态，采用递归调用
	void produceout();               //输出生成的LR1分析表到analyseTable.txt
	void stateout();                //输出每个状态，在屏幕，为辅助函数，便于分析
	void getAcc();					//找出所有状态的当前位置到达式子末式子的
};

int numofendchar=0;							//记录终结符的个数
int numofstate=0;                           //记录状态数
int numofset=1;                             //记录式子集的个数
State *ss=new State[1000];
char *Nonend=new char[numofset+1];          //保存非终结符 
char *endchar=new char[100];                //+，-，*，/，(,),N,I,and so on,保存终结符 
int **LR1list;                              //在内存保存LR1分析表
//*******************************************************************************//
//************************************输出每个状态*******************************//
void State::stateout()             //辅助函数
{
	cout<<"statenumber :           "<<IDofstate<<endl;
	for(int i=0;i<numofformula;i++)                      //输出每个式子
	{
		//***先输出式子和当前位置********//
		cout<<stateformula[i].formula<<"               "<<stateformula[i].position<<"                  ";
		//***接着输出FOLLOW**************//
		for(int j=0;j<stateformula[i].numoffollow;j++)
		{
			cout<<stateformula[i].follow[j];
		}
		cout<<endl;
	}
	cout<<endl;
	int s=0;
	cout<<"正数代表生成的新的状态的编号，负数代表当前状态的应该规约的式子的编号："<<endl;
	while(s<numofproduce)
	{
		cout<<produce[s].nextstate<<"         "<<produce[s].sign<<endl;
		s++;
	}
	cout<<endl<<endl;
}
//*******************************************************************************//
////**********************对每一个formula生成新的formula************************///
void State::addformula(stateFormula& stateformula1,setOfFormula* setofformula)             
                                                                    //对某一个formula看是否生成新的formula
{
	if(stateformula1.formula[stateformula1.position+1]=='\0')
		return;
	char ne=stateformula1.formula[stateformula1.position+1];
	//下面判断ne是否为终结符
	int i=0;
	int setnum=-1;         
	while(i<numofset)
	{
		if(setofformula[i].non_end==ne)
		{
			setnum=i;			///找到将要扩展的字符串集，若为终结符，则不需要扩展
			break;
		}
		i++;
	}
	if(i==numofset)       //说明为终结符
	{
		return;
	}
	int j=0;
	while(j<setofformula[setnum].numofformula)        //setnum为non_end的编号
	{
		bool is=false;     //判断是否已存在
		for(int p=0;p<numofformula;p++)              //与当前的所有formula比较
		{
			if(setofformula[setnum].formula[j]==stateformula[p].formula&&stateformula[p].position==0)
			//1判断式子setofformula[setnum].formula[j]是否已经存在,比较首地址,2判断当前位置
			{	
				//	is=true;
					if(setofformula[setnum].formula[j][2]=='\0')//$->E,E->F,F->G
					{//将stateformula1->follow[j]加到stateformula[p].follow
						for(int s1=0;s1<stateformula1.numoffollow;s1++)
						{		int s2=0;																										
							for(;s2<stateformula[p].numoffollow;s2++)
							{
								if(stateformula1.follow[s1]==stateformula[p].follow[s2])//已经存在
									break;
							}
							if(s2==stateformula[p].numoffollow)
							{//说明与已有的follow不重复
								stateformula[p].follow[stateformula[p].numoffollow]=stateformula1.follow[s1];
								stateformula[p].numoffollow++;
								//注意最后将stateformula[p].follow的最后加上'\0'，在构造函数里实现
							}
						}		
					}
					else                                       //E->E+F,E->E-F,F->F*G,...
					{
						stateformula[p].follow[stateformula[p].numoffollow]=stateformula1.formula[2];
						stateformula[p].numoffollow++;
						//注意最后将stateformula[p].follow的最后加上'\0',在构造函数里实现
					}
					is=true;                //formula已经存在
					j++;
					break;
			}
		}
		//*********************上面为式子已经存在的情况*******************//
		if(is==true)
		{
			is=false;
			continue;
		}
		//******************下面为is=false的情况,即要添加formula**********//
     	stateformula[numofformula].formula=new char[100];
		stateformula[numofformula].follow=new char[100];
		stateformula[numofformula].formula=setofformula[setnum].formula[j];
		stateformula[numofformula].position=0;
		stateformula[numofformula].formulaid1=setnum;
		stateformula[numofformula].formulaid2=j;
		if(stateformula1.formula[stateformula1.position+2]=='\0')          //注意不要出错
		{
			for(int d=0;d<stateformula1.numoffollow;d++)
			{
				stateformula[numofformula].follow[d]=stateformula1.follow[d];
			}
			stateformula[numofformula].numoffollow=stateformula1.numoffollow;
		}
		else
		{
			stateformula[numofformula].follow[0]=stateformula1.formula[stateformula1.position+2];
			stateformula[numofformula].numoffollow=1;
		}
		numofformula++;
		j++;
	}
}
//**************************************************************//
////*********************状态类的构造函数*********************//// 
State::State(setOfFormula* setofformula)
{
	IDofstate=0;
	numofproduce=0;
	stateformula=new stateFormula[100];       //
	produce=new Produce[100];
	for(int w=0;w<100;w++)                    //分配空间
	{
		stateformula[w].formula=new char[100];
		stateformula[w].follow =new char[100];
	}
	
	numofformula=1; 
	stateformula[0].formula=setofformula[0].formula[0];		 //$->.E,#
	stateformula[0].follow=new char[2];
	stateformula[0].follow[0]='#';
	stateformula[0].follow[1]='\0';
	stateformula[0].numoffollow=1;
	stateformula[0].position=0;               //其前面的符号所在的位置
	stateformula[0].formulaid1=0;
	stateformula[0].formulaid2=0;
	int i=0;
	while(i<numofformula)
	{
		addformula(stateformula[i],setofformula);     
		i++;
	}	
	//注意最后将stateformula[p].follow的最后加上'\0'
	for(int j=0;j<numofformula;j++)
	{
		stateformula[j].follow[stateformula[j].numoffollow]='\0';
	}
 	numofstate++;
}
State::State(State* state,char c)            
{ 
	IDofstate=numofstate;
	numofproduce=0;
	stateformula=new stateFormula[100];
	produce=new Produce[100];
	for(int w=0;w<100;w++)        //分配空间
	{
		stateformula[w].formula=new char[100];
		stateformula[w].follow =new char[100];
	}
 numofformula=0;
 //****************将前一个的状态的formula先加到新状态*********************//

	for(int i=0;i<state->numofformula;i++)
	{
		if(state->stateformula[i].formula[state->stateformula[i].position+1]==c)
		{
			stateformula[numofformula].formula=state->stateformula[i].formula;
			stateformula[numofformula].follow=state->stateformula[i].follow;
			stateformula[numofformula].position=state->stateformula[i].position+1;
			stateformula[numofformula].numoffollow=state->stateformula[i].numoffollow;
			stateformula[numofformula].formulaid1=state->stateformula[i].formulaid1;
			stateformula[numofformula].formulaid2=state->stateformula[i].formulaid2;
			numofformula++;
		}
	}
				//**************************完成*********************//
	int j=0;
	while(j<numofformula)
	{
		addformula(stateformula[j],setofformula);
		j++;
	}
}
///********************上面是构造函数*******************************//
//****************************************************************//
int State::alreadyExist()                        //比较当前State是否与原先已经存在的State相同,here
{                                  
	for(int i=0;i<numofstate;i++)
	{int is=1;    
		if(ss[i].numofformula==this->numofformula)  //先看formula的个数
		{
			for(int j=0;j<this->numofformula;j++)
			{
				//这里假设formula是有序的,每个formula与对应的formula比较
				if(stateformula[j].formula!=ss[i].stateformula[j].formula) //
				{
					is=0;
					break;
				}
				if(stateformula[j].position!=ss[i].stateformula[j].position)
				{
					is=0;
					break;
				}
				if(stateformula[j].numoffollow!=ss[i].stateformula[j].numoffollow)
				{
					is=0;
					break;
				}
				for(int d=0;d<stateformula[j].numoffollow;d++)
				{
					if(stateformula[j].follow[d]!=ss[i].stateformula[j].follow[d])
					{
						is=-1;
						break;
					}
				}
				if(is==-1)
				{
					is=0;
					break;
				}
			}
			if(1==is)
			{
				return i;
			}
		} 
	}
	return -1;
}
//********************从当前状态开始生成新的状态*****************//
void State::newState()            
{ 
	int numofnewstate=0;
	bool is;
	char *n=new char[numofformula];    
	for(int i=0;i<numofformula;i++)          //对每个式子进行扫描，
	{
		is=true;
		for(int e=0;e<numofnewstate;e++)
		{
			if(stateformula[i].formula[stateformula[i].position+1]==n[e])   //已经存在
			{
				is=false;
				break;
			}
		}
		if(stateformula[i].formula[stateformula[i].position+1]=='\0')
			is=false;
		if(is==true)
		{
			n[numofnewstate]=stateformula[i].formula[stateformula[i].position+1];
			numofnewstate++;
		}
	}

	if(numofnewstate==0)         
		return;
	n[numofnewstate]='\0';
	//上面得出生成新的状态的符号集,每个符号生成一个新的状态
	int m=-1;

	int lastnumofstate=numofstate;

	for(int j=0;j<numofnewstate;j++)
	{