bianyi.cpp

词法分析和语法分析,基于算术优先文法分析的汇编课设

#include <stdio.h>
#include <string.h>
char *action[10][3]={"S3#","S4#",NULL, NULL,NULL,"acc", /*ACTION表*/
                      "S6#","S7#",NULL,"S3#","S4#",NULL,
                      "r3#","r3#",NULL,NULL,NULL,"r1#","S6#","S7#",NULL,NULL,NULL,
					  "r3#","r2#","r2#",NULL,NULL,NULL,"r2#"};
int goto1[10][2]={1,2,0,0,0,5,0,8,0,0,0,0,0,9}; /*GOTO表*/
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include"math.h"
#include"iostream.h"

char str[100];
char ch;
int	nn=0;
int	f=0;
char count='0';


	
struct cifa            //定义词法结构体
{
	int  type;        //类型
	char word[10];    //字符串内容
	cifa *next;
};
cifa *cifa_head,*cifa_end,*cifa_p;//cifa队列

struct yufa          //定义语法结构体
{
	yufa *pre;
	char  word[10];  //字符串内容
	yufa *next;
};
yufa *yufa_head,*yufa_end,*yufa_q,*yufa_vt;//yufa队列


struct yuyi//定义语义结构体
{
	char  op;      //操作符
	char  op1[10]; //操作数 1
	char  op2[10]; //操作数 2
	char  result[10]; //结果
	yuyi  *next;
};
yuyi *yuyi_head,*yuyi_end,*yuyi_q,*yuyi_vt;//yuyi队列
char E_name[10],T_name[10],F_name[10],temp_name[10];

//*****************************************词法分析部分***************************************

cifa *cifa_add(cifa *p)			//在分析结果列表尾添加一个新接点
{
	cifa_end->next=p;
	cifa_end=cifa_end->next;
	return cifa_head;
}

void cifa_disp(cifa *cifa_head)	//输出词法分析结果
{
	cifa *p;
	p=cifa_head->next ;
	cout<<"  "<<'('<<'\t'<<"编码"<<'\t'<<','<<'\t'<<"符号"<<'\t'<<')'<<endl;
	while(p!=NULL)
	{
	 cout<<"  "<<'('<<'\t'<<p->type<<'\t'<<','<<'\t'<<p->word<<'\t'<<')'<<endl;
	 p=p->next;
	}
}


void GetChar()			//读取字符
{
  ch=str[nn];
  nn++;
}

void out_space()		//去掉空格
{
   if(ch==' ' )
	 while(ch==' ')
		GetChar();
}


void ider(void)        //标识符   
{		
	int	i=0;
	char temp[10];
	int	type=1;
	temp[i]=ch;
	i++;
	GetChar();
	while((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch=='_')||(ch>='0'&&ch<='9'))
	{
	temp[i]=ch;
	i++;
	GetChar();
	}
	temp[i]='\0';
	if(ch==' ')out_space();
	 else if(ch!='^'&&ch!='+'&&ch!='-'&&ch!='='&&ch!='&'&&ch!='*'&&ch!='/'&&ch!='('&&ch!='|'&&ch!=')'&&ch!=';')
	  {
	   cout<<temp<<"接错误后缀，出错"<<endl;
	   return ;
	  }	
	cifa *p;
	p=new cifa;
	p->next=NULL;
	p->type=type;
	strcpy(p->word,temp);
	cifa_add(p);	 	
}

void number(void)   //数字 
{
	int type=2;
    int i=0;
	char temp[10];
    while('0'<=ch&&ch<='9')
    {
	 temp[i]=ch;
	 i++;
	 GetChar();
    }
	temp[i]='\0';
	if(ch==' ')out_space();
	  else if(ch!='^'&&ch!='+'&&ch!='-'&&ch!='='&&ch!='&'&&ch!='*'&&ch!='/'&&ch!='('&&ch!='|'&&ch!=')')
	  {
	   cout<<temp<<"接错误后缀，出错"<<endl;
	   return ;
	  }
	  if(ch==' ')out_space(); 	
	cifa *p;
	p=new cifa;
	p->next=NULL;
	p->type=type;
	strcpy(p->word,temp);
	cifa_add(p);	
}

