slr.cpp

slr语义分析器

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<ctype.h>
#include<fstream>

using namespace std;
using std::string;

//符号表的数据结构
struct	entrytype
{
	int		address;
	string	idname;
	string	type;
};
struct entrytype ENTRY[100];

struct digittype
{
	int value;
	int entry;
	string type;
};
struct digittype digit[100];


//token表的数据结构
struct tokentype
{
	int id;
	int entry;
};
struct tokentype token[100];

//产生式的存储结构
struct generatype
{
	char    str[100];
	int     length;
	int     left;
};
struct generatype generate[38];

//堆栈的数据结构
struct stacktype
{
	int content[200];
	int top;
};
struct stacktype STACK;

//非终结符的数据结构
struct utype
{
	struct stacktype nextlist[100];
	int	   Top;
	int    Head;
};
struct idtype
{	
	int	address;
	string name;
	string type;
};
struct quadtype
{
	string op;
	string first;
	string second;
	string third;
};
struct etype
{
	string x[100];
	int	top;
};

struct utype U;

struct idtype Id;

struct etype E;

struct quadtype quad[100];
struct stacktype L_nextlist,S_nextlist,C_nextlist,N_falselist,F_nextlist,D_list;
struct stacktype P_truelist,B_truelist,B_falselist,B1_truelist,B1_falselist,B2_truelist,B2_falselist;
int	M_quad,W_head;
int nextquad,temp,varicount;
string T_type, relop_op,relop_id,B_place,const_val;
struct stacktype idstack,conststack;

int  ACTION[69][32];		//action表
int  GOTO[69][17];			//goto表
char vn[18];				//非终结符
int  last;					//token表长度
int entry_lenth;
int lastdigit;

void init()
{
	FILE *fp1,*fp2,*fp3,*fp4,*fvn;
	int i=0,j;
	
	//读入action表
	fp1=fopen("action.txt","r");
	while(!feof(fp1))
	{
		for(i=0;i<69;i++)
		{
			for(j=1;j<=31;j++)
			{
				fscanf(fp1,"%d",&ACTION[i][j]);
			}
		}
	}

	//读入goto表
	fp2=fopen("goto.txt","r");
	while(!feof(fp2))
	{
		for(i=0;i<69;i++)
		{
			for(j=1;j<=16;j++)
			{
				fscanf(fp2,"%d",&GOTO[i][j]);
			}
		}
	}

	//读入生成式表
	fp3=fopen("production.txt","r");
	while(!feof(fp3))
	{
		for(i=1;i<=37;i++)
		{
			fscanf(fp3,"%d%d%s",&generate[i].left,&generate[i].length,&generate[i].str);			
		}
	} 

	last=0;
	//读入token表
	fp4=fopen("ftok.txt","r");
	while(!feof(fp4))
	{
		fscanf(fp4,"%d%d",&token[last].id,&token[last].entry);
		last++;
	}
	token[last-1].id=31;

	//读入非终结符
	fvn=fopen("Vn.txt","r");
	while(!feof(fvn))
	{
		for(i=1;i<=16;i++)
			fscanf(fvn,"%c",&vn[i]);
	}

	ifstream  ffu;
	ffu.open("fuhao.txt");
	entry_lenth=0;
	do{	
		entry_lenth++;
		ffu>>ENTRY[entry_lenth].idname;
		ffu>>ENTRY[entry_lenth].address;		
	}while(ENTRY[entry_lenth].address!=0);
	ffu.close();
	entry_lenth--;

	ifstream  fdigit;
	lastdigit=0;
	fdigit.open("digit.txt");
	do
	{
	    fdigit>>digit[lastdigit].entry>>digit[lastdigit].value>>digit[lastdigit].type;	
		lastdigit++;
	}while(digit[lastdigit-1
		].type=="const");
	fdigit.close();
	lastdigit--;

	STACK.top=0;
	STACK.content[STACK.top]=0;

	varicount=1;
	nextquad=0;
	L_nextlist.top=0;
	S_nextlist.top=0;
	C_nextlist.top=0;
	N_falselist.top=0;
	F_nextlist.top=0;
	D_list.top=0;

	P_truelist.top=0;
	U.Head=0;
	U.Top=0;
	E.top=0;
	for(i=0;i<100;i++)
	{
		U.nextlist[i].top=1;
	}
	B_falselist.top=0;
	B_truelist.top=0;

	idstack.top=0;
	conststack.top=0;

	fclose(fp1);
	fclose(fp2);
	fclose(fp3);
	fclose(fp4);
	fclose(fvn);
	return;
}

