复件 cpp1.cpp

用SLR分析法实现的语法分析

#include <fstream.h>
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#define M 20
#define N 20
#define O 10
#define syn_size 7
#define max_id	256		//标识符最大长度；
#define stack_size	90	//栈的大小；
#define max_in  90    //输入存放数组的大小；
struct token{
char id;
char val[max_id];
};		//符号表表项的结构体定义;
struct item
{ 	char p[M][O];	//二位数组用来存放产生式；
	int num;		//标记产生式的数量；
}group[N];
int count;
char *syntax[]={"S.E","E.E+T","E.T","T.T*F","T.F","F.(E)","F.i"};
//指针数组用来存放文法产生式
char *syntax1[]={"S→E","E→E+T","E→T","T→T*F","T→F","F→(E)","F→i"};
char *follow[]={"$","+)$","+)*$","+)*$"};
//指针数组用来存放产生中的FOLLOW集； 
char terminal[]={"i+*()$"};
//终结符列表；
char unterminal[]={"SETF"};
//非终结符列表； 
/*
0.S→E
1.E→E|T
2.E→T
3.T→T&F
4.T→F
5.F→!F
6.F→(E)
7.F→iCi
8.F→i
9.C→>		
10.C→>=		y	
11.C→<
12.C→<=		x
13.C→==		z
14.C→!=		w
*/
int action[N][6];
int mygoto1[N][4];
int mygoto2[N][10];
int ifterminal(char c)
{	int i;
	int a=strlen(unterminal);
	for(i=0;i<a;i++)
		if(unterminal[i]==c) return 0;
	a=strlen(terminal);
	for(i=0;i<a;i++)
		if(terminal[i]==c)	return 1;
	return -1;
}
int ifbelong1(struct item a,char *b)
//数组b是否属于结构体a，是则返回1，否则返回0；
{	
	for(int i=0;i<a.num;i++)
	{	if(strcmp(a.p[i],b)==0)
			return 1;
	}
	return 0;
}
struct item Closure(struct item a)
/*
function Closure(I)
begin
	j:=I;
	repeat
		for J 的每个项目A→α·Bβ和G的每个产生式B→·γ,若
		B→γ不在J中do 
			把B→·γ加入J；
	return J
end
*/
{	int i;
	char temp[10];
	for(i=0;i<a.num;i++)
	{	strcpy(temp,a.p[i]);
		for(int j=0;j<strlen(temp);j++)
			if(temp[j]=='.')	break;
		j++;
		if(!ifterminal(temp[j]))
		{	for(int k=0;k<syn_size;k++)
			{	if(syntax[k][0]==temp[j]&&ifbelong1(a,syntax[k])==0)
				{	strcpy(a.p[a.num],syntax[k]);
					a.num++;
				}
			}
		}
	}
	return a;
}

struct item Goto(struct item a,char b)
{	
	struct item gtemp={{"\0"},0};
	for(int i=0;i<a.num;i++)
	{	char temp[10];
		strcpy(temp,a.p[i]);
		for(int j=0;j<strlen(temp);j++)
			if(temp[j]=='.')	break;
		j++;
		if(temp[j]==b)
		{	temp[j-1]=temp[j];
			temp[j]='.';
			strcpy(gtemp.p[gtemp.num],temp);
			gtemp.num++;
			gtemp=Closure(gtemp);
		}
	}
	return gtemp;
}
int ifbelong2(struct item a,struct item b[])
//判断结构体a中指针数组的第一个字符串是否包含于结构体数组b，是则返回1，否则返回0；
{	int flag=0;
	for(int k=0;k<count;k++)
		for(int j=0;j<b[k].num;j++)
			{	if(strcmp(a.p[0],b[k].p[j])==0)	flag=1;
			}
	
	return flag;
}
int link(char c)
{	int i;
	int a=strlen(terminal);
	for(i=0;i<a;i++)
		if(terminal[i]==c)	return i;
	int b=strlen(unterminal);
	for(i=0;i<b;i++)
		if(unterminal[i]==c)	return i;
	return -1;
}
void myCollection(void)
/*
I0=Closure({S'->S});
C={I0};
for(i=0,j=0;i<=j;i++)
	for(k=0;k<strlen(所有的文法符号);i++)
		if(GO(Ii,Xk)!={}&&GO(Ii,Xk)不真包含于C)
		{	j++;Ij=GO(Ii,Xk);C=C并Ij;
		}
*/
{	struct item a;
	a.num=0;
	strcpy(a.p[0],syntax[0]);
	a.num++;
	group[0]=Closure(a);
	count=1;
	int i,j;
//	int m2;
	for(i=0,j=0;i<=j;i++)
	{	for(int k=0;k<strlen(unterminal);k++)
		{	a=Goto(group[i],unterminal[k]);
		//	if(a.num!=0)
		//	{	m2=link(unterminal[k])+strlen(terminal);
		//		mygoto2[i][m2]=j+1;
		//	}
			if(a.num!=0&&ifbelong2(a,group)==0)
			{	j++;
				group[j]=a;
			//	m2=link(unterminal[k])+strlen(terminal);
			//	mygoto2[i][m2]=j+1;
				count++;
			}
		}
		for(k=0;k<strlen(terminal);k++)
		{	a=Goto(group[i],terminal[k]);
			//if(a.num!=0)
			//{	m2=link(unterminal[k])+strlen(terminal);
		//		mygoto2[i][m2]=j+1;
		//	}
			if(a.num!=0&&ifbelong2(a,group)==0)
			{	j++;
				group[j]=a;
		//		m2=link(terminal[k]);
		//		mygoto2[i][m2]=j+1;
				count++;
			}
		}
		
	}
}
int ifequal(struct item a,struct item b[])
//返回值为a在b中的编号j;
{	for(int i=0;i<count;i++)
	{	if(a.num!=b[i].num)
			continue;
		else
		{	for(int j=0;j<a.num;j++)
			{	if(strcmp(a.p[j],b[i].p[j])!=0)
					break;
			}
			if(j==a.num)	return i+1;
		}
	}
	return -1;
	
}

