parse.cpp

一个类c语言的解释器

	followset.push_back(_RBPAREN);
	followset.push_back(_INT);
	followset.push_back(_REAL);
	temp = compound_stmt(appendVector(synchset,followset));
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	//while循环的一个过程执行结束侯,无条件跳转到判断表达式处,判断是否该执行下一个循环
	code->push_back("JMP "+itos(address));
	codeAddress++;
	//回填while开始时候的跳转地址,如果while循环不执行,则跳转到此处
	code->at(backfill)="JPC "+itos(codeAddress);
	codeAddress++;
	check_input(appendVector(synchset,followset),firstset);
	return t;
}


/*
*<read_exp>::=read ID;
*firstset _READ
*followset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*/
TreeNode* read_exp(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "read_exp";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_READ);
	followset.push_back(_ID);
	followset.push_back(_IF);
	followset.push_back(_WHILE);
	followset.push_back(_READ);
	followset.push_back(_WRITE);
	followset.push_back(_RETURN);
	followset.push_back(_RBPAREN);
	followset.push_back(_INT);
	followset.push_back(_REAL);
	match(_READ,t);
	TokenRecord id = token;
	bool isArr = false;
	if(tokenList->at(index+1).tp==_LMPAREN)
		isArr = true;
	temp = var(appendVector(synchset,followset));
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	else{
		parse_err = true;
		errorList->push_back("miss the variable to store input at line "+itos(token.lineno));
		return NULL;
	}
	match(_SEMI,t);
	check_input(appendVector(synchset,followset),firstset);
	if(sym->find(id.tv)==NULL){
		parse_err = true;
		errorList->push_back("undeclared identifier "+token.tv+" at line "+itos(token.lineno));
		symbol->id = token.tv;
		sym->insert(symbol);
		symbol = new Symbol;
	}
	else{
		//弹出变量的值
		code->pop_back();
		codeAddress--;
		//获取保存输入ID的类型
		//输入的数据同样也会转换为该类型
		int type = sym->find(id.tv)->type;
		//输入一个和保存输入的变量类型相同的数保存再栈顶
		code->push_back("IN "+itos(type));
		codeAddress++;
		//保存数据栈顶的数字到要保存的变量中
		if(!isArr)
			code->push_back("STO "+sym->find(id.tv)->address);
		else{
			code->push_back("STO "+sym->find(id.tv)->address+"+[TOP]");
		}
		codeAddress++;
	}
	return t;
}

/*
*<write_exp>::=write <expression>;
*firstset _WRITE
*followset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*/
TreeNode* write_exp(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "write_exp";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_WRITE);
	followset.push_back(_ID);
	followset.push_back(_IF);
	followset.push_back(_WHILE);
	followset.push_back(_READ);
	followset.push_back(_WRITE);
	followset.push_back(_RETURN);
	followset.push_back(_RBPAREN);
	followset.push_back(_INT);
	followset.push_back(_REAL);
	match(_WRITE,t);
	synchset.push_back(_SEMI);
	temp = expression(appendVector(synchset,followset));
	data_type->pop_back();
	code->push_back("OUT");
	codeAddress++;
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	else{
		errorList->push_back("miss expression after 'write' at line " + itos(token.lineno));
	}
	match(_SEMI,t);
	check_input(appendVector(synchset,followset),firstset);
	return t;
}

/*
*<return_exp>::=return <expression>;
*firstset _RETURN
*followset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*/
TreeNode* return_exp(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "return_exp";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_RETURN);
	followset.push_back(_ID);
	followset.push_back(_IF);
	followset.push_back(_WHILE);
	followset.push_back(_READ);
	followset.push_back(_WRITE);
	followset.push_back(_RETURN);
	followset.push_back(_RBPAREN);
	followset.push_back(_INT);
	followset.push_back(_REAL);
	check_input(firstset,synchset);
	match(_RETURN,t);
	synchset.push_back(_SEMI);
	temp = expression(appendVector(synchset,followset));
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	else{
		errorList->push_back("miss expression after 'return' at line " + itos(token.lineno));
	}
	//判断返回类型是否和函数类型兼容,不兼容则报错
	if (fun->type<data_type->at(data_type->size()-1))
	{
		parse_err = true;
		errorList->push_back("return statement at line"+itos(token.lineno)+" conver 'real' to 'int'");
	}
	data_type->pop_back();
	match(_SEMI,t);
	//函数返回
	code->push_back("RET");
	codeAddress++;
	check_input(appendVector(synchset,followset),firstset);
	return t;
}
/*
*<local_var_declaration>::=(int|real)<var_list>
*firstset _INT _REAL
*followset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*/
TreeNode* local_var_declaration(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "local_var_declaration";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_INT);
	firstset.push_back(_REAL);
	followset.push_back(_ID);
	followset.push_back(_IF);
	followset.push_back(_WHILE);
	followset.push_back(_READ);
	followset.push_back(_WRITE);
	followset.push_back(_RETURN);
	followset.push_back(_RBPAREN);
	followset.push_back(_INT);
	followset.push_back(_REAL);
	//设置isLocal=true
	isLocal = true;
	check_input(firstset,synchset);
	//设置参数的类型
	if (token.tp==_INT||token.tp==_REAL)
	{
		if (token.tp==_INT)
		{
			match(_INT,t);
			symbol->type = 0;
		}
		else{
			match(_REAL,t);
			symbol->type=1;
		}
		temp = var_list(appendVector(synchset,followset));
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
		else{
			errorList->push_back("miss varlist at line "+ itos(token.lineno));
		}
	}
	check_input(appendVector(synchset,followset),firstset);
	return t;
}

