ivancompiler.cpp

编译原理课程设计词法分析源码及程序

	action[16][10].sr='r';action[16][10].state=13;
	action[17][3].sr='s';action[17][3].state=19;
	action[17][10].sr='s';action[17][10].state=18;
	action[18][17].sr='r';action[18][17].state=19;
	action[19][0].sr='s';action[19][0].state=14;
	action[19][13].sr='s';action[19][13].state=23;
	action[19][15].sr='s';action[19][15].state=27;
	action[20][3].sr='r';action[20][3].state=17;
	action[20][10].sr='r';action[20][10].state=17;
	action[21][3].sr='r';action[21][3].state=18;
	action[21][10].sr='r';action[21][10].state=18;
	action[22][3].sr='r';action[22][3].state=16;
	action[22][10].sr='r';action[22][10].state=16;
	action[23][0].sr='s';action[23][0].state=31;
	action[24][12].sr='s';action[24][12].state=34;
	action[24][14].sr='s';action[24][14].state=25;
	action[25][0].sr='s';action[25][0].state=14;
	action[26][3].sr='r';action[26][3].state=14;
	action[26][10].sr='r';action[26][10].state=14;
	action[27][0].sr='s';action[27][0].state=31;
	action[28][12].sr='s';action[28][12].state=34;
	action[28][16].sr='s';action[28][16].state=29;
	action[29][0].sr='s';action[29][0].state=14;
	action[30][3].sr='r';action[30][3].state=15;
	action[30][10].sr='r';action[30][10].state=15;
	action[31][7].sr='s';action[31][7].state=32;
	action[32][0].sr='s';action[32][0].state=33;
	action[33][12].sr='r';action[33][12].state=12;
	action[33][14].sr='r';action[33][14].state=12;
	action[33][16].sr='r';action[33][16].state=12;
	action[34][0].sr='s';action[34][0].state=31;
	action[35][12].sr='r';action[35][12].state=11;
	action[35][14].sr='r';action[35][14].state=11;
	action[35][16].sr='r';action[35][16].state=11;
	action[36][2].sr='r';action[36][2].state=10;
	action[36][3].sr='r';action[36][3].state=10;
	action[36][5].sr='r';action[36][5].state=10;
	action[36][6].sr='r';action[36][6].state=10;
	action[36][10].sr='r';action[36][10].state=10;
	action[37][2].sr='r';action[37][2].state=8;
	action[37][3].sr='r';action[37][3].state=8;
	action[37][5].sr='r';action[37][5].state=8;
	action[37][6].sr='r';action[37][6].state=8;
	action[37][10].sr='r';action[37][10].state=8;
	action[38][2].sr='r';action[38][2].state=6;
	action[38][3].sr='r';action[38][3].state=6;
	action[38][5].sr='s';action[38][5].state=39;
	action[38][6].sr='r';action[38][6].state=6;
	action[38][10].sr='r';action[38][10].state=6;
	action[39][0].sr='s';action[39][0].state=36;
	action[39][1].sr='s';action[39][1].state=41;
	action[40][2].sr='r';action[40][2].state=7;
	action[40][3].sr='r';action[40][3].state=7;
	action[40][5].sr='r';action[40][5].state=7;
	action[40][6].sr='r';action[40][6].state=7;
	action[40][10].sr='r';action[40][10].state=7;
	action[41][0].sr='s';action[41][0].state=36;
	action[41][1].sr='s';action[41][1].state=41;
	action[42][2].sr='s';action[42][2].state=45;
	action[42][6].sr='s';action[42][6].state=43;
	action[43][0].sr='s';action[43][0].state=36;
	action[43][1].sr='s';action[43][1].state=41;
	action[44][2].sr='r';action[44][2].state=5;
	action[44][3].sr='r';action[44][3].state=5;
	action[44][5].sr='s';action[44][5].state=39;
	action[44][6].sr='r';action[44][6].state=5;
	action[44][10].sr='r';action[44][10].state=5;
	action[45][2].sr='r';action[45][2].state=9;
	action[45][3].sr='r';action[45][3].state=9;
	action[45][5].sr='r';action[45][5].state=9;
	action[45][6].sr='r';action[45][6].state=9;
	action[45][10].sr='r';action[45][10].state=9;

	go_to[0][0]=1;go_to[4][1]=8;go_to[4][9]=9;go_to[10][1]=12;go_to[10][2]=11;go_to[13][7]=22;go_to[13][8]=21;go_to[13][10]=17;
	go_to[15][3]=16;go_to[15][4]=38;go_to[15][5]=37;go_to[19][7]=20;go_to[19][8]=20;go_to[23][6]=24;go_to[25][7]=26;go_to[27][6]=28;
	go_to[29][7]=30;go_to[34][6]=35;go_to[39][5]=40;go_to[41][3]=42;go_to[41][4]=38;go_to[41][5]=37;go_to[43][4]=44;go_to[43][5]=37;
	/****************************action表和go_to表赋初值完毕************************/
}
int ID1(int i)//按action表，给输入字符编号
{
	int j;
	j=-1;
	if(i==25) {j=0;id_num++;}//设置变量名称标志
	if(i==1) {j=8,id_left=id_num;}//设置产生试左边变量名称标志
	if(i==2) j=6;
	if(i==3) j=5;
	if(i==4) j=7;
	if(i==5) j=4;
	if(i==6) j=3;
	if(i==7) j=9;
	if(i==8) j=10;
	if(i==9) j=1;
	if(i==10) j=2;
	if(i==31) j=12;
	if(i==32) j=13;
	if(i==33) {j=14;id_then=L_four_tail->k+1;}//设置if语句中then位置标志
	if(i==35) {j=15;id_while=L_four_tail->k+1;}//设置while语句中while位置标志
	if(i==36) {j=16;id_do=L_four_tail->k+1;}//设置while语句中do位置标志
	if(i==37) j=11;
	return(j);
}
string ID10(int i)//反编号输入字符
{
	string ch;
	if(i==0) ch="id";
	if(i==1) ch="(";
	if(i==2) ch=")";
	if(i==3) ch=";";
	if(i==4) ch=":";
	if(i==5) ch="*";
	if(i==6) ch="+";
	if(i==7) ch=">";
	if(i==8) ch="=";
	if(i==9) ch="{";
	if(i==10) ch="}";
	if(i==11) ch="int";
	if(i==12) ch="and";
	if(i==13) ch="if";
	if(i==14) ch="then";
	if(i==15) ch="while";
	if(i==16) ch="do";
	if(i==17) ch="$";
	return(ch);
}
int ID2(char ch)//按go_to表给非终结符编号
{
	int j;
	j=-1;
	if(ch=='P') j=0;
	if(ch=='D') j=1;
	if(ch=='R') j=2;
	if(ch=='E') j=3;
	if(ch=='T') j=4;
	if(ch=='F') j=5;
	if(ch=='B') j=6;
	if(ch=='M') j=7;
	if(ch=='S') j=8;
	if(ch=='L') j=9;
	if(ch=='N') j=10;
	return(j);
}
int ID20(char ch)//给非终结符编号
{
	int j;
	j=-1;
	if(ch=='P') j=100;
	if(ch=='D') j=101;
	if(ch=='R') j=102;
	if(ch=='E') j=103;
	if(ch=='T') j=104;
	if(ch=='F') j=105;
	if(ch=='B') j=106;
	if(ch=='M') j=107;
	if(ch=='S') j=108;
	if(ch=='L') j=109;
	if(ch=='N') j=1010;
	return(j);
}
char ID21(int j)//反编号非终结符
{
	char ch;
	if(j==100 || j==0) ch='P';
	if(j==101 || j==1) ch='D';
	if(j==102 || j==2) ch='R';
	if(j==103 || j==3) ch='E';
	if(j==104 || j==4) ch='T';
	if(j==105 || j==5) ch='F';
	if(j==106 || j==6) ch='B';
	if(j==107 || j==7) ch='M';
	if(j==108 || j==8) ch='S';
	if(j==109 || j==9) ch='L';
	if(j==1010 || j==10) ch='N';
	return(ch);
}
void add(ike *temp)//加一个结点
{
	if(stack_head->next==stack_tail)
	{
		temp->pre=stack_head;
		temp->next=stack_tail;
		stack_head->next=temp;
		stack_tail->pre=temp;
	}
	else
	{
		temp->pre=stack_tail->pre;
		temp->next=stack_tail;
		stack_tail->pre->next=temp;
		stack_tail->pre=temp;
	}
}
void del()//删除一个结点
{
	stack_tail->pre->pre->next=stack_tail;
	stack_tail->pre=stack_tail->pre->pre;
}
int yufa_SLR1(int w)
{
	/*cout<<"当前输入符号："<<ID10(w)<<"   ";*/
	int i,flag=0,state_temp;//flag错误标志，0正常移进，1错误,2归约，3结束
	char sr_temp;
	sr_temp=action[stack_tail->pre->num][w].sr;//动作
	state_temp=action[stack_tail->pre->num][w].state;//状态变化
	if(sr_temp=='#')//错误动作
	{
		flag=1;
		err=3;
		cout<<"语法分析出错!"<<endl;
	}
	else if(sr_temp=='s')//移进动作
	{
		ike *temp;
		temp=new ike;
		temp->next=NULL;
		temp->pre=NULL;
		temp->word=w;
		temp->num=state_temp;
		add(temp);
		cout/*<<"动作（移进）："*/<<sr_temp<<state_temp<<"    "/*<<"状态转为："<<stack_tail->pre->num<<"  "<<"栈顶符号："<<ID10(stack_tail->pre->word)*/<<endl;
		flag=0;
	}
	else if(sr_temp=='r')//归约动作
	{
		int p=ID2(css[state_temp].left);
		int q=css[state_temp].len;
		for(i=0;i<q;i++)
			del();
		ike *temp;
		temp=new ike;
		temp->next=NULL;
		temp->pre=NULL;
		temp->word=ID20(css[state_temp].left);
		temp->num=go_to[stack_tail->pre->num][p];//查go_to表
		add(temp);
		cout/*<<"动作（归约）："*/<<sr_temp<<state_temp<<"  "<<css[state_temp].left<<"→"<<css[state_temp].right<<"    "/*<<"状态转为："<<stack_tail->pre->num<<"  "<<"栈顶符号："<<ID21(stack_tail->pre->word)*/<<endl;
		flag=2;
		yuyi_main(state_temp);//在产生树的同时进行语义分析
	}
	else if(sr_temp=='@')//结束动作
	{
		cout<<"END"/*<<"动作（归约）："<<sr_temp<<state_temp*/<<"  "<<css[state_temp].left<<"→"<<css[state_temp].right<<"    "/*<<"状态转为："<<stack_tail->pre->num<<"  "<<"栈顶符号："<<ID21(stack_tail->pre->word)*/<<endl;
		flag=3;
		cout<<"语法分析正确完成!"<<endl;
	}
	else//其他意外情况
	{
		flag=1;
		err=3;
		cout<<"语法分析出错!"<<endl;
	}
	return(flag);
}