int iffollow(struct item a,char c)
//判断字符A开头且以.结尾的产生式是否位于Ii中，若在，返回值为产生式A->????的编号；
{	for(int i=0;i<a.num;i++)
	{	char temp1[10];
		strcpy(temp1,a.p[i]);
		int b=strlen(temp1);
		if(temp1[b-1]=='.'&&temp1[0]==c)	
		{	for(int j=0;j<syn_size;j++)
			{	char temp2[10];
				strcpy(temp2,syntax[j]);
				for(int k=1;k<strlen(temp2);k++)
				{	temp2[k]=temp2[k+1];
				}
				temp2[k-1]='.';
				if(strcmp(temp1,temp2)==0)	return j;	
			}
		
		}
	}
	return -1;
}
void myCreate(void)
/*
0表示出错；
99表示接受；
2表示移进1；
-2表示规约1；
*/
{	myCollection();
	for(int i=0;i<count;i++)
	{	int b,c;
	//	int m2;
		struct item a;
		for(int j=0;j<strlen(terminal);j++)
		{	
			a=Goto(group[i],terminal[j]);
			b=ifequal(a,group);
			if(b!=-1)
			{	c=link(terminal[j]);
				action[i][c]=b;
			}
		/*	m2=link(terminal[j]);
			if(mygoto2[i][m2]!=0)
			{
				action[i][m2]=mygoto2[i][m2];	//移进j;
				}
				*/
		}	
		
		for(j=0;j<strlen(unterminal);j++)
		{	a=Goto(group[i],unterminal[j]);
			b=ifequal(a,group);
			if(b!=-1)
			{	c=link(unterminal[j]);
				mygoto1[i][c]=b;
			}
		//	m2=link(unterminal[j])+strlen(terminal);
		/*	if(mygoto2[i][m2]!=0)
			{	c=link(unterminal[j]);
				mygoto1[i][c]=mygoto2[i][m2];
			}
			*/
			b=iffollow(group[i],unterminal[j]);
			if(b!=-1)
			{	if(b==0)
				{	c=link('$');
					action[i][c]=99;	//接受；
				}
				else
				{	for(int k=0;k<strlen(follow[j]);k++)
					{	c=link(follow[j][k]);
						action[i][c]=-(b+1);	//按第b个产生式规约；
					}
				}
			}
		}
	}
}
void main()
{	
	myCreate();
	for(int k=0;k<count;k++)
	{	for(int l=0;l<6;l++)
			 cout<<action[k][l]<<"  ";
		for(l=0;l<4;l++)
			cout<<mygoto1[k][l]<<"  ";
		cout<<endl;
	}
	token temp[max_in];
	char filename[40];
	cout<<"请输入语法分析源文件的文件名及路径：";
	cin>>filename;
	ifstream infile(filename,ios::in);
	cout<<"请输入语法分析过程描述文件的文件名及路径：";
	cin>>filename;
	ofstream outfile(filename,ios::out);
//	infile>>temp.id>>temp.val;
	char stack[stack_size]={'$'};
	int  state[stack_size]={0};
	int  top_ptr=0;
	char inbuff[max_in]={'\0'};
	int in_ptr=0;
	outfile<<"栈"<<'\t'<<'\t'<<'\t'<<"输入"<<'\t'<<'\t'<<'\t'<<"动作"<<endl;
	int i=0;
	
	do{	infile>>temp[i].id>>temp[i].val;
		if(temp[i].id=='#') break;
		inbuff[i]=temp[i].id;
		i++;
	}while(1);
	inbuff[i]='$';
	outfile<<stack<<'\t'<<'\t'<<'\t'<<inbuff<<'\t'<<'\t'<<'\t'<<endl;
	cout<<inbuff<<endl;
	while(1)
	{	int m,n;
		m=state[top_ptr];
		n=link(inbuff[in_ptr]);
		if(n==-1)
		{	cout<<"出错！输入字符"<<inbuff[in_ptr]<<"为非法字符！"<<endl;
			break;
		}
		if(action[m][n]>0&&action[m][n]<99)
			//移进
		{	top_ptr++;
			state[top_ptr]=action[m][n]-1;
			stack[top_ptr]=inbuff[in_ptr];
			inbuff[in_ptr]=' ';
			in_ptr++;
			outfile<<stack<<'\t'<<'\t'<<'\t'<<inbuff<<'\t'<<'\t'<<'\t'<<"移进"<<endl;
		}
		else if(action[m][n]<0)
		{	int a=-action[m][n]-1;
			int b=strlen(syntax[a])-2;
			top_ptr=top_ptr-b;
			int c=state[top_ptr];
			top_ptr++;
			b=link(syntax[a][0]);
			state[top_ptr]=mygoto1[c][b]-1;
			state[top_ptr+1]=0;
			stack[top_ptr]=syntax[a][0];
			stack[top_ptr+1]='\0';
			outfile<<stack<<'\t'<<'\t'<<'\t'<<inbuff<<'\t'<<'\t'<<'\t'<<"用"<<syntax1[a]<<"归约"<<endl;
		}
		else if(action[m][n]==99)
		{	
			break;
		}
		else	
		{	cout<<"出错！SLR分析表表项为0！"<<endl;
			break;
		}
	}
}