//查action表
int checkact(int a,int b)		//a为栈顶,b为当前输入符
{
	return ACTION[a][b];
}

//查goto表
int checkgoto(int a,int b)		//a为当前状态,b为栈顶
{
	return GOTO[a][b];
}

//栈的操作
void push(struct stacktype &s,int a)
{
	s.top++;
	s.content[s.top]=a;
	return;
}

void pop(struct stacktype &s)
{
	s.content[s.top]=0;
	s.top--;
	return;
}

int empty(struct stacktype s)
{
	if(s.top==0)
		return 1;
	else
		return 0;
}


void copy(struct stacktype &s1,struct stacktype &s2)
{
	int	count=0;

	if(s2.top==0)
		s1.top=0;
	else
	{
	count=s2.top;
	do
	{
		s1.content[count]=s2.content[count];
		count--;
	}while(count!=0);

	s1.top=s2.top;
	}
}

string  convert(int c,string s)
{
	struct stacktype a;
	char	ch;
	a.top=0;
	do
	{
		push(a,c%10);
		c=c/10;
	}while(c!=0);

	do
	{
		ch=a.content[a.top]+48;
		s=s+ch;
		pop(a);
	}while(!empty(a));

	return s;
}
void merge(struct stacktype &s1,struct stacktype &s2)
{	
	int i=1;

	while(i<=s1.top)
	{
		s2.content[i+s2.top]=s1.content[i];
		s1.content[i]=0;
		i++;
	}
	s2.top=s1.top+s2.top;
}

void backpatch(struct stacktype &s,int i)
{
	string a;

	a=convert(i,a);
  
	while(s.top>0 && s.content[s.top]!=0)
	{
		quad[s.content[s.top]].third=a;
		s.top--;
	}
}

void emit(string s1,string s2,string s3,string s4)
{
	quad[nextquad].op=s1;
	quad[nextquad].first=s2;
	quad[nextquad].second=s3;
	quad[nextquad].third=s4;
	nextquad++;
	cout<<s1<<","<<s2<<","<<s3<<","<<s4<<endl;
}

void  makelist(struct stacktype &s,int temp)
{
	s.top=1;
	s.content[s.top]=temp;
}
void tablefill(struct stacktype s,string type)
{
	int	i;

	for(i=s.top;i>0;i--)
		ENTRY[s.content[i]].type=type;
}

string  newvari(int count)
{
	string s;
	
	s=s+"t";
	s=convert(count,s);

	return s;
}

void f1()//K->func id {L}
{	
	backpatch(L_nextlist,nextquad);
	emit("end","","","0"); 
}

void f2()//L->LMS
{ 
	copy(L_nextlist,S_nextlist);
 }
 
void f3()//L->S
{
	copy(L_nextlist,S_nextlist);
}
 
void f4()//M->epsilon
{
	M_quad=nextquad; 
}

void f5()//S->{L}
{
	copy(S_nextlist,L_nextlist); 
}

void f6()//S->US 
{
	string a;

	backpatch(S_nextlist,nextquad);
	copy(S_nextlist,U.nextlist[U.Top]);
	a=convert(U.Head,a);
	emit("j","","",a);
}

void f7()//U->W B do
{ 
	U.Head=W_head;
	copy(U.nextlist[U.Top],B_falselist);   
	backpatch(B_truelist,nextquad);
} 

void f8()//W->while
{
	W_head=nextquad;
}

void f9()//C->if B then
{ 
	copy(C_nextlist,B_falselist); 
	backpatch(B_truelist,nextquad); 
}

