parse.cpp

一个类c语言的解释器

	firstset.push_back(_INT);
	firstset.push_back(_REAL);
	firstset.push_back(_RSPAREN);
	followset.push_back(_RSPAREN);
	followset.push_back(_LBPAREN);

	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "params";
	//函数没有参数,返回
	if (token.tp==_RSPAREN||token.tp==_LBPAREN)
	{
		return NULL;
	}
	//函数的参数为int型
	if (token.tp==_INT)
	{
		match(_INT,t);
		//函数表中添加函数参数的类型
		fun->args->push_back(0);
		//在局部变量中声明一个int型的变量
		//code->push_back("INT 1");
		//codeAddress++;
		//当前符号的类型为int
		symbol->type=0;
		//设置当前符号的地址
		symbol->address="SP+"+itos(local_address);
		local_address++;
	}
	//函数的参数为real型
	else if(token.tp==_REAL){
		match(_REAL,t);
		//函数表中添加函数参数的类型
		fun->args->push_back(1);
		//在局部变量中声明一个real型的变量
		//code->push_back("REAL 1");
		//codeAddress++;
		//设置符号的类型和符号的地址
		symbol->type=1;
		symbol->address="SP+"+itos(local_address);
		local_address++;
	}
	//如果参数没有类型,报错
	else{
		parse_err = true;
		errorList->push_back("miss of type identifier at line "+itos(token.lineno));
	}
	//设置当前符号的id和size
	symbol->id = token.tv;
	symbol->size = 1;
	//把函数的参数当作一个局部变量,插入符号表
	if(sym->contain(token.tv)){
		parse_err = true;
		errorList->push_back("identifier '"+token.tv+"'at line "+itos(token.lineno)+" redefine");
	}
	else{
		sym->insert(symbol);
		symbol = new Symbol;
	}
	match(_ID,t);
	/*if (token.tp==_LSPAREN)
	{
	match(_LSPAREN,t);
	match(_RSPAREN,t);
	}*/
	//如果下一个符号为','循环的读取参数
	while (token.tp==_COMMA)
	{
		match(_COMMA,t);
		if (token.tp==_INT)
		{
			match(_INT,t);
			//函数表中添加函数参数的类型
			fun->args->push_back(0);
			//在局部变量中声明一个int型的变量
			//code->push_back("INT 1");
			//codeAddress++;
			//当前符号的类型为int
			symbol->type=0;
			//设置当前符号的地址
			symbol->address="SP+"+itos(local_address);
			local_address++;
		}
		//函数的参数为real型
		else if(token.tp==_REAL){
			match(_REAL,t);
			//函数表中添加函数参数的类型
			fun->args->push_back(1);
			//在局部变量中声明一个real型的变量
			//code->push_back("REAL 1");
			//codeAddress++;
			//设置符号的类型和符号的地址
			symbol->type=1;
			symbol->address="SP+"+itos(local_address);
			local_address++;
		}
		//缺少参数类型,报错
		else{
			parse_err = true;
			errorList->push_back("miss of type identifier at line "+itos(token.lineno));
		}
		//设置参数的id和大小
		symbol->id = token.tv;
		symbol->size = 1;
		//把参数当作局部变量插入符号表
		if(sym->contain(token.tv)){
			parse_err = true;
			errorList->push_back("identifier '"+token.tv+"'at line "+itos(token.lineno)+" redefine");
		}
		else{
			sym->insert(symbol);
			symbol = new Symbol;
		}
		match(_ID,t);
		/*if (token.tp==_LMPAREN)
		{
		match(_LMPAREN,t);
		match(_RMPAREN,t);
		}*/
	}
	if(check_input(followset,followset)!=0){
		errorList->push_back("unexcept token before '"+token.tv+" at "+ itos(token.lineno)+" ' lost ','?");
	}
	else if (token.tp==_LBPAREN)
	{
		errorList->push_back("miss ')' before '{' at line "+ itos(token.lineno));
	}
	//sym = sym->parent;
	//delete ts;
	return t;
}

