luobo.cpp

基于递归下降分析法的循环语句WHILE E DO S1的语法及语义分析程序

#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include<iomanip.h>

#define $other 19
#define $mul   20
#define $div   21
#define $add   22
#define $sub   23
#define $fen   24
#define $equal 25
#define $WHILE 26              
#define $DO    27 
#define $big   29
#define $small 30
#define $ID    31       //字符
#define $num   32       //数字


/////////////////////////////////////////////////////////////
                                              
typedef struct Token
{
	int type;
	char ch;
}Token;                                   //定义输入串的结构

typedef enum{JUMP,JG,JL,equal,END,add,mul,sub,div}OpKind;      //操作符
typedef struct
{
	int label;//标号
	OpKind op;//操作符
	char par1,par2; //操作数
	union{
		char result; //结果
		int address; // 地址
	};
}Quad;      

typedef struct{				//逆波兰
	char nbl1[10];			//操作数数组
	char nbl2[20];			//操作符数组
}Nbl;



/////////////////////////////////////////////////////////////
#define MAX_TOKEN 256 //Token表大小  词法分析
#define MAX_QUAD 256 //逆波兰式数组大小

Token tokentable[MAX_TOKEN];    //建立词法表
Quad quad[MAX_QUAD];            //建立逆波兰式表
Nbl	nbl[10];
int nbln=0;					//第几条逆波兰式
int n=0;					//nbl1中当前包含几个字符
int j=0;
int m=0;
int token_index;//token表索引
int total_len;//token表有效长度

int quad_len;//逆波兰式表有效长度
int quad_index;//逆波兰式索引
Token cur;
Token queue[10];
int label,k,one;      //标记接口
ifstream ins;
int trueadd,falseadd,end;

                                                //申明函数
bool init(char filename[255]);
bool cifa();                           //词法分析函数
void print();                          //词法输出函数

void backpath(int,int);
void ERROR();
void S();
char M_addsub();
char F_addsub(char);
char P_muldiv(char);
char T_muldiv();
char B_number();
void E();
bool nexttoken();
int newlabel();
char newchar();
void push();
void nextone();
void yuyi();                        //语义分析函数
void printQuad();                   //输出逆波兰式表
void AD_ADDRESS(int nlabel,OpKind nop,char npar1,char npar2,int naddress);
void AD_RESULT(int nlabel,OpKind nop,char npar1,char npar2, char nresult);
///////////////////////////////////////////////////////////////

void main()
{   
	cout<<"文法结构:"<<endl;
	cout<<"------------------------------"<<endl;
	cout<<"S->M | WHILE E DO S "<<endl;
  	cout<<"E->id ^ id | id v id | ! id"<<endl;
    cout<<"M->TF|T"<<endl;
    cout<<"F-> +TF |-TF|ε"<<endl;
    cout<<"T->BP|B"<<endl;
    cout<<"P->*BP|/BP|ε"<<endl;
    cout<<"B->id|digit"<<endl;
	cout<<"------------------------------"<<endl;
	cout<<"请输入文件名称:";
	char fname[200];
	cin>>fname;
	if(!init(fname))               //打开文件
		return ;
	if(!cifa())                    //调用cifa()函数进行词法分析
		return ;
	char ch;
	while(1)
	{
		if(ins.eof())
			break;
		ins>>ch;
	}
	cout<<"词法分析结果:"<<endl;
	print();                    //输出词法分析结果
	cout<<endl;
	cout<<"词法分析结束"<<endl;
	cout<<endl;
	
	yuyi();                   //调用语法语义分析函数
	printQuad();              //输出逆波兰式
	if(label==0)
		cout<<"语法语义分析成功!"<<endl;
	else
		cout<<"语法语义分析失败!"<<endl;
}
char newchar()
{ char p;
    p=char(k);
	k++;
	return p;	 
}