void test(void)     //符号 
{
	char temp[3];
	int i=0;
	int type;
	switch (ch)
	{
	case ';':			// ';'
		{
		temp[i++]=ch;
		GetChar();
		if(ch==' ')temp[i++]=' ';
		temp[i]='\0';
		type=4;
		break;
		}
	case '=':		
		{
		temp[i++]=ch;
		GetChar();
		if(ch==' ')temp[i++]=' ';		// '='
		temp[i]='\0';	
		type=3;
		break;
		}
	case '+':		
		{
		temp[i++]=ch;
		GetChar();
		if(ch==' ')temp[i++]=' ';	// '+'
		temp[i]='\0';
		type=3;
		break;
		}
	case '-':			
		{
		temp[i++]=ch;
		GetChar();
		if(ch==' ')temp[i++] =' ';		// '-'
		temp[i]='\0';
		type=3;
		break;
		}
	case '*':			// '*'
		{
		temp[i++]=ch;
		GetChar();
		if(ch==' ')temp[i++]=' ';
		temp[i]='\0';
		type=3;
		break;
		}
	case '/' :			// '/'
		{
		temp[i++]=ch;
		GetChar();
		if(ch==' ')temp[i++]=' ';
		temp[i]='\0';
		type=3;
		break;
		}
	case '(':
		{
		temp[i++]=ch;  // '('
		GetChar();
		if(ch==' ')temp[i++]=' ';
		temp[i]='\0';
		type=4;
		break;
		}
	case ')' :
		{
		temp[i++]=ch;  // ')'
		GetChar();
		if(ch==' ')temp[i++]=' ';			    
		temp[i]='\0';
		type=4;
		 break;	
		}
	case ' ':return; 
	case '^':return;
	default :
		{cout<<ch;
		cout<<"无法识别，出错！"<<endl;
		GetChar();
		if(ch==' ')out_space();
		return;
		}
	}
	if(ch==' ')out_space();    // 空格跳过	
	cifa *p;
	p=new cifa;
	p->next=NULL;
	p->type=type;
	strcpy(p->word,temp);
	cifa_add(p);	
} 
					
void cifa_main()		//词法分析主函数
{
	cifa_head=new cifa;
	cifa_head->type=-1;
	cifa_head->next=NULL;
	cifa_end=cifa_head;
	cout<<" 单词种类定义如下     ：                 "<<endl;
	cout<<"****************************************"<<endl;
	cout<<"                        种类编码     "<<endl;
	cout<<"  标识符             ----------1           "<<endl;
	cout<<"  常数               ----------2           "<<endl;	
	cout<<"  算术运算符         ----------3           "<<endl;
	cout<<"  界限符             ----------4           "<<endl;
	GetChar();
	out_space();
	cout<<"****************************************"<<endl<<" 词法分析结果如下："<<endl;
	while (nn<100&&ch!='^')
	{
	   if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch=='_'))ider(); //字母串
	   else if(ch>='0'&&ch<='9')number(); //数字串
		    else test();//其他符号
	} 
	cifa_disp(cifa_head);
}
//*****************************************语法分析部分***************************************

int E();
int G();
int S();
int T();
int F();

void advance()//取词法分析产生列表中的结点作语法分析
{
  cifa_p=cifa_p->next;
}

void yufa_zfc_disp(cifa *p)
{
 while(p!=NULL)
 {
  cout<<p->word ;
  p=p->next;
 }
  cout<<endl;
}

void yufa_zhan_disp(yufa *p)
{
while(p!=NULL)
{
 cout<<p->word ;
 p=p->next;
}
 cout<<endl;
}
//***************************************************************************************
int E()
{
	int t,g;
	cout<<f++<<'\t'<<"E -> TG"<<endl;
	t=T();
	if(t==0) return(0);
	g=G();
	if(g==0) return(0);
	else return (1);
}

