lranalyser.cpp

1.1 引言 1.1.1 设计目的 本次课程设计是在完成一个学期的编译原理课程之后

/******************************************************************************
*模块名:LR分析器
*
*功能:对程序可执行部分进行语法分析，并适时调用语义处理程序，生成四元式。
*       
*开始时间:2004.11.8       
*
*修改时间:2004.11.8,2004.11.9,2004.11.14,2004.11.15,2004.11.20
*     
*完成时间:2004.11.20
*
*作者: 胡彬      
*      
*       

*******************************************************************************/
#include "LRSemanticor.cpp"

//全局变量
stack<int> clusterSta;		//状态栈
stack<char*> signSta;		//符号栈

//PL数组：下标表示产生式编号（为与讲义协调，数组第一个元素不使用），内容表示此产生式右部长度。
int PL[43]={1,2,1,2,3,3,2,2,2,3,5,2,4,4,3,3,3,1,3,3,4,3,1,1,3,1,1,1,3,3,3,3,2,
			3,1,1,3,1,1,1,1,1,1};
//AL数组：第一列表示产生式编号（为与讲义协调，数组第一个元素不使用），第二列存放此产生式左部符号名称。
char AL[43][5]={{'P','L','\0'},{'L','\0'},{'L','\0'},{'L','S','\0'},{'S','\0'},{'S','\0'},
				{'S','\0'},{'S','\0'},{'S','\0'},{'S','\0'},{'S','\0'},{'S','\0'},
				{'S','\0'},{'S','\0'},{'C','\0'},{'T','p','\0'},{'W','d','\0'},
				{'W','\0'},{'F','3','\0'},{'F','2','\0'},{'F','1','\0'},
				{'P','A','R','T','\0'},{'P','A','R','T','\0'},{'T','T','\0'},
				{'I','\0'},{'I','\0'},{'I','D','\0'},{'E','X','P','\0'},{'E','\0'},
				{'E','\0'},{'E','\0'},{'E','\0'},{'E','\0'},{'E','\0'},{'E','\0'},
				{'E','\0'},{'L','E','\0'},{'R','O','P','\0'},{'R','O','P','\0'},
				{'R','O','P','\0'},{'R','O','P','\0'},{'R','O','P','\0'},{'R','O','P','\0'}};
//以下四个数组用于存放LR分析表
///////////////////////////////////////////////////////////////////////////////////////////////
//SL数组与SA数组配合，存放了ACTION表中内容：
//SL数组：下标表示状态号，内容为对应下标所表示的状态在SA数组中从第几行开始。
int SL[85]={0,9,12,21,22,23,24,33,35,44,53,62,64,66,68,70,75,80,81,83,85,87,90,91,96,97,99,100,
		    101,102,111,112,114,119,120,121,124,125,130,131,133,136,137,138,139,141,142,144,147,
			148,150,151,158,163,164,166,167,172,173,178,179,181,186,187,188,189,190,191,192,193,
			198,203,208,209,210,215,220,225,230,233,236,237,238,239,245};
