function.h

编译原理实验

#include <iostream.h>
#include "stack.h"
//#include "head.h"
#include "queue.h"
#include <string.h>

////////////////////函数声名///////////////////////
void term();
void error();
bool Is_number(char temp);
bool Is_letter(char temp);
///////////////////////////////////////////////////

int lookup(char lexeme[])		//在标识符表里查找，找到返回其下标，找不到返回0
{
	int i;
	i=total;
	while(strcmp(lexeme,table[i].name)&&(i>0))
		i--;
	return i;
}

int insert(char lexeme[])		//将标识符插入到标识符表，并返回其插入的下标
{
	int i;
	i=lookup(lexeme);
	if(i==0)
	{
		total++;
		strcpy(table[total].name,lexeme);	//将lexeme的内容复制到table[total].name里
		return total;
	}
	else
		return i;
}

void getidentifer()		//识别标识符并将其插入到标识符表中
{
	char lexeme[17];	//标识符缓冲区
	int i;
	i=0;
	while(Is_letter(buffer[position])||Is_number(buffer[position]))
	{
		if(i<16)	//标识符长度小于16的部分保留，多余部分去掉
		{
			lexeme[i]=buffer[position];
			i++;
		}
		position++;
	}
	lexeme[i]='\0';	//结束符，要自己加上去
	position--;		//让position指回当前字符
	identry=insert(lexeme);
}

bool Is_number(char temp)	//判断是否为数字
{
	if(temp>='0'&&temp<='9')
		return true;
	return false;
}

bool Is_letter(char temp)	//判断是否为英文字母
{
	if((temp>='A'&&temp<='Z')||(temp>='a'&&temp<='z'))
		return true;
	return false;
}

bool Is_operator(char temp)
{
	for(int i=0;i<6;i++)
	{
		if(temp==operators[i])
			return true;
	}
	return false;
}

double num_analy()		//数字的识别，多位整数，小数
{
	double radix,decval;
	numval=0.0;
	do {
		decval=buffer[position]-'0';		//整数部分
		numval=numval*10+decval;
		position=position+1;
	}while(Is_number(buffer[position]));
	if (buffer[position]=='.'){				//小数部分
		position=position+1;
		radix=0.1;
		while(Is_number(buffer[position]))
		{
			decval=radix*(buffer[position]-'0');
			numval=numval+decval;
			radix=radix*0.1;
			position=position+1;
		}
	}//endif
	position=position-1;		//gettoken()首先position=position+1;
	return numval;
}

void gettoken()		//求表达式的值时用
{
    do{
		   position=position+1;
		   lookahead=buffer[position];
		}while(lookahead==' ');	//不为空格时停止，跳过遇到的空格
}

void error()
{
   cout<<buffer[position]<<" :"<<"syntax error."<<endl;
}

void expre()
{
	char addoper;		//addoper=='+'||addoper=='-'
	double operand;		//减数
	int j;
	term();
	j=identry;		//记住+=或-=符号前标识符的下标，如果first+=second便记住first在table的下标
	while(lookahead=='+'||lookahead=='-')
	{
		addoper=lookahead;
		gettoken();
		if(lookahead=='=')
		{
			gettoken();
			term();
			switch(addoper){
			case '+':
				array.Push(array.Pop()+array.Pop());	//相加的结果压栈
				table[j].value=array.GetTop();
				break;
			case '-':
				operand=array.Pop();
				array.Push(array.Pop()-operand);
				table[j].value=array.GetTop();
				break;
			}//end switch
		}//end if
		else
		{
			term();
			switch(addoper){
			case'+':
				array.Push(array.Pop()+array.Pop());	//相加的结果压栈
				break;
			case'-':
				operand=array.Pop();
				array.Push(array.Pop()-operand);		//相减的结果压栈
				break;
			}//end switch
		}//end else
	}//end while
}