int G()//******************分析一下））））））））））））））））））））））））））））））））
{
	int t,g;
	if (strcmp(cifa_p->word,"+")==0) 
	{
	 cout<<f++<<'\t'<<"G -> +TG"<<endl;
	 advance();
	 t=T();
	 if(t==0) return(0);
   	 g=G();
	 if(g==0) return(0);
     return (1);
	}
	else if(strcmp(cifa_p->word,"-")==0) 
	{
	  cout<<f++<<'\t'<<"G -> -TG"<<endl;
	  advance();
	  t=T();
	  if(t==0) return(0);
	  g=G();
	  if(g==0) return(0);
	  return(1);
	}
	else if(strcmp(cifa_p->word,")")==0||strcmp(cifa_p->word,"#")==0) 
	{
	  cout<<f++<<'\t'<<"G -> ε"<<endl;
	  return(1);
	}
}

int T()
{
	int t,g;
	cout<<f++<<'\t'<<"T -> FS"<<endl;
	t=F();
	if(t==0) return 0;
	g=S();
	if(g==0) return 0;
	return(1);
}

int S()
{
	int t,g;
	if(strcmp(cifa_p->word,"*")==0) 
	{
	 cout<<f++<<'\t'<<"S -> *FS"<<endl;
     advance();
	 t=F();
	 if(t==0) return 0;
	 g=S();
	 if(g==0) return 0;
	 return(1);
	}
	else if(strcmp(cifa_p->word,"/")==0) 
	{
	  cout<<f++<<'\t'<<"S -> /FS"<<endl;
	  advance();
	  t=F();
	  if(t==0)return 0;
	  g=S();
	  if(g==0)return 0;
	  return(1);
	}
	else if(strcmp(cifa_p->word,"+")==0||(strcmp(cifa_p->word,"-")==0)||(strcmp(cifa_p->word,"#")==0)||(strcmp(cifa_p->word,")")==0)) 
	{
	  cout<<f++<<'\t'<<"S -> ε"<<endl;
	  return(1);
	}
}

int F()
{
	int m;
	if ((strcmp(cifa_p->word,"(")==0))	
	{
		cout<<f++<<'\t'<<"F -> (E)"<<endl;
		advance();
		m=E();
		if(m==0) return (0);
		if((strcmp(cifa_p->word,")")==0)) 
		{			
		 advance();
		 return (1);
		}
		else 
		{
		 cout<<"ERROR"<<endl;
		 return (0);
		}
	}
	else if(cifa_p->type==1||cifa_p->type==2)
	{
	 cout<<f++<<'\t'<<"F -> 标识符｜无符号整数"<<endl;
	 advance();
	 return(1);
	}
	else return 0;
}

int yufa_main()
{
	int n;
	cifa *p=new cifa;
	strcpy(p->word ,"#");
	p->type=-1;
	p->next=NULL;
	cifa_add(p);	
	cifa_p = cifa_head;
	yufa_zfc_disp(cifa_head->next);
	yufa_head=new yufa;
	yufa_head->pre=NULL;
	yufa_head->next=NULL;
	strcpy(yufa_head -> word ,"#");
	yufa_end = yufa_head;	
	advance();
	n=E();	
	if(n==0) 
	{
	  cout<<endl<<"输入串不是该文法的一个句子！"<<endl;
	  return(0);
	}
	else if(n==1)
	{
	  cout<<endl<<"输入串是该文法的一个句子！  "<<endl;
	  return(1);
	}
}
//********************************语义分析**************************************************
yuyi *yuyi_add(yuyi *p)
{
  yuyi_end->next=p ;
  yuyi_end=p;
  return yuyi_head;
}
int E1();
int T1();
int F1();