//SA数组：第一列存放单词编码，第二列存放动作。
int SA[246][2]={{4,6},{6,15},{9,17},{11,20},{14,12},{15,13},{16,14},{17,7},{0,0},{5,999},{33,4},
				{0,0},{4,6},{6,15},{9,17},{11,20},{14,12},{15,13},{16,14},{17,7},{0,0},
				{-1,-2},{-1,-3},{-1,-1},{4,6},{6,15},{9,17},{11,20},{14,12},{15,13},{16,14},{17,7},{0,0},
				{23,23},{0,0},{4,6},{6,15},{9,17},{11,20},{14,12},{15,13},{16,14},{17,7},{0,0},
				{4,6},{6,15},{9,17},{11,20},{14,12},{15,13},{16,14},{17,7},{0,0},
				{4,6},{6,15},{9,17},{11,20},{14,12},{15,13},{16,14},{17,7},{0,0},
				{10,29},{0,0},{17,31},{0,0},{30,39},{0,0},{30,46},{0,0},
				{17,72},{18,73},{20,70},{30,71},{0,0},{17,72},{18,73},{20,70},{30,71},{0,0},
				{-1,-17},{13,56},{0,0},{12,58},{0,0},{17,60},{0,0},{5,22},{33,4},{0,0},
				{-1,-4},{17,72},{18,73},{20,70},{30,71},{0,0},{-1,-5},{8,26},{-1,-6},{-1,-15},{-1,-7},
				{-1,-8},{4,6},{6,15},{9,17},{11,20},{14,12},{15,13},{16,14},{17,7},{0,0},
				{-1,-9},{30,32},{-1,-11},{17,72},{18,73},{20,70},{30,71},{0,0},{-1,-22},
				{-1,-23},{31,36},{32,37},{0,0},{-1,-10},{17,72},{18,73},{20,70},{30,71},{0,0},
				{-1,-21},{17,42},{0,0},{31,43},{32,44},{0,0},{-1,-25},{-1,-26},{-1,-12},{17,42},
				{0,0},{-1,-24},{17,42},{0,0},{31,48},{32,44},{0,0},{-1,-13},{7,50},{0,0},
				{-1,-14},{24,63},{25,64},{26,65},{27,66},{28,67},{29,68},{0,0},{17,72},{18,73},{20,70},{30,71},{0,0},
				{-1,-36},{10,55},{0,0},{-1,-16},{17,72},{18,73},{20,70},{30,71},{0,0},
				{-1,-18},{17,72},{18,73},{20,70},{30,71},{0,0},{-1,-19},{23,61},{0,0},
				{17,72},{18,73},{20,70},{30,71},{0,0},{-1,-20},{-1,-37},{-1,-38},{-1,-39},
				{-1,-40},{-1,-41},{-1,-42},{19,74},{20,75},{21,76},{22,77},{-1,-27},
				{17,72},{18,73},{20,70},{30,71},{0,0},{17,72},{18,73},{20,70},{30,71},{0,0},
				{-1,-34},{-1,-35},{17,72},{18,73},{20,70},{30,71},{0,0},{17,72},{18,73},{20,70},{30,71},{0,0},
				{17,72},{18,73},{20,70},{30,71},{0,0},{17,72},{18,73},{20,70},{30,71},{0,0},
				{21,76},{22,77},{-1,-28},{21,76},{22,77},{-1,-29},{-1,-30},{-1,-31},{-1,-32},
				{19,74},{20,75},{21,76},{22,77},{31,84},{0,0},{-1,-33}};
///////////////////////////////////////////////////////////////////////////////////////////////
//NL数组与GL数组配合，存放GOTO表中内容：
//NL数组：下标表示产生式编号（为与讲义协调，数组第一个元素不使用），内容表示此产生式左部非终结符
//		  在GOTO表中从GL数组的第几行开始。
int NL[43]={-1,0,0,2,3,3,3,3,3,3,3,3,3,3,9,10,11,12,13,14,15,16,16,17,19,19,21,23,31,31,31,
			31,31,31,31,31,38,40,40,40,40,40,40};
//GL数组：第一列存放原状态，第二列存放下一状态。
int GL[41][2]={{0,1},{-1,21},{-1,2},{2,5},{8,25},{9,27},{10,28},{29,30},{-1,3},{-1,8},{-1,9},
				{-1,10},{-1,16},{-1,11},{-1,18},{-1,19},{-1,35},{32,33},{-1,38},{39,40},{-1,47},
				{44,45},{-1,41},{23,24},{32,34},{37,34},{52,53},{56,57},{58,59},{61,62},{-1,51},
				{70,82},{71,83},{74,78},{75,79},{76,80},{77,81},{-1,69},{15,49},{-1,54},{-1,52}};