void factor()
{
	double variable;
	if(lookahead=='(')
	{
		gettoken();
		expre();
		if(lookahead==')')
			gettoken();
		else 
			error();
	}
	else
		if(Is_letter(buffer[position]))		//遇到字母
		{		
			getidentifer();
			if(table[identry].evaluated==false)	//未赋值
			{
				int i=0;
				do{
					cout<<table[identry].name[i];
					i++;
				}while(table[identry].name[i]!='\0');
				cout<<":";
				cin>>variable;
				table[identry].value=variable;	//对标识符表里对于的标识符赋值
				table[identry].evaluated=true;	//并将其设为已赋值
			}
			else
				variable=table[identry].value;	//若该标识符已赋值，则将该值赋给variable
			array.Push(variable);		//将数值压栈，参加运算
			gettoken();
		}
		else
			if(Is_number(lookahead))
			{	
				variable=num_analy();		//数的识别
				array.Push(variable);		//压栈
				gettoken();
			}
			else
				error();
}

void term()
{
	char multoper;			//multoper=='*'||multoper=='/'
	double operand;			//除数
	int j;
	factor();
	j=identry;	//记住在talbe中的下标
	while(lookahead=='*'||lookahead=='/'){
		multoper=lookahead;
		gettoken();
		if(lookahead=='=')
		{
			gettoken();
			factor();
			switch(multoper){
			case '*':
				array.Push(array.Pop()*array.Pop());
				table[j].value=array.GetTop();
				break;
			case '/':
				operand=array.Pop();
				if(operand!=0.0)
				{
					array.Push(array.Pop()/operand);
					table[j].value=array.GetTop();
				}
				else
					cout<<"Zero divisor."<<endl;
				break;
			}
		}
		else
		{
		factor();
		switch(multoper){
		case'*':
			array.Push(array.Pop()*array.Pop());	//把相乘的结果压栈
			break;
		case'/':
			operand=array.Pop();
			if (operand!=0.0)
				array.Push (array.Pop()/operand);	//把相除的结果压栈
			else 
				cout<<"Zero divisor."<<endl;		//0不能作除数
			break;
		default:
			break;		//可省略
		}//swith
		}//end else
	}//while
	while(lookahead=='D'||buffer[position+1]=='I'||buffer[position+2]=='V')//整除DIV
	{
		position=position+2;
		gettoken();
		factor();
		operand=array.Pop();
		if(operand!=0.0)
			array.Push(int(array.Pop()/operand));
		else
			cout<<"Zero divisor."<<endl;
	}
	while(lookahead=='M'||buffer[position+1]=='O'||buffer[position+2]=='D')//求余MOD
	{
		position=position+2;
		gettoken();
		factor();
		operand=array.Pop();
		if(operand!=0.0)
			array.Push((int)array.Pop()%(int)operand);
		else
			cout<<"Zero divisor."<<endl;
	}
}

//////////////////////以下函数为生成语法树/////////////////////////////////////////
node* expr2();
node* term2();
node* factor2();
void printtree(node *root);
void traverse(node *ptr);

///////////////////////////lookahead有关说明//////////////////////////
//	1:+		2:-		3:*		4:/		5:(		6:)
//	7:标识符		8:数字	9:整除DIV		10:求模MOD
//	11:+=	12:-=	13:*=	14:/=
//////////////////////////////////////////////////////////////////////

void gettoken2()		//语法树生成时用
{
	while(buffer[position]==' ')
		position++;
	if(Is_operator(buffer[position]))
	{
		switch(buffer[position]){
		case '+':
			lookahead=1;
			if(buffer[position+1]=='=')
			{
				lookahead=11;
				position++;
			}
			break;
		case '-':
			lookahead=2;
			if(buffer[position+1]=='=')
			{
				lookahead=12;
				position++;
			}
			break;
		case '*':
			lookahead=3;
			if(buffer[position+1]=='=')
			{
				lookahead=13;
				position++;
			}
			break;
		case '/':
			lookahead=4;
			if(buffer[position+1]=='=')
			{
				lookahead=14;
				position++;
			}
			break;
		case '(':
			lookahead=5;
			break;
		case ')':
			lookahead=6;
			break;
		}
		position++;		//要加1，因为跟求值那里已经不同了
	}
	else
		if(buffer[position]=='D'||buffer[position+1]=='I'||buffer[position+2]=='V')//整除DIV
		{
			position=position+3;
			lookahead=9;	//整除DIV
		}
		else
			if(buffer[position]=='M'||buffer[position+1]=='O'||buffer[position+2]=='D')
			{
				position=position+3;
				lookahead=10;	//求余MOD
			}
			else
				if(Is_letter(buffer[position]))
				{
					getidentifer();
					lookahead=7;
					position++;		/////////////////////
				}
				else
					if(Is_number(buffer[position]))
					{
						num_analy();
						lookahead=8;
						position++;		/////////////////
					}
					else
						if(buffer[position]=='#')
							lookahead=0;
}

