parse.cpp

一个类c语言的解释器

		t->describe = "expression";
	}
	return t;
}


/*
*<additive_expression>::=<term>{(+|-)<term>]
*firstset _ID _LSPAREN _MINUS _PLUS _NUM
*followset _PLUS _MINUS
*/
TreeNode* additive_expression(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	vector<_TokenType>followset;
	followset.push_back(_PLUS);
	followset.push_back(_MINUS);
	t->describe = "additive_expression";
	temp = term(appendVector(synchset,followset));
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	else{
		//return NULL;
	}
	while (token.tp==_PLUS||token.tp==_MINUS)
	{
		_TokenType tp = token.tp;
		string tv = token.tv;
		if (token.tp==_PLUS)
		{
			match(_PLUS,t);
		}
		else if (token.tp==_MINUS)
		{
			match(_MINUS,t);
		}
		temp = term(appendVector(synchset,followset));
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
		else{
			errorList->push_back("unexcept token '"+tv+"' at line "+ itos(token.lineno));
			return NULL;
		}
		if (tp==_PLUS)
		{
			code->push_back("OPR 0");
		}
		else{
			code->push_back("OPR 1");
		}
		codeAddress++;
		//计算并保存运算结果的类型
		int i = data_type->at(data_type->size()-1);
		data_type->pop_back();
		i = i||data_type->at(data_type->size()-1);
		data_type->pop_back();
		data_type->push_back(i);
	}
	if (t->children->size()==1)
	{
		t = t->children->at(0);
		t->describe = "additive_expression";
	}
	return t;
}

/*
*<term>::=<factor>{(*|/)<factor>}
*firstset _ID _LSPAREN _MINUS _PLUS _NUM
*followset _DIV _MUL
*/
TreeNode* term(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	vector<_TokenType>followset;
	followset.push_back(_DIV);
	followset.push_back(_MUL);
	t->describe = "term";
	negative = false;
	if (token.tp==_PLUS)
	{
		match(_PLUS,t);
	}
	else if (token.tp==_MINUS)
	{
		//判断该term是否应该再前面加负号
		match(_MINUS,t);
		negative=!negative;
	}
	temp = factor(appendVector(synchset,followset));
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	else{
		//return NULL;
	}
	while (token.tp==_MUL||token.tp==_DIV)
	{
		_TokenType tp = token.tp;
		string tv = token.tv;
		if (token.tp==_MUL)
		{
			match(_MUL,t);
		}
		else if (token.tp==_DIV)
		{
			match(_DIV,t);
		}
		if (token.tp==_PLUS)
		{
			match(_PLUS,t);
		}
		else if (token.tp==_MINUS)
		{
			match(_MINUS,t);
			negative=!negative;
		}
		temp = factor(appendVector(synchset,followset));
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
		else{
			errorList->push_back("unexcept token '"+tv+"' at line "+ itos(token.lineno));
		}
		if (tp == _MUL)
		{
			code->push_back("OPR 2");
		}
		else{
			code->push_back("OPR 3");
		}
		codeAddress++;
		//计算并保存运算结果的类型
		int i = data_type->at(data_type->size()-1);
		data_type->pop_back();
		i = i||data_type->at(data_type->size()-1);
		data_type->pop_back();
		data_type->push_back(i);
	}
	if (t->children->size()==1)
	{
		t = t->children->at(0);
		t->describe = "term";
	}
	//如果应该再该term前面加负号,则对栈顶元素取相反数
	if(negative){
		code->push_back("NEG");
		codeAddress++;
	}
	return t;
}