/*
*<compound_stmt>::={<statement_list>}
*firstset _LBPAREN
*
*/
TreeNode* compound_stmt(vector<_TokenType> synchset){
	int temp_address = local_address;
	SymTable* ts = new SymTable;
	ts->parent = sym;
	sym = ts;
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "compound_stmt";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_LBPAREN);
	int tempindex = index;
	if(check_input(firstset,synchset)==0){
		match(_LBPAREN,t);
		temp = statement_list(appendVector(synchset,followset));
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
		match(_RBPAREN,t);
		check_input(synchset,firstset);
	}
	else{
		errorList->push_back("miss '{' before '"+(tokenList->at(tempindex)).tv + "' at line "+itos((tokenList->at(tempindex)).lineno));
		index = tempindex--;
		token.tp=_LBPAREN;
		token.tv="{";
		token.lineno = tokenList->at(index+1).lineno;
		parse_err = true;
		return compound_stmt(appendVector(synchset,followset));
	}
	ts = sym;
	sym = sym->parent;
	//map<string,Symbol*>::iterator it = ts->table->begin();
	//map<string,Symbol*>::iterator end = ts->table->end();
	/*if(it->second!=NULL)
	for (;it!=end;it++)
	{
	for (int k=0;k<it->second->size;k++)
	{
	code->push_back("POP");
	codeAddress++;
	local_address--;
	}
	}*/
	while(temp_address<local_address)
	{
		code->push_back("POP");
		codeAddress++;
		local_address--;
	}
	delete ts;
	return t;
}

/*
*<statement_list>::={<statement>}
*
*
*/
TreeNode* statement_list(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "statement_list";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_ID);
	firstset.push_back(_IF);
	firstset.push_back(_WHILE);
	firstset.push_back(_READ);
	firstset.push_back(_WRITE);
	firstset.push_back(_LBPAREN);
	firstset.push_back(_RETURN);
	firstset.push_back(_RBPAREN);
	firstset.push_back(_INT);
	firstset.push_back(_REAL);
	followset.push_back(_RBPAREN);
	check_input(firstset,synchset);
	while (token.tp==_ID||token.tp==_IF||token.tp==_WHILE||token.tp==_READ||token.tp==_WRITE||token.tp == _RETURN||token.tp==_INT||token.tp==_REAL)
	{
		temp = statement(appendVector(synchset,followset));
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
	}
	//逻辑变量地址的差就是在该函数块里面声明的逻辑变量的个数,函数块结束侯,把他们一次弹出
	return t;
}

/*
*<statement>::=(<assign_exp>)|(<selection_exp>)|(<iteration_exp>)|(<read_exp>)|(<write_exp>)|(<return_exp>)|(<call>)|(<local_var_declaration>)
*firstset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*followset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*/
TreeNode* statement(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "statement";
	switch(token.tp)
	{
	case _INT:
	case _REAL:
		t = local_var_declaration(synchset);
		break;
	case _ID:
		if ((tokenList->at(index+1)).tp==_LSPAREN)
		{
			if (funs->get_fun(token.tv)==NULL)
			{
				Function * fun = new Function;
				parse_err = true;
				errorList->push_back("Line "+itos(token.lineno)+" function '"+token.tv+"' can,t be found");
				fun->id = token.tv;
				funs->insert(fun);
			}
			string s = "CALL "+funs->get_fun(token.tv)->address;
			t = call(synchset);
			code->push_back(s);
			codeAddress++;

			//函数调用结束后,当前数据栈顶的值为函数返回值,无用,弹出
			code->push_back("POP");
			codeAddress++;
			match(_SEMI,t);
		}
		else{
			t=assign_exp(synchset);
		}
		break;
	case _IF:
		t=selection_exp(synchset);
		break;
	case _WHILE:
		t=iteration_exp(synchset);
		break;
	case _READ:
		t=read_exp(synchset);
		break;
	case _WRITE:
		t=write_exp(synchset);
		break;
	case _RETURN:
		t = return_exp(synchset);
		break;
	}
	return t;
}