///////////////////////////////////////////////////////////////////////////////////////////////
//此函数完成查GOTO表的功能
//参数：产生式编号
//返回值：查到返回true，否则返回false
bool checkGoto(int productor)
{
	int cluster;
	int start;
	char *temp;
	temp=(char*)malloc((strlen(AL[productor])+1)*sizeof(char));
	strcpy(temp,AL[productor]);
	signSta.push(temp);
	cluster=clusterSta.top();				//取当前状态
	start=NL[productor];
	do										//查找相应状态
	{
		if(GL[start][0]==cluster||GL[start][0]==-1) break;	
		start++;
	}while(start<41);
	if(start==41)
	{
		isTrue=false;
		return false;
	}
	clusterSta.push(GL[start][1]);
	if(isTrue==true) 
	LRSemanticor(productor);
	return true;
}
///////////////////////////////////////////////////////////////////////////////////////////////
//此函数完成查ACTION表的功能
//参数：无
//返回值：未查到返回0，查到而未结束返回1，结束返回2
int checkAction()
{
	int cluster;
	int start;
	int act;
	int plen;
	int i;
	char *temp;
	cluster=clusterSta.top();				//取当前状态
	while(WORD.index==0||WORD.index==35)	//去掉换行符
	{
		if(WORD.index==35) linenum++;
		getWord();			
	}
	start=SL[cluster];						//取查SA数组的起始行
	do										//查找相应单词（编码）
	{
		if(SA[start][0]==WORD.index||SA[start][0]==-1) break;	
		start++;
	}while(SA[start][0]!=0);
	if(SA[start][0]==0)
	{
		isTrue=false;
		return 0;							//出错
	}
	act=SA[start][1];						//取相应动作
	if(act==999)
	{
		while(signSta.size()!=0)
		{
			signSta.pop();					//清空符号栈
		}
		while(clusterSta.size()!=0)
		{
			clusterSta.pop();				//清空状态栈
		}
		return 2;							//LR分析结束
	}
	if(act>0)								//移进操作
	{
		temp=(char*)malloc((strlen(WORD.value)+1)*sizeof(char));
		strcpy(temp,WORD.value);
		clusterSta.push(act);
		WORD.index=0;						//清空WORD，准备再次读入
		signSta.push(temp);
		return 1;
	}
	if(act<0)								//归约操作
	{
		act=-act;							//取正数：产生式编号
		plen=PL[act];						//取产生式右部长度
		for(i=0;i<plen;i++)
		{
			clusterSta.pop();
			temp=signSta.top();
			signSta.pop();
			signCache[i]=temp;				//保留规约式
		}
		if(checkGoto(act)==false)
		{
			isTrue=false;
			return 0;
		}
		return 1;
	}
	isTrue=false;
	return 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////
//此函数初始化全局变量
//参数：无
//返回值：无
void initialize()
{
	int i;	
	clusterSta.push(0);						//状态0入栈
	for(i=0;i<5;i++)
		signCache[i]=NULL;
}
///////////////////////////////////////////////////////////////////////////////////////////////
//此函数显示状态栈的内容（用于调试）
//参数：无
//返回值：无
void showclusterStack()
{
	int k;
	FILE *fp;
	stack<int> temp;
	fp=fopen("showclusterStack.txt","a");
	while(clusterSta.size()!=0)
	{
		k=clusterSta.top();
		temp.push(k);
		clusterSta.pop();
	}
	while(temp.size()!=0)
	{
		k=temp.top();
		clusterSta.push(k);
		fprintf(fp,"%d ",k);
		temp.pop();
	}
	fprintf(fp,"\n");
	fclose(fp);
}
///////////////////////////////////////////////////////////////////////////////////////////////
//此函数显示符号栈的内容（用于调试）
//参数：无
//返回值：无
void showsignStack()
{
	char *k;
	FILE *fp;
	stack<char*> temp;
	fp=fopen("showsignStack.txt","a");
	while(signSta.size()!=0)
	{
		k=signSta.top();
		temp.push(k);
		signSta.pop();
	}
	while(temp.size()!=0)
	{
		k=temp.top();
		signSta.push(k);
		fprintf(fp,"%s ",k);
		temp.pop();
	}
	fprintf(fp,"\n");
	fclose(fp);
}
///////////////////////////////////////////////////////////////////////////////////////////////
//此函数完成LR分析中的出错处理
//参数：无
//返回值：无
void errorDeal()
{
	int back;
	char *temp;
	printf("Error!行数：%d，字符：%s\n",linenum,WORD.value);
	getWord();
	while(WORD.index!=0)	//去掉换行符
	{
		if(WORD.index==35) linenum++;
		if(WORD.index==4||WORD.index==5||WORD.index==17||WORD.index==14||WORD.index==15||WORD.index==16||WORD.index==6||WORD.index==9||WORD.index==11)
			break;
		getWord();			
	}
	back=clusterSta.top();
	if(WORD.index==5)					//如果是“end”前的最后一条语句出错，则不跳到下一条语句
	{
		while(back!=21&&back!=2)		//回退到可以接受“end”的地方
			{
				clusterSta.pop();
				temp=signSta.top();
				signSta.pop();
				free(temp);
				back=clusterSta.top();
			}
		if(back==2)						//更改栈顶状态，以便可以接受“end”，顺利完成后续的翻译。
		{
			temp=signSta.top();
			signSta.pop();
			free(temp);
			temp=(char*)malloc(2*sizeof(char));
			strcpy(temp,"L");
			signSta.push(temp);
			clusterSta.pop();
			clusterSta.push(21);
		}
	}
	else		//如果不是“end”前的最后一条语句出错，则跳到下一条语句继续执行。
	{
		while(back!=0&&back!=2&&back!=6&&back!=8&&back!=9&&back!=10&&back!=29)
			{
				clusterSta.pop();
				temp=signSta.top();
				signSta.pop();
				free(temp);
				back=clusterSta.top();
			}
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////
//此函数为LR总控程序
//参数：无
//返回值：无
void LRAnalyser()
{
	int i=0;
	initialize();
	while(i!=2)
	{
		showclusterStack();
		showsignStack();
		i=checkAction();
		if(i==0) errorDeal();
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////
//mini_pascal总控程序
//参数：无
//返回值：无
main()
{
	WordAnalyser();
	init();
	getWord();
	recurPROG();
	OUTQ();
	printVTable();
	printPTable();
	return 0;
}