node* mknode(double tokencode)
{
	node *p;
	p=new node;
	if(tokencode==1||tokencode==2||tokencode==3||tokencode==4||tokencode==9||tokencode==10||
		tokencode==11||tokencode==12||tokencode==13||tokencode==14)
	{
		p->code=tokencode;			//+,-,*,/
		p->left=NULL;
		p->right=NULL;
	}
	else
		if(tokencode==7)
		{
			p->code=7;		//标识符
			p->entry=identry;
		}
		else
			if(tokencode==8)
			{
				p->code=8;	//数字
				p->value=numval;
			}
			else
				error();
	p->No=number;
	number++;
	return p;
}

node* factor2()
{
	node *pf;
	if(lookahead==5)
	{
		gettoken2();
		pf=expr2();
		if(lookahead==6)
			gettoken2();
		else
			error();
	}
	else
		if(lookahead==7||lookahead==8)
		{
			pf=mknode(lookahead);
			gettoken2();
		}
		else
			error();
	return pf;
}

node* term2()
{
	double multoper;
	node *pt,*ptl,*ptr;
	ptl=factor2();
	while(lookahead==3||lookahead==4||lookahead==9||lookahead==10||lookahead==13||lookahead==14)
	{
		multoper=lookahead;
		gettoken2();
		ptr=factor2();
		pt=mknode(multoper);
		pt->left=ptl;
		pt->right=ptr;
		ptl=pt;
	}
	return ptl;
}

node* expr2()
{
	double addoper;
	node *pe,*pel,*per;
	pel=term2();
	while(lookahead==1||lookahead==2||lookahead==11||lookahead==12)
	{
		addoper=lookahead;
		gettoken2();
		per=term2();
		pe=mknode(addoper);
		pe->left=pel;
		pe->right=per;
		pel=pe;
	}
	return pel;
}

void printtree(node *root)
{
	cout<<"No.  "<<"node     "<<"token     "<<"lexeme"<<endl;
	number=0;
	if(root!=NULL)
		traverse(root);
}

void traverse(node *ptr)
{
	if(ptr!=NULL)
	{
		number++;
		cout<<ptr->No<<"     "<<number<<"         "<<ptr->code<<"          ";
		switch((int)ptr->code){
		case 1:
			cout<<"+"<<endl;
			break;
		case 2:
			cout<<"-"<<endl;
			break;
		case 3:
			cout<<"*"<<endl;
			break;
		case 4:
			cout<<"/"<<endl;
			break;
		case 7:
			cout<<table[ptr->entry].name<<endl;
			break;
		case 8:
			cout<<ptr->value<<endl;
			break;
		case 9:
			cout<<"DIV"<<endl;
			break;
		case 10:
			cout<<"MOD"<<endl;
			break;
		case 11:
			cout<<"+="<<endl;
			break;
		case 12:
			cout<<"-="<<endl;
			break;
		case 13:
			cout<<"*="<<endl;
			break;
		case 14:
			cout<<"/="<<endl;
			break;
		}
		if(ptr->code<=4||ptr->code==9||ptr->code==10||ptr->code==11||ptr->code==12||
			ptr->code==13||ptr->code==14)
		{
			traverse(ptr->left);
			traverse(ptr->right);
		}
	}
}
//////////////////////////////////////////////////////////////////////////