void f10()//F->CSelse
{ 
	string a;
	struct stacktype s1,temp1;

	copy(F_nextlist,S_nextlist); 
	temp=nextquad;
	a=convert(temp,a);
	emit("j","","",a);
	makelist(s1,temp);
	merge(s1,F_nextlist);
	copy(temp1,C_nextlist); 
	backpatch(temp1,nextquad); 
}
  
void f11()//S->CS
{
	merge(C_nextlist,S_nextlist);
}

void f12()//S->FS
{
	merge(F_nextlist,S_nextlist); 
}

void f13()//S->TD
{
	tablefill(D_list,T_type);
}

void f14()//T->int
{
	T_type="int";
}

void f15()//D->D,id
{	
	Id.address=idstack.content[idstack.top];
	pop(idstack);
	push(D_list,Id.address);
}

void f16()//D->id
{
	while(!empty(D_list)) 
		pop(D_list);
	Id.address=idstack.content[idstack.top];
	pop(idstack);
	push(D_list,Id.address); 
}

void f17()//S->id=E;
{ 
	Id.address=idstack.content[idstack.top];
	Id.name=ENTRY[Id.address].idname;
	pop(idstack);
	emit("=",E.x[E.top],"",Id.name);
}

void f18()//B->B1&NB2
{ 
	merge(N_falselist,B2_falselist);
    copy(B_falselist,B2_falselist); 
}

void f19()//N->epsilon
{
	backpatch(B_truelist,nextquad); 
	copy(N_falselist,B_falselist);
}

void f20()//B->B1|PB2
{ 
	merge(P_truelist,B2_truelist);
    copy(B_truelist,B2_truelist);
}

void f21()//P->epsilon
{ 
	backpatch(B_falselist,nextquad); 
	copy(P_truelist,B_truelist);
}
 
void f22()//B->!B1
{ 
	copy(B_truelist,B1_falselist);
	copy(B_falselist,B1_truelist); 
}

void f23()//B->(B1)
{
	copy(B_truelist,B1_truelist);
	copy(B_falselist,B1_falselist);
}

void f24()//B->true
{ 
	string a;
	
	temp=nextquad; 
	a=convert(temp,a);
	emit("j","","",a);
	makelist(B_truelist,temp);
	makelist(B_falselist,0);
}

void f25()//B->false
{ 
	string s;
	temp=nextquad;
	s=convert(temp,s);
	emit("j","","",s);
	makelist(B_falselist,temp);
	makelist(B_truelist,0);
}

void f26()//B->id relop E
{ 
	string s1;

	temp=nextquad;
	s1=convert(temp,s1);
	emit(relop_op,relop_id,E.x[E.top],s1);
	makelist(B_truelist,temp);
	s1="";
	s1=convert(temp+1,s1);
	emit("j","","",s1);
	makelist(B_falselist,temp+1);
}

void f27()//relop-><
{ 
	Id.address=idstack.content[idstack.top];
	Id.name=ENTRY[Id.address].idname;
	pop(idstack);
	relop_op="j<"; 
	relop_id=Id.name;
}	

void f28()//relop-><=
{ 
	Id.address=idstack.content[idstack.top];
	Id.name=ENTRY[Id.address].idname;
	pop(idstack);
	relop_op="j<="; 
	relop_id=Id.name;
} 	

void f29()//relop->==
{ 
	Id.address=idstack.content[idstack.top];
	Id.name=ENTRY[Id.address].idname;
	pop(idstack);
	relop_op="j==";
	relop_id=Id.name;
}

void f30()//relop-><>
{ 
	Id.address=idstack.content[idstack.top];
	Id.name=ENTRY[Id.address].idname;
	pop(idstack);
	relop_op="j<>";
	relop_id=Id.name;
}

void f31()//E->E1+E2
{ 
	E.top++;
	E.x[E.top]=newvari(varicount);
    emit("+",E.x[E.top-2],E.x[E.top-1],E.x[E.top]);
	varicount++;
}

void f32()//E->E1*E2
{ 
	E.top++;
	E.x[E.top]=newvari(varicount);
	emit("*",E.x[E.top-2],E.x[E.top-1],E.x[E.top]);
	varicount++;
}