//文件打开初始化
bool init(char filename[255])
{   
	one=0;
	token_index=0;
	total_len=0;
	quad_len=0;
	quad_index=0;
	label=0;
	end=0;
	k=48;
	ins.open(filename,ios::nocreate | ios::in);
	if(ins.fail())
	{
		cout<<"文件打开出错!"<<endl;
		return false;
	}

	return true;
}
//////////////////////////////////////////////////////////
                                                   //词法分析
bool cifa()
{
	int k=0;
	char buf[16];
	char ch;
	while(1)
	{
		ins>>ch;
		if(ins.fail())
			break;
		while(ch==' ')
		{	ins>>ch;}
		if(ch=='W')                                  //对输入串进行扫描
		{
			ins>>buf;
			if(strcmp(buf,"HILE")==0)                //扫描到while
				tokentable[total_len++].type=$WHILE; //就将while关键字存入表中
		}
		else if(ch=='D')
		{
			ins>>buf;
			if(strcmp(buf,"O")==0)
				tokentable[total_len++].type=$DO;    //将do关键字存入表中
		}
		else if(ch=='>')                             //以下将其他字符或数字存入表中
		{
			tokentable[total_len++].type=$big;
		}
			else if(ch=='<')
		{
			tokentable[total_len++].type=$small;
		}
		else if(ch=='=')
		{
			tokentable[total_len++].type=$equal;
		}
		else if((ch>='A'&& ch<='Z' )|| (ch>='a' && ch<='z'))
		{
			tokentable[total_len].type=$ID;
			tokentable[total_len++].ch=ch;
		}
		else if(ch>='0' && ch<='9')
		{	tokentable[total_len].type=$num;
		    tokentable[total_len++].ch =ch;
		}
		else
		switch (ch)                            //将扫描到的操作符存入表中
		{case '+' :
			tokentable[total_len].type=$add;
		    tokentable[total_len++].ch =ch;
	     	break;
		   case '-' :
			tokentable[total_len].type=$sub;
		    tokentable[total_len++].ch =ch;
	    	break;
			 case '/' :  	
			tokentable[total_len].type=$div;
		    tokentable[total_len++].ch =ch;
	    	break;
			 case '*' :
			tokentable[total_len].type=$mul;
		    tokentable[total_len++].ch =ch;
			break;
			 case ';' :
			tokentable[total_len].type=$fen;
		    tokentable[total_len++].ch =ch;
	    	break;
			 default:cout<<"!"<<endl;
		  
		}
	}
	return true;
	
}
void AD_RESULT(int nlabel,OpKind nop,char npar1,char npar2, char nresult)
{quad[quad_len].label=nlabel;
 quad[quad_len].op=nop; 
 quad[quad_len].par1=npar1;
 quad[quad_len].par2=npar2; 
 quad[quad_len].result=nresult; 
 quad_len++; 
}
void AD_ADDRESS(int nlabel,OpKind nop,char npar1,char npar2,int naddress)
 {	quad[quad_len].label=nlabel; 
	quad[quad_len].op=nop;
	quad[quad_len].par1=npar1;
	quad[quad_len].par2=npar2; 
	quad[quad_len].address=naddress;
	quad_len++; 
}


//扫描下一个单词函数
bool nexttoken()
{
	if(token_index>=total_len)
		return false;
	if(tokentable[token_index].type==$fen)
		token_index++;
	cur.type=tokentable[token_index].type;
	cur.ch=tokentable[token_index].ch;
	token_index++;
	return true;
}
//进队列
void push()
{   
while(tokentable[token_index].type!=$fen)
{
	queue[one].type=tokentable[token_index].type;
	queue[one].ch=tokentable[token_index].ch;
	token_index++;
	one++;
}
}
//队列下一个字符
void next()
{
 one--;
 cur.type=queue[one].type;
 cur.ch =queue[one].ch ;

}
//错误处理
void ERROR(char str[20])
{   label++;
	cout<<endl;
	cout<<"error!  "<<str<<endl;
}
          