/*
*<var>::=ID[[<expression>]]
*firstset _ID
*followset _SIMI
*/
TreeNode* var(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "var";
	TokenRecord id = token;
	match(_ID,t);
	//保存当前符号
	Symbol* s  = sym->find(id.tv);
	//使用数组
	if (token.tp==_LMPAREN)
	{
		//如果操作的变量不是数组,打印错误
		if(!s->isarr&&!s->isfun){
			parse_err = true;
			errorList->push_back("identifier '"+s->id+"' at line "+itos(id.lineno)+" is a nuber but used as array");
		}
		synchset.push_back(_RMPAREN);
		match(_LMPAREN,t);
		temp = expression(synchset);
		//判断数组的下标是否为整数
		//此时,数组的下标保存在栈顶
		if (data_type->at(data_type->size()-1)!=0)
		{
			parse_err = true;
			errorList->push_back("array index at line "+itos(token.lineno)+" must be a integer");

		}
		//弹出数组下标类型
		data_type->pop_back();
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
		else{
			errorList->push_back("miss expression after '[' at line " + itos(token.lineno));
		}
		match(_RMPAREN,t);
		//读取数组首地址和栈顶的值来获取操作的数组项的地址
		code->push_back("LOD "+s->address+"+[TOP]");
		codeAddress++;
	}
	else{
		//变量使用
		//如果该变量是数组,报错
		if(s->isarr&&!s->isfun){
			parse_err = true;
			errorList->push_back("identifier '"+s->id+"' at line "+itos(id.lineno)+" is a number but used as array");
		}
		//把该变量的值提取到数据栈顶
		code->push_back("LOD "+s->address);
		codeAddress++;
	}
	//当前的符号的类型入类型栈
	//data_type->push_back(type);
	return t;
}

/*
*<assign_exp>::=ID[[<expression>]]=<expression>;
*firstset _ID
*followset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*/
TreeNode* assign_exp(vector<_TokenType> synchset){
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "assign_exp";
	firstset.push_back(_ID);
	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);
	//判断当前赋值的语句是否为数组项
	//初始化为非数组项
	bool isArr = false;
	if(check_input(firstset,synchset)==0){
		TokenRecord id = token;
		match(_ID,t);
		if (sym->find(id.tv)==NULL)
		{
			parse_err = true;
			errorList->push_back("identifier '"+id.tv+"' at line "+itos(id.lineno)+" used without been declare");
			symbol->id = id.tv;
			sym->insert(symbol);
			symbol = new Symbol;
		}
		string address = sym->find(id.tv)->address;
		if (token.tp==_LMPAREN)
		{
			//如果该变量不是数组,出错
			if(!sym->find(id.tv)->isarr){
				parse_err = true;
				errorList->push_back("identifier '"+id.tv+"' at line "+itos(id.lineno)+"is not a array ,but used as array");
			}
			//设置当前赋值的变量为数组
			isArr = true;
			match(_LMPAREN,t);
			followset.push_back(_RMPAREN);
			temp = expression(appendVector(synchset,followset));
			//检查表达式的下标是否为整型,不是整型则报错
			if (data_type->at(data_type->size()-1)!=0)
			{
				parse_err=true;
				errorList->push_back("array index must be a integer at line "+itos(id.lineno));
			}
			data_type->pop_back();
			if (temp!=NULL)
			{
				t->addChild(temp);
			}
			else{
				errorList->push_back("miss expression after '[' at line " + itos(token.lineno));
			}
			match(_RMPAREN,t);
		}
		else{
			if(sym->find(id.tv)->isarr||sym->find(id.tv)->isfun){
				parse_err = true;
				errorList->push_back("identifier '"+id.tv+"' at line "+itos(id.lineno)+"must be a number variable");
			}
		}
		match(_ASSIGN,t);
		synchset.push_back(_SEMI);
		temp = expression(appendVector(synchset,followset));
		//检查右边表达式的类型是否和左边要赋值的变量的值兼容,不兼容则报错
		if (sym->find(id.tv)->type<data_type->at(data_type->size()-1))
		{
			parse_err = true;
			errorList->push_back("can't cast right-hand expression from 'real' to 'int' at line "+itos(id.lineno));
		}
		else{
			//如果是数组,通过数组首地址和数据栈顶值可以得到要赋值的地址
			//把栈顶值保存再此地址中
			if (isArr)
			{
				code->push_back("STO "+sym->find(id.tv)->address+"+[TOP]");
				codeAddress++;
			}
			//如果是变量,把数据栈顶的值保存再变量地址中
			else{
				code->push_back("STO "+sym->find(id.tv)->address);
				codeAddress++;
			}
		}
		data_type->pop_back();
		if (temp!=NULL)
		{
			t->addChild(temp);
		}
		else{
			errorList->push_back("miss expression after '=' at line " + itos(token.lineno));
		}
		match(_SEMI,t);
		check_input(appendVector(synchset,followset),firstset);
	}
	return t;
}