/*
*<factor>::=NUM|((<expression>))|<var>|<call>
*firstset _ID _LSPAREN _MINUS _PLUS _NUM
*followset _BT _LT _NE _EQ
*/
TreeNode* factor(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "factor";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_LSPAREN);
	firstset.push_back(_ID);
	firstset.push_back(_INUM);
	firstset.push_back(_RNUM);

	followset.push_back(_BT);
	followset.push_back(_LT);
	followset.push_back(_NE);
	followset.push_back(_EQ);
	if (check_input(firstset,appendVector(synchset,followset))!=0)
	{
		errorList->push_back("too much operator before '"+token.tv+"' at line "+ itos(token.lineno));
		//return NULL;
	}
	//因子为(exp)
	if (token.tp==_LSPAREN)
	{
		match(_LSPAREN,t);
		followset.push_back(_RSPAREN);
		temp=expression(appendVector(synchset,followset));
		//data_type->pop_back();
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
		else{
			errorList->push_back("miss expression after '[' at line " + itos(token.lineno));
		}
		match(_RSPAREN,t);
	}
	//因子为整数
	else if (token.tp==_INUM)
	{
		//设置数据类型
		data_type->push_back(0);
		code->push_back("LIT "+itos(0)+" "+token.tv);
		codeAddress++;
		match(_INUM,t);

	}
	//因子为实数
	else if (token.tp==_RNUM)
	{
		//设置因子数据类型
		data_type->push_back(1);
		code->push_back("LIT "+itos(1)+" "+token.tv);
		codeAddress++;
		match(_RNUM,t);

	}

	else{
		if (sym->find(token.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;
		}
		//因子为函数调用,id后面有小括号
		if ((tokenList->at(index+1)).tp==_LSPAREN)
		{
			//判断函数是否存在,不存在则出错
			if(funs->get_fun(token.tv)==NULL){
				parse_err=true;
				errorList->push_back("identifier "+token.tv+"at line"+itos(token.lineno)+"is a variable, but used as a function");
				Function * fun = new Function;
				fun->id = token.tv;
				funs->insert(fun);
			}
			//获取函数的返回地址
			string address = funs->get_fun(token.tv)->address;
			//设置因子的数据类型
			data_type->push_back(funs->get_fun(token.tv)->type);
			//调用函数
			temp = call(appendVector(synchset,followset));
			code->push_back("CALL "+address);
			codeAddress++;
			if (temp!=NULL)
			{
				t->addChild(temp);
			}
		}
		//因子为变量,id后面没有小括号
		else{
			//如果因子是函数,出错
			if(sym->find(token.tv)->isfun){
				parse_err=true;
				errorList->push_back("identifier "+token.tv+"at line"+itos(token.lineno)+"is a function, but used as a variable");
			}
			//设置因子的类型
			data_type->push_back(sym->find(token.tv)->type);
			temp = var(appendVector(synchset,followset));
			if (temp!=NULL)
			{
				t->addChild(temp);
			}
		}
	}
	//check_input(followset,firstset);
	/*if (t->children->size()==1)
	{
	t = t->children->at(0);
	if (t->type==NULL)
	{
	t->describe = "factor";
	}
	}*/
	return t;
}


/*
*<call>::=ID(<args>);
*firstset _ID
*followset
*/
TreeNode* call(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "call";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_LSPAREN);
	firstset.push_back(_ID);
	firstset.push_back(_INUM);
	firstset.push_back(_RNUM);
	followset.push_back(_SEMI);
	if (check_input(firstset,synchset)==2)
	{
		return NULL;
	}
	//判断标识符是否为函数,不是则出错
	if(funs->get_fun(token.tv)==NULL){
		parse_err = true;
		errorList->push_back("function ,"+token.tv+"' called at line "+itos(token.lineno)+" used without declare");
		return NULL;
	}
	match(_ID,t);
	match(_LSPAREN,t);
	//递归调用参数处理函数
	temp = args(appendVector(synchset,followset));
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	match(_RSPAREN,t);
	check_input(appendVector(synchset,followset),firstset);
	return t;
}
/*
*<args>::=(void)|(<expression>[,<expression>])
*firstset _ID _NUM _RSPAREN
*followset _RSPAREN
*/
TreeNode* args(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "args";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_ID);
	firstset.push_back(_INUM);
	firstset.push_back(_RNUM);
	firstset.push_back(_RSPAREN);
	followset.push_back(_RSPAREN);
	followset.push_back(_LBPAREN);
	//获取当前调用的函数
	TokenRecord tk = tokenList->at(index-2);
	Function* fun = funs->get_fun(tokenList->at(index-2).tv);
	//如果函数为空,出错
	if(fun==NULL){
		return NULL;
	}
	int check = check_input(firstset,followset);
	if (check == 2)
	{
		return NULL;
	}
	else if (check==1)
	{
		errorList->push_back("unexcept token before '"+token.tv+"' at line "+itos(token.lineno));
	}
	//参数列表为空
	if (token.tp==_RSPAREN)
	{
		if (fun->args->size()==0)
		{
			return NULL;
		}
		//如果函数表中参数列表不为空,出错
		else{
			parse_err = true;
			errorList->push_back("too few arguments while call '"+fun->id+"' at line "+itos(token.lineno));
			return NULL;
		}
	}
	//参数列表不为空,计算第一个参数
	temp = expression(appendVector(synchset,followset));
	//获取第一个参数的类型
	int type = data_type->at(data_type->size()-1);
	data_type->pop_back();
	//参数的编号
	int arg_index = 0;
	//比较参数的数据类型,看是否能够兼容,不能兼容则出错
	if (arg_index<fun->args->size())
	{
		if (fun->args->at(arg_index++) < type)
		{
			parse_err = true;
			errorList->push_back("can't cast argument "+itos(arg_index)+" from 'real' to 'int' at line "+itos(token.lineno));
		}
	}
	//如果参数的编号大于函数表中参数的个数,出错,参数过多
	else{
		parse_err = true;
		errorList->push_back("too many arguments while call '"+fun->id+"' at line "+itos(token.lineno));
	}
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	//遇到','读取下一个参数
	while (token.tp==_COMMA)
	{
		match(_COMMA,t);
		//读取下一个参数
		temp = expression(appendVector(synchset,followset));
		//保存参数类型
		type = data_type->at(data_type->size()-1);
		data_type->pop_back();
		//判断参数是否匹配
		if (arg_index<fun->args->size())
		{
			if (type < fun->args->at(arg_index++))
			{
				parse_err = true;
				errorList->push_back("can't cast argument "+itos(arg_index)+" from 'real' to 'int'");
			}
		}
		//如果参数过多,出错
		else{
			parse_err = true;
			errorList->push_back("too many arguments while call '"+fun->id+"' at line "+itos(token.lineno));
		}
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
	}
	if (arg_index<fun->args->size())
	{
		parse_err=true;
		errorList->push_back("too few arguments while call "+fun->id+" at line "+itos(token.lineno));
	}
	check = check_input(appendVector(synchset,followset),firstset);
	if (check==2)
	{
		errorList->push_back("miss ',' before '"+token.tv+"' at line "+itos(token.lineno));
		token.tp=_COMMA;
		token.tv=",";
		index--;
		parse_err = true;
	}
	else if (check!=0)
	{
		errorList->push_back("unexcept token before '"+token.tv+"' at line "+itos(token.lineno));
		if (token.tp==_LBPAREN)
		{
			errorList->push_back("miss ')' before '"+token.tv+"' at line "+itos(token.lineno)+" ?");
		}
	}
	code->push_back("LIT 0 "+itos(fun->args->size()));
	return t;
}