void yuyi_sys_disp()
{ 
  yuyi *p;
  p=yuyi_head->next;
  while(p!=NULL)
  {
   cout<<"  "<<'('<<p->op<<','<<p->op1<<','<<p->op2<<','<<p->result<<')'<<endl;
   p=p->next;
  }
cout<<endl;
}

int E1()
{
	yuyi *p = new yuyi;
	T1();
	strcpy(p->op1,T_name);
	if (strcmp(cifa_p->word,"+")==0) 
	{
	 advance();
	 E1();
	 p->next=NULL;
	 p->op='+';
	 strcpy(p->op2,E_name);		
	 E_name[0]='t';
	 E_name[1]=++count;
	 E_name[2]='\0';
  	 strcpy(p->result,E_name);
	 yuyi_add(p);
	 return (1);
	}
	else if(strcmp(cifa_p->word,"-")==0) 
	{
	 advance();
	 E1();	
	 p->next=NULL;
	 p->op='-';
	 strcpy(p->op2,E_name);		
	 E_name[0]='t';
	 E_name[1]=++count;
	 E_name[2]='\0';
	 strcpy(p->result,E_name);
	 yuyi_add(p);
 	 return(1);
	}
	else
	{		
	 strcpy(E_name,T_name);
	 return(1);
	}	
}


int T1()
{
	yuyi *p = new yuyi;	
	F1();	
	strcpy(p->op1,F_name);
	if (strcmp(cifa_p->word,"*")==0) 
	{
	 advance();
	 T1();	
	 p->next =NULL;
	 p->op = '*';
  	 strcpy(p->op2,T_name);	
	 T_name[0]='t';
 	 T_name[1]=++count;
	 T_name[2]='\0';
     strcpy(p->result,T_name);
	 yuyi_add(p);
		return(1);
	}
	else if(strcmp(cifa_p->word,"/")==0) 
	{
		advance();
		T1();
		p->next=NULL;
		p->op='/';
		strcpy(p->op2,T_name);	
		T_name[0]='t';
		T_name[1]=++count;
		T_name[2]='\0';
		strcpy(p->result,T_name);
		yuyi_add(p);
		return(1);
	}
	else 
	{	
		strcpy(T_name,F_name);
		return(1);
	}
}

int F1()
{	
	if ((strcmp(cifa_p->word,"(")==0))	
	{
		advance();		
		strcpy(F_name,cifa_p->word);
		strcpy(E_name,F_name);	
		E1();
		if  ((strcmp(cifa_p->word,")")==0)) 
		{
		 advance();
		 strcpy(F_name,E_name);
		 return (1);
		}
	 	else 
		{
		 cout<<"ERROR"<<endl;
		 return (0);
		}
	}
	else if(cifa_p->type==1||cifa_p->type==2)
	{
	 strcpy(F_name,cifa_p->word);
	 advance();
	 return (1);
	}
	else return 0;
}


void yuyi_main()
{
	cifa_p=cifa_head;
	yuyi_head=new yuyi;
	yuyi_head->next = NULL;
	yuyi_end=yuyi_head;
	yufa_zfc_disp(cifa_head->next);
	advance();
	E1();
	yuyi_sys_disp();
}

//********************************主函数***************************************************
void main()
{  
	int len;
    cout<<"算术表达式的文法描述："<<endl;
    cout<<" E -> TG          "<<endl;
    cout<<" T -> FS          "<<endl;
    cout<<" G -> +TG｜-TG｜ε"<<endl;
    cout<<" S -> *FS｜/FS｜ε"<<endl;
    cout<<" F -> (E)｜标识符｜无符号整数"<<endl<<endl;	
	cout<<"请输入算术表达式："<<endl<<endl;
	gets(str);
	len = strlen(str);
	str[len] = '^';
	cout<<endl<<"---------------进行词法分析----------------"<<endl<<endl;
	cifa_main();
	cout<<endl<<"---------------进行语法分析----------------"<<endl<<endl;
	yufa_main();
	cout<<endl<<"---------------进行语义分析----------------"<<endl<<endl;
	yuyi_main();
	//	cin>>len;

}