语法分析器.cpp

语法分析器 输入一段程序后

		temp1=temp1->next;
	}
	cout<<"常数表内容如下："<<endl;
	number *temp2;
	temp2=new number;
	temp2=number_head->next;
	while(temp2!=NULL)
	{
		cout<<temp2->num<<"   "<<temp2->value<<endl;
		temp2=temp2->next;
	}
	cout<<"符号表内容如下："<<endl;
	str *temp3;
	temp3=new str;
	temp3=string_head->next;
	while(temp3!=NULL)
	{
		cout<<temp3->num<<"   "<<temp3->word<<endl;
		temp3=temp3->next;
	}
}
void outfile()
{
	ofstream fout1("token.txt");//写文件
	ofstream fout2("number.txt");
	ofstream fout3("string.txt");
	token *temp1;
	temp1=new token;
	temp1=token_head->next;
	while(temp1!=NULL)
	{
		fout1<<temp1->code;
		if(temp1->num == -1)
			fout1<<endl;
		else
			fout1<<"   "<<temp1->num<<endl;
		temp1=temp1->next;
	}
	number *temp2;
	temp2=new number;
	temp2=number_head->next;
	while(temp2!=NULL)
	{
		fout2<<temp2->num<<"   "<<temp2->value<<endl;
		temp2=temp2->next;
	}
	str *temp3;
	temp3=new str;
	temp3=string_head->next;
	while(temp3!=NULL)
	{
		fout3<<temp3->num<<"   "<<temp3->word<<endl;
		temp3=temp3->next;
	}
}

/****************************以上是词法，以下是语法**************************/
void yufa_initialize()
{
	
	stack_head=new ike;
	stack_tail=new ike;
	stack_head->pre=NULL;
	stack_head->next=stack_tail;
	stack_head->num=0;
	stack_head->word='!';
	stack_tail->pre=stack_head;
	stack_tail->next=NULL;//初始化栈分析链表
	css[0].left='Q';
	css[0].right="P";
	css[1].left='P';
	css[1].right="id()L;R";
	css[2].left='L';
	css[2].right="L;D";
	css[3].left='L';
	css[3].right="D";
	css[4].left='D';
	css[4].right="id:int";
	css[5].left='E';
	css[5].right="E+T";
	css[6].left='E';
	css[6].right="T";
	css[7].left='T';
	css[7].right="T*F";
	css[8].left='T';
	css[8].right="F";
	css[9].left='F';
	css[9].right="(E)";
	css[10].left='F';
	css[10].right="id";
	css[11].left='B';
	css[11].right="B and B";
	css[12].left='B';
	css[12].right="id>id";
	css[13].left='M';
	css[13].right="id=E";
	css[14].left='S';
	css[14].right="if B then M";
	css[15].left='S';
	css[15].right="while B do M";
	css[16].left='S';
	css[16].right="M";
	css[17].left='N';
	css[17].right="N;S";
	css[18].left='N';
	css[18].right="S";
	css[19].left='R';
	css[19].right="{N}";
	int i,j;
	for(i=0;i<20;i++)
	{
		char *css_len;
		css_len=&css[i].right[0];
		css[i].len=strlen(css_len);
	}
	css[1].len=6;
	css[4].len=3;
	css[10].len=1;
	css[11].len=3;
	css[12].len=3;
	css[13].len=3;
	css[14].len=4;
	css[15].len=4;//初始化产生式
	for(i=0;i<46;i++)
	{
		for(j=0;j<18;j++)
			action[i][j].sr='#';
	}//初始化action表
	for(i=0;i<46;i++)
	{
		for(j=0;j<11;j++)
			go_to[i][j]=-1;
	}//初始化go_to表
	/****************************以下是给action表和go_to表赋初值************************/
	action[0][0].sr='s';action[0][0].state=2;
	action[1][17].sr='@';//结束
	action[2][1].sr='s';action[2][1].state=3;
	action[3][2].sr='s';action[3][2].state=4;
	action[4][0].sr='s';action[4][0].state=5;
	action[5][4].sr='s';action[5][4].state=6;
	action[6][11].sr='s';action[6][11].state=7;
	action[7][3].sr='r';action[7][3].state=4;
	action[8][3].sr='r';action[8][3].state=3;
	action[9][3].sr='s';action[9][3].state=10;
	action[10][0].sr='s';action[10][0].state=5;
	action[10][9].sr='s';action[10][9].state=13;
	action[11][17].sr='r';action[11][17].state=1;
	action[12][3].sr='r';action[12][3].state=2;
	action[13][0].sr='s';action[13][0].state=14;
	action[13][13].sr='s';action[13][13].state=23;
	action[13][15].sr='s';action[13][15].state=27;
	action[14][8].sr='s';action[14][8].state=15;
	action[15][0].sr='s';action[15][0].state=36;
	action[15][1].sr='s';action[15][1].state=41;
	action[16][6].sr='s';action[16][6].state=43;
	action[16][3].sr='r';action[16][3].state=13;
	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 || i==26) j=0;
	if(i==1) j=8;
	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;
	if(i==35) j=15;
	if(i==36) j=16;
	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_main(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;
		cout<<endl<<"语法分析出错!"<<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<<"    ";
		cout<<"状态转为："<<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<<"    ";
		cout<<"状态转为："<<stack_tail->pre->num<<"  "<<"栈顶符号："<<ID21(stack_tail->pre->word)<<endl;
		flag=2;
	}
	else if(sr_temp=='@')//结束动作
	{
		cout<<"动作（归约）："<<sr_temp<<state_temp<<"  "<<css[state_temp].left<<"→"<<css[state_temp].right<<"    ";
		cout<<"状态转为："<<stack_tail->pre->num<<"  "<<"栈顶符号："<<ID21(stack_tail->pre->word)<<endl;
		flag=3;
		cout<<endl<<"语法分析正确完成!"<<endl;
	}
	else//其他意外情况
	{
		flag=1;
		cout<<endl<<"语法分析出错!"<<endl;
	}
	return(flag);
}