void f33()//E->(E1)
{ 
	E.top++;
	E.x[E.top]=newvari(varicount);
	emit("=",E.x[E.top-1],"",E.x[E.top]);
	varicount++;
}

void f34()//E->id
{ 
	Id.address=idstack.content[idstack.top];
	Id.name=ENTRY[Id.address].idname;
	Id.type=ENTRY[Id.address].type;
	pop(idstack);
	if(Id.type!="") 
	{
		E.top++;
		E.x[E.top]=Id.name; 
	}
	 else
	 {
		 E.top++;
		 E.x[E.top]=Id.name;
		 cout<<E.x[E.top]<<" not declared!"<<endl;
	  }
}

void f35()//E->const
{
	string s="";
	const_val=convert(digit[conststack.content[conststack.top]].value,s);
	pop(conststack);
	E.top++;
	E.x[E.top]=const_val;
}

void run(int a)
{
	switch (a)
	{
	case 1 :
		f1();
		break;
	case 2 :
		f2();
		break;
	case 3 :
		f3();
		break;
	case 4 :
		f4();
		break;
	case 5 :
		f5();
		break;
	case 6 :
		f6();
		break;
	case 7 :
		f7();
		break;
	case 8 :
		f8();
		break;
	case 9 :
		f9();
		break;
	case 10 :
		f10();
		break;
	case 11 :
		f11();
		break;
	case 12 :
		f12();
		break;
	case 13 :
		f13();
		break;
	case 14 :
		f14();
		break;
	case 15 :
		f15();
		break;
	case 16 :
		f16();
		break;
	case 17 :
		f17();
		break;
	case 18 :
		f18();
		break;
	case 19 :
		f19();
		break;
	case 20 :
		f20();
		break;
	case 21 :
		f21();
		break;
	case 22 :
		f22();
		break;
	case 23 :
		f23();
		break;
	case 24 :
		f24();
		break;
	case 25 :
		f25();
		break;
	case 26 :
		f26();
		break;
	case 27 :
		f27();
		break;
	case 28 :
		f28();
		break;
	case 29 :
		f29();
		break;
	case 30 :
		f30();
		break;
	case 31 :
		f31();
		break;
	case 32 :
		f32();
		break;
	case 33 :
		f33();
		break;
	case 34 :
		f34();
		break;
	case 35 :
		f35();
		break;
	}
}

//用第a条产生式规约
void execute(int a)
{
	int i;
	//输出产生式
	cout<<vn[generate[a].left]<<"->"<<generate[a].str<<endl;
	run(a);
	for(i=0;i<generate[a].length;i++)
	{
		pop(STACK);
		pop(STACK);	
	}
	push(STACK,generate[a].left);
	return;
}

//分析函数
void analyse()
{
	int first=0;
	int x,y;
	while(1)
	{
		x=checkact(STACK.content[STACK.top],token[first].id);
		while(x/1000!=0)
		{
			execute(x%1000);		//规约
			y=checkgoto(STACK.content[STACK.top-1],STACK.content[STACK.top]);
			push(STACK,y);
			x=checkact(STACK.content[STACK.top],token[first].id);
		}
		if(x==0)
			return;
		push(STACK,token[first].id);
		push(STACK,x%1000);
		if(token[first].id==11)
					push(idstack,token[first].entry);
				else if(token[first].id==10)
					push(conststack,token[first].entry);
		first++;
	}
}

//主函数
void main()
{
	int i;
	ofstream	new_file;
	init();
	analyse();
	new_file.open("new.txt");

	for(i=0;i<nextquad;i++)
	{
		new_file<<i<<"\t("<<quad[i].op<<" , "<<quad[i].first<<" , "<<quad[i].second<<" , "<<quad[i].third<<")"<<endl;
		cout<<i<<" ";
		cout<<"("<<quad[i].op<<" , "<<quad[i].first<<" , "<<quad[i].second<<" , "<<quad[i].third<<")"<<endl;
	}
	return;
}