/*
*<selection_exp>::=if(<expression>)<compound_stmt>[else <compound_stmt>]
*firstset _IF
*followset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*/
TreeNode* selection_exp(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "selection_exp";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_IF);
	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(_IF,t);
	match(_LSPAREN,t);
	synchset.push_back(_RSPAREN);
	//判断的bool表达式的值
	temp = expression(appendVector(synchset,followset));
	data_type->pop_back();
	//保存回填的代码地址
	//如果bool表达式为假时,跳转
	int backfill1 = code->size();
	code->push_back("");
	codeAddress++;
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	else{
		errorList->push_back("miss expression after '(' at line " + itos(token.lineno));
	}
	match(_RSPAREN,t);
	followset.push_back(_ELSE);
	//if体
	temp = compound_stmt(appendVector(synchset,followset));
	followset.pop_back();
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	//if体执行结束,跳转到else体后面
	//设置第二个回填的地址
	int backfill2 = code->size();
	code->push_back("");
	codeAddress++;
	//回填if语句体最前方的跳转
	code->at(backfill1)="JPC "+itos(codeAddress);
	if (token.tp==_ELSE)
	{
		match(_ELSE,t);
		temp = compound_stmt(appendVector(synchset,followset));
		if (temp!=NULL)
		{
			t->addChild(temp);
		}	
	}
	//回填if体结束的时候的跳转
	code->at(backfill2)="JMP "+itos(codeAddress);
	check_input(appendVector(synchset,followset),firstset);
	return t;
}

/*
*<iteration_exp>::=while(expression)<compound_stmt>
*firstset _WHILE
*followset _RBPAREN _INT _REAL _ID _IF _WHILE _READ _WRITE _RETURN
*/
TreeNode* iteration_exp(vector<_TokenType> synchset){
	TreeNode* t = new TreeNode;
	TreeNode* temp = new TreeNode;
	t->describe = "iteration_exp";
	vector<_TokenType> firstset;
	vector<_TokenType> followset;
	firstset.push_back(_WHILE);
	followset.push_back(_RSPAREN);
	match(_WHILE,t);
	match(_LSPAREN,t);
	//保存while的首地址
	int address = codeAddress;
	temp = expression(appendVector(synchset,followset));
	data_type->pop_back();
	//保存回填的代码地址
	//如果bool表达式为假时,跳转,不执行while体
	int backfill = code->size();
	code->push_back("");
	codeAddress++;
	if (temp!=NULL)
	{
		t->addChild(temp);
	}
	else{
		errorList->push_back("miss expression after '(' at line " + itos(token.lineno));
	}
	match(_RSPAREN,t);
	followset.push_back(_ID);
	followset.push_back(_IF);
	followset.push_back(_WHILE);
	followset.push_back(_READ);
	followset.push_back(_WRITE);
	followset.push_back(_RETURN);