/*
*<num_list>::=NUM{,NUM}
*firstset _NUM
*followset _RBPAREN
*/
TreeNode* num_list(){
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	int count = currArraySize;
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "num_list";
	firstset.push_back(_INUM);
	firstset.push_back(_RNUM);
	followset.push_back(_RBPAREN);
	if (check_input(firstset,followset)==2)
	{
		return NULL;
	}
	if (count==0)
	{

	}
	type = symbol->type;
	if (type==0)
	{
		match(_INUM,t);
		code->push_back("LIT 0 "+tokenList->at(index-1).tv);
	}
	else{

		if(token.tp==_RNUM){
			match(_RNUM,t);
			code->push_back("LIT 1 "+tokenList->at(index-1).tv);
		}
		else{
			match(_INUM,t);
			code->push_back("LIT 1 "+tokenList->at(index-1).tv);
		}
	}
	codeAddress++;
	count--;
	while (token.tp==_COMMA)
	{
		if (count==0)
		{
			errorList->push_back("too many number while initialize array at line "+ itos(token.lineno));
			parse_err = true;
			break;
		}
		match(_COMMA,t);
		if (type==0)
		{
			match(_INUM,t);
			code->push_back("LIT 0 "+tokenList->at(index-1).tv);
		}
		else{
			if(token.tp==_RNUM){
				match(_RNUM,t);
				code->push_back("LIT 1 "+tokenList->at(index-1).tv);
			}
			else{
				match(_INUM,t);
				code->push_back("LIT 1 "+tokenList->at(index-1).tv);
			}
		}
		count--;
		codeAddress++;
	}
	check_input(followset,firstset);
	initNums = currArraySize - count;
	return t;
}
/*
*<progrem >::= <declaration_list>
*/
TreeNode* parse(){
	data_type = new vector<int>;
	global_init = new vector<string>;
	code = new vector<string>;
	code->push_back("LIT 0 0");
	codeAddress++;
	code->push_back("");
	codeAddress++;
	code->push_back("EXIT");
	codeAddress++;
	data = new vector<string>;
	printf_skip_err = false;
	sym = new SymTable;
	symbol = new Symbol;
	funs = new FunTable;
	fun = new Function;
	TreeNode* t =  declaration_list();
	//设置mian函数的参数个数
	//data->push_back("LIT 0 0");
	if(funs->get_fun("main")!=NULL){
		//main函数参数不正确,main函数不能哟也参数
		if(funs->get_fun("main")->args->size()!=0){
			parse_err = true;
			errorList->push_back("main didn't take params");
		}
		else if(funs->get_fun("main")->type!=0){
			parse_err = true;
			errorList->push_back("The return type of main function must be 'integer'");
		}
		else{
			code->at(1) = "CALL "+funs->get_fun("main")->address;
		}
	}
	//找不到main函数
	else{
		parse_err = true;
		errorList->push_back("can't find the main function");
	}
	return t;
}