1.cpp

编译原理课程设计

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXSIZE 64   //栈的大小
#define N -10
typedef char datatype;     //以char作为栈中元素

typedef struct          //定义一个栈结构
{ 
	datatype data[MAXSIZE]; 
	int top; 
}seqstack; 
seqstack OPR;                   //操作数栈OPR
seqstack OPT;                     //申明操作符栈
char *p;                          //全局变量指针，用来指向待分析字符串
int  matrix[15][15]={{N,-1,-1,-1,-1,N,1},        //算符优先矩阵
				   {N,1,-1,-1,-1,1,1},
				   {N,1,1,-1,-1,1,1},
                      {1,1,1,N,N,1,1},
                      {N,-1,-1,-1,-1,0,N},
                      {N,1,1,N,N,1,1},
                      {-1,N,N,-1,N,N,0}};
/*算符优先关系距阵
//-1表示对应的行元素的优先级低于对应的列元素的优先级
//0表示对应的行元素的优先级等于对应的列元素的优先级
//1表示对应的行元素的优先级高于对应的列元素的优先级
//N表示对应的行元素与列元素不存在优先关系

		=		+		*		i		(		)		$		
=				<		<		<		<				>
+				>		<		<		<		>		>
*				>		>		<		<        >	     >
i		>		>		>						>		>
(				<		<		<		<		=		
)				>		>						>		>
$		<						<						=
*/
int row,line;                     //全局变量，分别来表示算符优先矩阵的行和列
int count=1;                
int compare(char m,char n){        //算符的优先级
	switch(m){
		case '=':row=0;break;
		case '+':row=1;break;
		case '*':row=2;break;
		case 'i':row=3;break;
		case '(':row=4;break;
		case ')':row=5;break;
		case '$':row=6;break;
		default: return -100;break;
	}
	switch(n){
		case '=':line=0;break;
		case '+':line=1;break;
		case '*':line=2;break;
		case 'i':line=3;break;
		case '(':line=4;break;
		case ')':line=5;break;
		case '$':line=6;break;
		default: return -100;break;
	}
	return matrix[row][line];
}
//定义对操作数栈的基本操作
void OPRsetnull() //设置操作数栈空
{ 
	OPR.top=-1; 
} 
bool OPRempty() //判断操作数栈是否为空
{ 
	if(OPR.top>=0) 
		return false; 
	else  
		return true; 
} 
void OPRpush(char x) //往操作数栈push一个操作数i
{ 
	if(OPR.top==MAXSIZE-1) 
	printf("上溢!"); 
	else { 
	OPR.top++; 
	OPR.data[OPR.top]=x; 
	} 
} 
datatype OPRpop() //从操作数栈中pop出一个操作数
{ 
	if(OPRempty())
	{ 
		printf("下溢！");
		return NULL; 
	} 
	else 
	{ 
		OPR.top--; 
		return(OPR.data[OPR.top+1]); 
	} 
} 
//定义对操作数栈的基本操作结束

datatype OPRtop() //获取操作数栈的栈顶的操作数
{ 
	if(OPRempty()) 
	{ 
		return NULL; 
	} 
	else 
		return(OPR.data[OPR.top]); 
} 
void OPTsetnull() //设置操作符栈空
{ 
	OPT.top=-1; 
} 

bool OPTempty() //判断操作符栈是否为空
{ 
	if(OPT.top>=0) 
		return false; 
	else  
		return true; 
} 
void OPTpush(char x) //往操作符栈push一个操作数
{ 
	if(OPT.top==MAXSIZE-1) 
		printf("上溢!"); 
	else 
	{ 
		OPT.top++; 
		OPT.data[OPT.top]=x; 
	} 
} 
datatype OPTpop() //从操作数符中pop出一个操作数
{ 
	if(OPTempty()) 
	{ 
		printf("下溢！");return NULL; 
	} 
	else 
	{ 
		OPT.top--;
		return(OPT.data[OPT.top+1]); 
	} 
} 
datatype OPTtop() //获取操作符栈的栈顶的操作数
{ 
	if(OPTempty()) 
	{ 
		return NULL; 
	} 
	else return(OPT.data[OPT.top]); 
}
//定义对操作符栈的基本操作结束

void output(char opt,char op1,char op2,int num) //输出四元式
{
	if(op1=='i'&&op2=='i') printf("(%c,%c,%c,t%d)\n",opt,op1,op2,num);
	if(op1!='i'&&op2=='i') printf("(%c,t%d,%c,t%d)\n",opt,op1,op2,num);
	if(op2!='i'&&op1=='i') printf("(%c,%c,t%d,t%d)\n",opt,op1,op2,num);
	if(op1!='i'&&op2!='i') printf("(%c,t%d,t%d,t%d)\n",opt,op1,op2,num); 
}
void scan()//扫描语法分析程序
{
	char opt;
	char op1,op2;
	if(*p=='$') OPTpush(*p);//将待分析的字符串的首字符$压栈
	p++;
	while(*p!='$')//循环直到待分析字符串尾
	{ 
	 if(*p=='i') OPRpush(*p);//如果当前字符是操作数则入栈，只有i一种操作数
		 else { 
			 opt=OPTtop();
//否则是操作符与操作符栈顶的字符比较优先级
		P: switch(compare(opt,*p)){
				case -1:  OPTpush(*p); break;
//如果栈顶操作符优先级下，则将当前字符压栈
				case N:  break;    
//若无优先级 则说明待分析字符有误，不合语法规范 
//出现语法错误

			case 0:  OPTpop(); break;
//若操作符优先级相等则说明栈顶
//符合当前操作符分别是左右括号
//将栈顶的左括号出栈即可
			case 1:	op1=OPRpop();
//若栈顶操作符优先级高，则将操作符栈最上两个操作数出栈
						op2=OPRpop();
					    output(opt,op1,op2,count);//输出四元式
						OPRpush(count); //并将生成的t的序数压栈（t1，t2等）；
						count++;
						opt=OPTpop();//将已规约的输出的操作符出栈  
						opt=OPTtop();//取栈顶操作符跳转到继续下一步。
						goto P; break;
		   }
		 }
		 p++;
	}
	while(!OPTempty()&&!OPRempty()&&(OPTtop()!='$')){
//这里用来处理当p指向待分析字符串最后一个字符$时
		//但是操作符和操作数栈中依然有字符的情况
        op1=OPRpop();          
		op2=OPRpop();     //这种情况一般是栈底操作符优先级低于其上的操作符
		opt=OPTpop();          //所以只要从上往下直接规约和输出四元式
		if(opt!='='){              //在这里判断是否到'='来改换一个输出方式
			output(opt,op1,op2,count);
			OPRpush(char(count));
			count++;
		}
		if(opt=='=') printf("(%c,t%d,_,i)\n",opt,count-1);
	}
}
void main()
{
	int d;
	OPRsetnull();//操作数栈清空
	OPTsetnull();//操作数栈清空
	char ch[]="$i=i*(i*(i+i))*i$";//赋值语句 
	p=ch;
	scan();//扫描分析输出
	
}