void S()                 //处理S->id=M | while E do S语句
{   char rtn;
    char c;
	if(!nexttoken())
		ERROR("s(0)");
	if(cur.type==$ID)    
	{   	  
		c=cur.ch;
		if(!nexttoken())
		 ERROR("S(0)");
		if(cur.type!=$equal)
			ERROR("S(equal)");
		push();
		rtn=M_addsub();                             //调用M_addsub()函数分析加减法
		AD_RESULT(quad_len,equal,rtn,0,c);          //分析同时产生逆波兰式
		nexttoken();                                //加入逆波兰式表中
		while(cur.type==$ID)
		{
		c=cur.ch;
		if(!nexttoken())
		 ERROR("S(0)");
		if(cur.type!=$equal)
			ERROR("S(equal)");
		push();
		rtn=M_addsub();
		AD_RESULT(quad_len,equal,rtn,0,c);
		nexttoken();
		}
	}
	else if(cur.type==$WHILE)                         //当当前字符为while时
	{	    
			E();                                      //判断表达式E真值,调用E()函数
	     	if(!nexttoken())
			ERROR("S(0)");
			if(cur.type==$DO)                         //
			{  
				backpath(trueadd,quad_len+1);				
				S();                                  //递归调用S()分析do 之后的表达式        
				end=quad_len;
                 AD_ADDRESS(quad_len,JUMP,0,0,end);               

			}
			else
			{
				ERROR("S(do)");
			}
	}	 
	else
				ERROR("S(while)");
		
}

void E()        // 处理E->id < id | id > id语句
{  
 	char a,b;
	int c;	
    if(!nexttoken())
	ERROR("E(0)");
	if(cur.type==$ID||cur.type==$num)
	{
		a=cur.ch;
		if(!nexttoken())
			ERROR("E(0)");
	if(cur.type==$big||cur.type==$small)
	{	
		  c=cur.type ;		
		if(!nexttoken())
		 ERROR("E(0)");
		if(cur.type==$ID||cur.type==$num)   
			b=cur.ch;
		else
		    ERROR("E(id/num)");
        if(c==$big)
		{
		trueadd=quad_len;
		 falseadd=quad_len+1;
		AD_ADDRESS(quad_len,JG,a,b,trueadd);        //语法分析同时产生逆波兰式
		AD_ADDRESS(quad_len,JUMP,0,0,falseadd);     //并加入逆波兰式表中
        }
		else
		{
		trueadd=quad_len;
		 falseadd=quad_len+1;
		AD_ADDRESS(quad_len,JL,a,b,trueadd);
		AD_ADDRESS(quad_len,JUMP,0,0,falseadd);
		}
	}
		else
             ERROR("E(id/num)");
	}
	else
		ERROR("E(big/small)");	
}
//处理M->TF|T  规则对应句子  
char M_addsub()
{
 char rtn,t;
 rtn=T_muldiv();                                       //调用T_muldiv()函数分析乘除法
 t=rtn;
 rtn=F_addsub(t);                                      //调用F_addsub(t)函数分析加减法
 return rtn;
}
                       //处理乘除法,处理P->*BP|/BP|ε  规则对应句子 
char P_muldiv(char a)
{
 char t,b;
 next();
 if(cur.type==$mul||cur.type==$div)
 {
  int op=cur.type;
  b=B_number();
  t=newchar();
  if(op==$mul)
   AD_RESULT(quad_len,mul,a,b,t);            //分析同时产生逆波兰式
  else                                       //加入逆波兰式表中
    AD_RESULT(quad_len,div,a,b,t);
   
 }
 else
	 t=a;
 return t;
}
//处理加减法,处理F-> +TF |-TF|ε 规则对应句子 
char F_addsub(char a)
{ char t,b;
 if(cur.type==$add||cur.type==$sub)
 {int op=cur.type ;
   b=T_muldiv();
   t=newchar();
  if(op==$add)
     AD_RESULT(quad_len,add,a,b,t);           //分析同时产生逆波兰式
  else
     AD_RESULT(quad_len,sub,a,b,t);
 }
 else 
	 t=a;
  return t;	  
 
}
//处理T->BP|B   规则对应句子 
char T_muldiv()
{
 char t;
 char rtn;
 rtn=B_number();
 t=rtn;
 rtn=P_muldiv(t);
 return rtn;

}
//处理B->id|digit   规则对应句子 
char B_number()
{
 char rtn;
 next();
 if(cur.type==$num||cur.type==$ID)
	 rtn=cur.ch ;
 else
	 cout<<"error:B()"<<endl;
	 return rtn;
}
///////////////////////////////////////////////////////////
                                                //语义分析
