yacc.cpp

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

		ss[numofstate]=State(this,n[j]); 
		//下面判断状态是否已经存在
		m=ss[numofstate].alreadyExist();
		if(m==-1)                    //状态原先不存在,原先是写的‘=’ ，应该是‘==’，所以开始一直死循环
		{
			produce[numofproduce].sign=n[j];                    //LR1分析表Si,i
			produce[numofproduce].nextstate=numofstate;
			numofstate++;
			numofproduce++;
		}
		else
		{
			//调用析构函数
			ss[numofstate].~State();
			produce[numofproduce].sign=n[j];
			produce[numofproduce].nextstate=m;
			numofproduce++;
		}
	}
	int number=numofstate;	
	while(last<numofstate-1)
	{
		ss[++last].newState();
	}
}
//**************************LR1分析表Ri********************//
void State::getAcc()                
{
	for(int i=0;i<numofformula;i++)
	{ //************每个式子判断******************//
		if(stateformula[i].formula[stateformula[i].position+1]=='\0')
		{//********位置已经移动到最后*******//
			if(stateformula[i].formula[0]=='$')
			{
				produce[numofproduce].nextstate=-255;
				produce[numofproduce].sign='#';
				numofproduce++;
				return;
			}
			for(int d=0;d<stateformula[i].numoffollow;d++)
			{
				int aa=0;
				for(int cc=0;cc<stateformula[i].formulaid1;cc++)
				{
					aa+=setofformula[cc].numofformula;
				}
				aa+=stateformula[i].formulaid2;
				//**********上面是求式子的编号**************//
				produce[numofproduce].nextstate=-aa-1;
				produce[numofproduce].sign=stateformula[i].follow[d];
				numofproduce++;
			} 
		}
	}
}
//************************将每个状态的produce写到LR1list数组里**************//
void State::produceout()
{
	for(int i=0;i<numofproduce;i++)
	{
		char a=produce[i].sign;
		int m=0;
		while(m<numofendchar)      //先看是不是终结符
		{
			if(endchar[m]==a)
			{
				LR1list[IDofstate][m]=produce[i].nextstate;
				break;
			}
			m++;
		}
		if(m==numofendchar)      //再看是不是非终结符
		{
			m=0;
			while(m<numofset)
			{
				if(Nonend[m+1]==a)           //不考虑'$'
				{
					LR1list[IDofstate][m+numofendchar]=produce[i].nextstate;
					break;
				}
				m++;
			}
		}
	}
}
//****************************************************************************************//
//****************************************************************************************//
void main()
{
	//**********************************第一步***************************//
	//**************这里假设所有终结符或非终结符都是单字符的，比如N代表NUM，I代表ID
	char p=syntaxIn.get();  
	while(p==' '||p=='\n'){p=syntaxIn.get();}                              //跳过空格和空行
	setofformula[0].non_end='$';                                          //E'用$表示 
	setofformula[0].formula=new char*[2];
	if(p==EOF) exit(0);
	setofformula[0].formula[0]=new char[3];
	setofformula[0].formula[0][0]='$';
	setofformula[0].formula[0][1]=p;
	setofformula[0].formula[0][2]='\0';             //否则输出的话会是乱码
	setofformula[0].formula[1]='\0';                //否则输出的话会是乱码
	setofformula[0].numofformula=1;
	
	int numofformula=0;                  //一个式子集中式子的个数,新建一个式子集，其值为0
	int positionofformula=0;             //式子的当前字符的位置，新建一个式子，其值为0

	setofformula[1].formula=new char*[10];
	setofformula[1].formula[0]=new char[10];
	setofformula[1].formula[0][0]=p;
	setofformula[1].non_end=p;
	positionofformula=1;
	numofformula=1;
	numofset=2;      
	
	p=syntaxIn.get(); 
	while(p!=EOF)
	{
		if(p==':'||p=='\n'||p==' ')
		{
			p=syntaxIn.get(); 
			continue;
		}
		if(p==';')
		{
			setofformula[numofset-1].formula[numofformula-1][positionofformula]='\0';
			setofformula[numofset-1].formula[numofformula]='\0';
			setofformula[numofset-1].numofformula=numofformula;    //一个式子集完成，保存其式子数目
			//*******先要完成'|'情况下一样的操作**********//
		 	numofformula=1;               //个数为1               
			positionofformula=1;           //第一个位置为读入的非终结符
			//*************下面再读入一个字符************//
			p=syntaxIn.get();
			while(p==' '||p=='\n'){p=syntaxIn.get();}                              //跳过空格和空行
			if(p=='\n')
				p=syntaxIn.get();          //行末有个换行符,假设开始没空格
		 	if(p==EOF)                     //已经是最后
			{
				setofformula[numofset].formula='\0';
				break;
			}
			numofset++;
			setofformula[numofset-1].formula=new char*[10];
			setofformula[numofset-1].formula[0]=new char[10];
			setofformula[numofset-1].non_end=p;                                 //
			setofformula[numofset-1].formula[0][0]=p;
			p=syntaxIn.get();
			continue;	
		}
		if(p=='|')
		{
			////*****************先在前一个式子的最后置'\0'************////
			setofformula[numofset-1].formula[numofformula-1][positionofformula]='\0';
			////*****************接着初始化*********////////
			numofformula++;

			setofformula[numofset-1].formula[numofformula-1]=new char[10];
			setofformula[numofset-1].formula[numofformula-1][0]=setofformula[numofset-1].non_end;
			positionofformula=1; 
			p=syntaxIn.get();
			continue;
		}
		setofformula[numofset-1].formula[numofformula-1][positionofformula]=p;
		positionofformula++;
		p=syntaxIn.get();
	}
	
//*******************************上面的代码将语法规则读入程序********************************///
//******************************************************************************************/// 
//******************************************************************************************/// 
		//**********************************第二步***************************//
//****************************************保存所有非终结符**************************************//
	for(int i=0;i<numofset;i++)                     //numofset为formula集的个数
	{
		Nonend[i]=setofformula[i].non_end;         //E,F,G,and so on,保存非终结符   
	}
    Nonend[numofset]='\0';
//********************************保存所有终结符**************************************//
//***************************通过对读入的式子进行逐个扫描实现*************************//	  
	
	bool isnonend=false;			//标明当前字符是否已经为非终结符
	bool already=false;             //标明当前字符是否已经在终结符串
	for(int j=0;j<numofset;j++)     //对读入的文法进行扫描
	{
		for(int j1=0;j1<setofformula[j].numofformula;j1++)
		{
			int te=0;
			while(setofformula[j].formula[j1][te]!='\0')
			{
				//对每个规则表达式的字符进行判断
				//先判断是否是非终结符
				for(int j2=0;j2<numofset;j2++)
				{
					if(setofformula[j].formula[j1][te]==Nonend[j2])//说明是非终结符
					{
						isnonend=true;
						break;
					}
				}
				if(isnonend==true)
				{
					isnonend=false;
					te++;
					continue;
				}
				//在判断当前字符是否已经保存在终结符串里
				for(int j3=0;j3<numofendchar;j3++)
				{
					if(setofformula[j].formula[j1][te]==endchar[j3])
					{
						already=true;
						break;
					}
				}
				if(already==true)
				{
					already=false;
					te++;
					continue;
				}
				//当前字符为终结符，且不在终结符表里
				endchar[numofendchar]=setofformula[j].formula[j1][te];
				numofendchar++;
				te++;
			}
		}
	}
	endchar[numofendchar]='#';
	numofendchar++;
//***********************************************************************************//
//**********************************下面开始构建*************************************//
	//**********************************第三步***************************//
	ss[0]=State(setofformula);
	ss[0].newState();
	//**********************************第四步***************************//
	for(int ddd=0;ddd<numofstate;ddd++)
		ss[ddd].getAcc();
	for(int t=0;t<numofstate;t++)
	{
	 	ss[t].stateout();                      //将每个生成的状态在屏幕输出，这里-1，-2，-3，...代表式子的
	}										   //编号,0作为出错的情况，-255代表Accept 
	
	//*******************下面将结果写到TXT文件里，并在屏幕输出************************//
	cout<<"下面输出LR1分析表，包含action的终结符和GOTO的非终结符以及状态编号：           "<<endl;
	cout<<"    ";
	for(int a=0;a<numofendchar;a++)          //先输出非终结符
		cout<<endchar[a]<<"     ";
	for(int b=1;b<numofset;b++)              //，再输出终结符，不包括'$'
		cout<<Nonend[b]<<"     ";
	cout<<endl;

	//***************下面将结果写到analyseTable.txt，第一行和第一列为符号和状态编号，可省略************//
 /*	analyseTableOut<<"    ";                    //第一行无状态编号，预留空间
	for(int a1=0;a1<numofendchar;a1++)	
	{
		analyseTableOut<<endchar[a1];
	 	analyseTableOut<<"     ";
	}
	for(int b1=1;b1<numofset;b1++)
	{
		analyseTableOut<<Nonend[b1];
		analyseTableOut<<"     ";
	}
	analyseTableOut<<'\n';
*/
	//**********下面定义保存LR1分析表的INT数组***********//
	LR1list=new int*[numofstate];
	for(int n=0;n<numofstate;n++)                   //分配空间并初始化，0代表出错状态
	{
		LR1list[n]=new int[numofendchar+numofset-1];
		for(int m=0;m<numofendchar+numofset-1;m++)
			LR1list[n][m]=0;
	}
	for(int k=0;k<numofstate;k++)     //将每个状态的produce写到LR1list数组里
		ss[k].produceout();
	//*************下面在屏幕画出LR1分析表，并将其写到analyseTable.txt************//
	for(int k1=0;k1<numofstate;k1++)
	{
	    cout<<k1<<"  ";
		//不输出状态编号到analyseTable.txt
	//	analyseTableOut<<k1;
	//	analyseTableOut<<"  ";                  
		if(k1<10)	
		{
			cout<<" ";                           //输出到屏幕
			analyseTableOut<<" ";                //输出到txt文件
		}
		for(int k2=0;k2<numofendchar+numofset-1;k2++)
		{
			cout<<LR1list[k1][k2]<<" ";
			analyseTableOut<<LR1list[k1][k2];
			analyseTableOut<<" ";
			//*********使屏幕输出对齐********//
			if(LR1list[k1][k2]>-10&&LR1list[k1][k2]<0) 
			{
				cout<<"   ";
			//	analyseTableOut<<"   ";
			}
			if(LR1list[k1][k2]>=10)
			{
				cout<<"   ";
			//	analyseTableOut<<"   ";
			}
			if(LR1list[k1][k2]<=-10)
			{
				if(LR1list[k1][k2]!=-255)
				{
					cout<<"  ";
				//	analyseTableOut<<"  ";
				}
				else
				{
					cout<<" ";
				//	analyseTableOut<<" ";
				}
			}
			if(LR1list[k1][k2]>=0&&LR1list[k1][k2]<10)
			{
				cout<<"    ";
			//	analyseTableOut<<"   ";
			}
		}
		cout<<endl;
		analyseTableOut<<'\n';
	}
}