/****************************以上是语法，以下是语义**************************/

void yuyi_main(int m)
{
	L *temp;
	int k;
	k=1;
	temp=new L;
	temp->op="  ";
	temp->op1="  ";
	temp->op2="  ";
	temp->result="";
	temp->next=NULL;
	temp->Ltrue=NULL;
	temp->Lfalse=NULL;
	if(m==4)//变量声明时加入符号表链
	{
		symb *Stemp;
		Stemp=new symb;
		id_name=id_numtoname(id_num);
		Stemp->word=id_name;
		Stemp->next=NULL;
		add_symb(Stemp);
	}
	if(m==5)//归约E→E+T
	{
		temp->op="+";
		temp->op1=E_name;
		temp->op2=T_name;
		yuyi_linshi++;//申请临时变量
		E_name="t"+newop(yuyi_linshi);
		temp->result=E_name;
		add_L_four(temp);//加一个四元式结点
	}
	if(m==6)//归约E→T
	{
		E_name=T_name;
	}
	if(m==7)//归约T→T*F
	{
		temp->op="*";
		temp->op1=T_name;
		temp->op2=F_name;
		yuyi_linshi++;//申请临时变量
		T_name="t"+newop(yuyi_linshi);
		temp->result=T_name;
		add_L_four(temp);//加一个四元式结点
	}
	if(m==8)//归约T→F
	{
		T_name=F_name;
	}
	if(m==9)//归约F→(E)
	{
		F_name=E_name;
	}
	if(m==10)//归约F→id
	{
		id_name=id_numtoname(id_num);
		F_name=id_name;
		k=lookup(id_name);//检查变量是否声明
		if(k==0)
		{
			err=2;
			errword=id_name;
			return;
		}
	}
	if(m==12)//归约B→id>id
	{
		temp->op="J>";
		id1_num=id_num-1;
		id1_name=id_numtoname(id1_num);
		k=lookup(id1_name);//检查变量是否声明
		if(k==0)
		{
			err=2;
			errword=id1_name;
			return;
		}
		id2_num=id_num;
		id2_name=id_numtoname(id2_num);
		k=lookup(id2_name);//检查变量是否声明
		if(k==0)
		{
			err=2;
			errword=id2_name;
			return;
		}
		temp->result="-1";
		temp->op1=id1_name;
		temp->op2=id2_name;
		add_L_four(temp);//加一个四元式结点
		add_L_true(temp);//加一个true链结点
		L *temp2;
		temp2=new L;
		temp2->op="J";
		temp2->op1="  ";
		temp2->op2="  ";
		temp2->result="-1";
		add_L_four(temp2);//加一个四元式结点
		add_L_false(temp2);//加一个false链结点
	}
	if(m==13)//归约M→id=E
	{
		temp->op="=";
		temp->op1=E_name;
		temp->op2="  ";
		id_name=id_numtoname(id_left);
		temp->result=id_name;
		add_L_four(temp);//加一个四元式结点
		yuyi_linshi=-1;//临时变量开始重新计数
	}
	if(m==14)//归约S→if B then M
	{
		int a;
		a=id_then;
		temp=L_true_head->Ltrue;
		while(temp!=NULL)
		{
			temp->result="L"+newop(a);
			a=temp->k;
			temp=temp->Ltrue;
		}
		a=L_four_tail->k+1;
		temp=L_false_head->Lfalse;
		while(temp!=NULL)
		{
			temp->result="L"+newop(a);
			temp=temp->Lfalse;
		}
		L_true_head->Ltrue=NULL;
		L_false_head->Lfalse=NULL;//回填并清空true链和false链
	}
	if(m==15)//归约S→while B do M
	{
		int a;
		a=id_do;
		temp=L_true_head->Ltrue;
		while(temp!=NULL)
		{
			temp->result="L"+newop(a);
			a=temp->k;
			temp=temp->Ltrue;
		}
		a=L_four_tail->k+2;
		temp=L_false_head->Lfalse;
		while(temp!=NULL)
		{
			temp->result="L"+newop(a);
			temp=temp->Lfalse;
		}
		L *temp1;
		temp1=new L;
		temp1->op="J";
		temp1->op1="  ";
		temp1->op2="  ";
		temp1->next=NULL;
		temp1->result="L"+newop(id_while);
		add_L_four(temp1);//加一个四元式结点
		L_true_head->Ltrue=NULL;
		L_false_head->Lfalse=NULL;//回填并清空true链和false链
	}
}
string newop(int m)//数字变成字符串
{
	int shang,yushu;
	string chuan,chuan1;
	shang=m;
	chuan="";
	while(1)
	{
		yushu=shang%10;
		chuan=chuan+char(48+yushu);
		shang=shang/10;
		if(shang==0)
			break;
	}
	int i;
	char *ch;
	ch=&chuan[0];
	chuan1="";
	for(i=strlen(ch)-1;i>=0;i--)
			chuan1=chuan1+chuan[i];
	return(chuan1);
}
void add_L_four(L *temp)//加一个四元式结点
{
	temp->k=L_four_tail->k+1;
	if(L_four_head->next == NULL)
	{
		L_four_head->next=temp;
		L_four_tail->next=temp;
	}
	else
	{
		L_four_tail->next->next=temp;
		L_four_tail->next=temp;
	}
	L_four_tail->k=L_four_tail->next->k;
}
void add_L_true(L *temp)//加一个true链结点
{
	temp->Ltrue=L_true_head->Ltrue;
	L_true_head->Ltrue=temp;

}
void add_L_false(L *temp)//加一个false链结点
{
	temp->Lfalse=L_false_head->Lfalse;
	L_false_head->Lfalse=temp;
}
void add_symb(symb *temp)//加一个语义符号表链结点
{
	if(symb_head->next == NULL)
	{
		temp->addr=0;
		symb_head->next=temp;
		symb_tail->next=temp;
	}
	else
	{
		temp->addr=symb_tail->next->addr+4;
		symb_tail->next->next=temp;
		symb_tail->next=temp;
	}
}
void output_yuyi()
{
	if(err==0)//语义分析正确时的输出
	{
		cout<<endl;
		system("pause");
		cout<<endl;
		cout<<"************************"<<endl;
		cout<<"*  第三部分：语义分析  *"<<endl;
		cout<<"************************"<<endl;
		cout<<"中间代码如下："<<endl;
		L *temp;
		temp=L_four_head->next;
		while(temp!=NULL)
		{
			cout<<"L"<<temp->k<<": （"<<temp->op<<",  "<<temp->op1<<",  "<<temp->op2<<",  "<<temp->result<<"）"<<endl;
			temp=temp->next;
		}
		cout<<"其他有用信息如下："<<endl;
		symb *Stemp;
		Stemp=symb_head->next;
		cout<<"name"<<"   type   "<<"   id   "<<"   identifer   "<<"addr"<<endl;
		while(Stemp!=NULL)
		{
			cout<<Stemp->word<<"     int     "<<"   25     "<<"     sv       "<<Stemp->addr<<endl;
			Stemp=Stemp->next;
		}
	}
	if(err==2)//语义分析错误时的输出
	{
		cout<<endl;
		system("pause");
		cout<<endl;
		cout<<"************************"<<endl;
		cout<<"*  第三部分：语义分析  *"<<endl;
		cout<<"************************"<<endl;
		cout<<"语义分析出错：变量"<<errword<<"未声明!"<<endl;
	}
}
string id_numtoname(int num)//根据编号找变量的名称
{
	str *temp;
	string name;
	temp=string_head->next;
	while(temp!=NULL)
	{
		if(num==temp->num)
		{
			name=temp->word;
			break;
		}
		temp=temp->next;
	}
	return(name);
}
int lookup(string m)//检查变量是否已经声明
{
	symb *temp;
	int i;
	i=0;
	temp=new symb;
	temp=symb_head->next;
	while(temp!=NULL)
	{
		if(m==temp->word)
		{
			i=1;
			break;
		}
		temp=temp->next;
	}
	return(i);
}