void yuyi()
{
   	cout<<"语法语义分析,逆波兰式如下:"<<endl; 
   	S();                                     //调用S()函数分析第一条规则
	AD_RESULT(quad_len,END,0,0,'-');
}
///////////////////////////////////////////////////////////
void backpath(int nlabel,int addr)
{
	quad[nlabel].address=addr;
}

//输出词法分析单词表
void print()
{ 
	for(token_index=0;token_index<total_len;token_index++)
	{   
		if(tokentable[token_index].type==$WHILE)
			cout<<setw(10)<<"WHILE";
		if(tokentable[token_index].type==$DO)
			cout<<setw(10)<<"DO"<<endl;
		if(tokentable[token_index].type==$ID)
			cout<<setw(10)<<tokentable[token_index].ch;
		if(tokentable[token_index].type==$num)
			cout<<setw(10)<<tokentable[token_index].ch;
		if(tokentable[token_index].type==$equal)
			cout<<setw(10)<<'=';
		if(tokentable[token_index].type==$big)
			cout<<setw(10)<<'>';
		if(tokentable[token_index].type==$small)
			cout<<setw(10)<<'<';
        if(tokentable[token_index].type==$add)
			cout<<setw(10)<<'+';
		if(tokentable[token_index].type==$sub)
			cout<<setw(10)<<'-';
		if(tokentable[token_index].type==$mul)
			cout<<setw(10)<<'*';
		if(tokentable[token_index].type==$div)
			cout<<setw(10)<<'/';
		if(tokentable[token_index].type==$fen)
			cout<<setw(10)<<';'<<endl;
	}
	token_index=0;
}
//输出逆波兰式
void printQuad()
{
	for(int i=0;i<quad_len;i++)
	{
		if(quad[i].op==JG)
		{
		}
		else if(quad[i].op==JL)
		{
		}
		else if(quad[i].op==JUMP)
		{
		}
		else if(quad[i].op==equal)
		{   
			nbl[nbln].nbl1[n++]=quad[i].result;
			strcat(nbl[nbln].nbl2,"=");
			nbln++;
			n=0;
		}
		else if(quad[i].op==END)
		{
		}
		else if(quad[i].op==add)
		{  
   			
		   nbl[nbln].nbl1[n++]=quad[i].par1;
		   nbl[nbln].nbl1[n++]=quad[i].par2;
			strcat(nbl[nbln].nbl2,"+");
		}
		else if(quad[i].op==sub)
		{ 
		   nbl[nbln].nbl1[n++]=quad[i].par1;
		   nbl[nbln].nbl1[n++]=quad[i].par2;
			strcat(nbl[nbln].nbl2,"-");
		}
		else if(quad[i].op==div)
		{    
			
		   nbl[nbln].nbl1[n++]=quad[i].par1;
		   nbl[nbln].nbl1[n++]=quad[i].par2;
			strcat(nbl[nbln].nbl2,"/");
		}
		else if(quad[i].op==mul)
		{  
		   nbl[nbln].nbl1[n++]=quad[i].par1;
		   nbl[nbln].nbl1[n++]=quad[i].par2;
			strcat(nbl[nbln].nbl2,"*");
		}
	}
	for(j=0;j<nbln;j++)
	{
		cout<<"L"<<j+1<<":";
		for(m=strlen(nbl[j].nbl1);m>0;m--)
			cout<<nbl[j].nbl1[m-1];
		cout<<nbl[j].nbl2<<endl;
	}
}