/*
*<var_list>::=(ID[=<expression>])|(ID[NUM][={<num_list>}])){,(ID[=<expression>])|(ID[NUM][={<num_list>}]))};
*firstset _ID
*followset
*/
TreeNode* var_list(vector<_TokenType> synchset){
	int ln = token.lineno;
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "var_list";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_ID);
	followset.push_back(_INT);
	followset.push_back(_REAL);
	int type = symbol->type;
	//当当前token为ID的时候,执行变量定义,这样可以同时定义多个变量
	while (token.tp==_ID&&ln == token.lineno)
	{
		printf_skip_err = true;
		if(check_input(firstset,synchset)==2){
			break;
		}
		printf_skip_err = false;
		synchset.push_back(_SEMI);
		//如果当前符号表里面包含ID,则是重复定义,报错
		if (sym->contain(token.tv))
		{
			parse_err = true;
			errorList->push_back("identifier '"+token.tv+"' at line "+itos(token.lineno)+" redefine");
		}
		match(_ID,t);
		//设置变量的id为上一个token的id
		symbol->id = tokenList->at(index-1).tv;
		//设置当前的符号的地址
		if(!isLocal)
			//如果是全局变量,设置地址为当前的全局变量地址
			symbol->address = itos(dataAddress);
		else{
			//如果是局部变量,设置地址为SP+当前局部变量地址
			symbol->address = "SP+"+itos(local_address);
		}
		//数组定义
		if (token.tp==_LMPAREN)
		{
			//设置符号的isarr=true
			symbol->isarr = true;
			match(_LMPAREN,t);
			match(_INUM,t);
			//读取当前的数组的大小
			currArraySize = atoi(tokenList->at(index-1).tv.c_str());
			if(!isLocal)
				//如果是全局变量,增加全局的变量的地址
				dataAddress+=atoi(tokenList->at(index-1).tv.c_str());
			else
				//如果是局部变量,增加局部变量的地址
				local_address+=atoi(tokenList->at(index-1).tv.c_str());
			//设置符号的size为数组的size
			symbol->size = atoi(tokenList->at(index-1).tv.c_str());
			//符号为int型
			if (type==0)
			{
				if(!isLocal){
					//全局变量,再全局数据区定义
					data->push_back("INT "+itos(symbol->size));
				}
				else{
					//局部变量,在代码区定义
					code->push_back("INT "+itos(symbol->size));
					codeAddress++;
				}
			}
			//符号为real型
			else{
				if(!isLocal){
					//全局变量,再全局数据区定义
					data->push_back("REAL "+itos(symbol->size));
				}
				else{
					//局部变量,在代码区定义
					code->push_back("REAL "+itos(symbol->size));
					codeAddress++;
				}
			}
			match(_RMPAREN,t);
			//当前输入符号为=,则在定义的时候赋值
			if (token.tp==_ASSIGN)
			{
				int temp_address;
				if (!isLocal)
				{
					temp_address = codeAddress;
				}
				match(_ASSIGN,t);
				match(_LBPAREN,t);
				//
				temp = num_list();
				if (temp!=NULL)
				{
					t->addChild(temp);
				}
				else{
					errorList->push_back("miss numlist after '[' at line "+ itos(token.lineno));
				}
				match(_RBPAREN,t);
				//数组大小-初始化的个数可以获取初始化的个数
				//
				if(!isLocal){
					for (int i=currArraySize-initNums+1;i<=currArraySize;i++)
					{
						code->push_back("STO "+itos(dataAddress-i));
						codeAddress++;
					}
				}
				else{
					for (int i=currArraySize-initNums+1;i<=currArraySize;i++)
					{
						code->push_back("STO SP+"+itos(local_address-i));
						codeAddress++;
					}
				}
				if (!isLocal)
				{
					for (int i = temp_address;i<codeAddress;i++)
					{
						global_init->push_back(code->at(i));
					}
					while (codeAddress!=temp_address)
					{
						code->pop_back();
						codeAddress--;
					}
				}
			}			
		}
		else{
			if (isLocal)
			{
				local_address++;
			}
			else{
				dataAddress++;
			}
			//数字定义,符号的大小为1
			symbol->size = 1;
			if (type==0)
			{
				if(!isLocal){
					//全局变量,再全局数据区定义
					data->push_back("INT "+itos(1));
				}
				else{
					//局部变量,在代码区定义
					code->push_back("INT "+itos(1));
					codeAddress++;
				}
			}
			//符号为real型
			else{
				if(!isLocal){
					//全局变量,再全局数据区定义
					data->push_back("REAL "+itos(1));
				}
				else{
					//局部变量,在代码区定义
					code->push_back("REAL "+itos(1));
					codeAddress++;
				}
			}
			//数字定义时同时赋值
			if (token.tp==_ASSIGN)
			{
				int temp_address;
				if (!isLocal)
				{
					temp_address = codeAddress;
				}
				match(_ASSIGN,t);
				temp = expression(appendVector(synchset,followset));
				//类型检查,判断类型栈顶的类型是否可以和定义的类型兼容
				if (type==0)
				{
					//不兼容,打印错误
					if (type!=data_type->at(data_type->size()-1))
					{
						parse_err = true;
						errorList->push_back("line "+itos(token.lineno)+", can,t cast right-hand expression  from 'real' to 'int'");
					}
				}
				//弹出符号栈的栈顶符号
				data_type->pop_back();
				code->push_back("STO "+symbol->address);
				codeAddress++;
				if (temp!=NULL)
				{
					t->addChild(temp);
				}
				//把数字栈顶的符号保存到变量中

				else{
					parse_err = true;
					errorList->push_back("miss expression after '=' at line " + itos(token.lineno));
				}
				if (!isLocal)
				{
					for (int i = temp_address;i<codeAddress;i++)
					{
						global_init->push_back(code->at(i));
					}
					while (codeAddress!=temp_address)
					{
						code->pop_back();
						codeAddress--;
					}
				}
			}
		}
		//如果遇到';',变量定义结束
		if (token.tp==_SEMI)
		{
			match(_SEMI,t);
			//如果当前符号表中有当前符号同id的符号,重复定义,打印错误
			if (sym->contain(symbol->id))
			{
				/*parse_err = true;
				errorList->push_back("identifier '"+symbol->id+"' at line "+itos(token.lineno));*/
			}
			//如果当前符号表中没有当前符号同id的符号,插入当前符号到符号表,并初始化当前符号,以便处理下一个符号
			else{
				sym->insert(symbol);
				symbol = new Symbol;
			}

			break;
		}
		//如果遇到','接着定义下一个符号
		if (token.tp==_COMMA)
		{
			match(_COMMA,t);
			//如果当前符号表中有当前符号同id的符号,重复定义,打印错误
			if (sym->contain(symbol->id))
			{
				/*parse_err = true;
				errorList->push_back("identifier '"+symbol->id+"' at line "+itos(token.lineno));*/
			}
			else{
				//如果当前符号表中没有当前符号同id的符号,插入当前符号到符号表,并初始化当前符号,以便处理下一个符号
				//并初始化新的当前符号的类型和老的相同
				sym->insert(symbol);
				int t = symbol->type;
				symbol = new Symbol;
				symbol->type = t;
			}		
			continue;
		}

	}
	if ((tokenList->at(index-1)).tp!=_SEMI)
	{
		errorList->push_back("miss ';' at line "+ itos(token.lineno-1));
		parse_err = true;
	}
	printf_skip_err=true;
	check_input(appendVector(synchset,followset),firstset);
	printf_skip_err = false;
	return t;
}


/*
*<expression>::=<additive_expression>[(>|<|==|<>)<additive_expression>]
*firstset _ID _LSPAREN _MINUS _PLUS _NUM
*followset _PLUS _MINUS
*/
TreeNode* expression(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "expression";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_LSPAREN);
	firstset.push_back(_MINUS);
	firstset.push_back(_PLUS);
	firstset.push_back(_ID);
	firstset.push_back(_RNUM);
	firstset.push_back(_INUM);
	if (check_input(firstset,synchset)==2)
	{
		return NULL;
	}
	else{
		temp = additive_expression(appendVector(synchset,followset));
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
		_TokenType tp = token.tp;
		if(token.tp==_LT||token.tp==_BT||token.tp==_NE||token.tp==_EQ)
		{
			string tv = token.tv;
			match(token.tp,t);
			temp = additive_expression(appendVector(synchset,followset));
			if (temp!=NULL)
			{
				t->addChild(temp);
			}
			else{
				parse_err = true;
				errorList->push_back("unexcept token '"+tv+"' at line "+ itos(token.lineno));
			}
			int i = 0;
			//判断操作的类型
			switch(tp)
			{
			case _LT:
				i = 4;
				break;
			case _BT:
				i = 5;
				break;
			case _EQ:
				i = 6;
				break;
			case _NE:
				i = 7;
				break;
			}
			code->push_back("OPR "+itos(i));
			codeAddress++;
			//弹出2个操作数的类型
			data_type->pop_back();
			data_type->pop_back();
			//bool运算的结果的类型为int
			data_type->push_back(0);
		}
		//if(check_input(followset,firstset)!=0){
		//	errorList->push_back("unexcept token before '"+token.tv+"' at line "+itos(token.lineno));
		//}
	}
	//如果只有一个子节点,子节点上移,为了减少输出树的深度
	if (t->children->size()==1)
	{
		t = t->children->at(0);