某次作业

balabala.cpp

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<iomanip>
#include<cstdlib>
using namespace std;

//#define DEBUG

#ifdef DEBUG
	#define  printPos(func) {  cout<<func<<endl; }
	#define debug(info) {  cout<<info<<endl; }
	#define printFilePos { const char *p = file_str.c_str();  cout<<(p + pos)<<endl; }
	#define printVarS	{\
							cout<<"varS is"<<endl;\
							for (auto i = Q.varS.begin(); i != Q.varS.end(); ++i) { \
								cout<<(*i)<<" "; \
							} \
							cout<<endl;\
						}
#else
	#define  printPos(func) {  }
	#define debug(info) {  }
	#define printFilePos {  }
	#define printVarS { }
#endif


#define pushAlpha 	{ \
						string i = "a";\
						while (i[0] <= 'z') {\
							inTable.push_back(i);\
							++(i[0]);\
						}\
					}
#define pushDigit 	{ \
						string i = "0";\
						while (i[0] <= '9') {\
							inTable.push_back(i);\
							++(i[0]);\
						}\
					}
struct {
	string Model,Info;
	int pos;
	bool handle;
	int cnt;
} Error;
class vectorRev{
public:
	vector<string> _S;
	string operator[](int pos){
		if( Error.cnt || pos >= int(_S.size()) ){
			return string("Error");
		}
		else{
			return _S[pos];
		}
	}
	void push_back(string str){
		_S.push_back(str);
	}
	void pop_back(){
		if(_S.size()) _S.pop_back();
	}
	int size(){
		return _S.size();
	}
};

class Quatriple{
public:
	struct Node{
		string op,arg1,arg2,result;
		Node(string _op,string _arg1, string _arg2, string _result):op(_op), arg1(_arg1), arg2(_arg2), result(_result){}
	};
private:
	vector<int> fillBack;
	vector<int> IfPos,WhileCPos;
	vector<Node> S;
	int index,length,tempIndex;
public:
	vectorRev varS;
	Quatriple(){
		index = length = tempIndex = 0;
	}
	void clear(){
		fillBack.clear();
		S.clear();
		index = length = tempIndex = 0;
	}
	void build( string op,string arg1 = "",string arg2 = "",string result = ""){
		S.push_back( Node(op, arg1, arg2, result) );
		++index;
	}
	int getIndex(){
		return index;
	}
	string getTempVar(){
		char buffer[10];
		sprintf(buffer, "t%d", tempIndex);
		++tempIndex;
		return string(buffer);
	}
	void setFillBackPos(){
		debug("setFillBackPos");
		debug(index);
		fillBack.push_back(index);
	}
	void setFillBack(){
		debug("fillBack size");debug(fillBack.size());
		int pos = fillBack[fillBack.size() - 1];
		char buffer[10];
		sprintf(buffer, "<%d>", index + 1);
		debug("fillBack pos");debug(pos);
		S[pos].result = buffer;
		fillBack.pop_back();
	}
	void setFillBackIf(){
		int pos = fillBack[fillBack.size() - 1];
		char buffer[10];
		sprintf(buffer, "<%d>", index);
		S[pos].result = buffer;
		//fillBack.pop_back();
		fillBack.pop_back();
	}
	/*
	int getFillBackPos(){
		debug("fillBack size");debug(fillBack.size());
		int pos = fillBack[fillBack.size() - 1];
		fillBack.pop_back();
		return pos;
	}
	*/
	void setIfGotoPos(){
		IfPos.push_back(index);
	}
	void setIfGoto(){
		char buffer[10];
		int pos = IfPos[IfPos.size() - 1];
		sprintf(buffer, "<%d>", index);
		S[pos].result = buffer;
		IfPos.pop_back();
	}
	void setWhileCPos(){
		WhileCPos.push_back(index);
	}
	void setWhileC(){
		char buffer[10];
		int pos = WhileCPos[WhileCPos.size() - 1];
		sprintf(buffer, "<%d>", pos);
		this->build("GOTO", "","", buffer );
		WhileCPos.pop_back();
	}
	void printNode(){
		int i = 0;
		cout<<"S size is "<<S.size()<<endl;
		for (auto iterator = S.begin(); iterator != S.end(); iterator++) {
			cout << setw(5) << (i++) << '|'
				 << setw(5) << iterator->op  
				 << setw(8) << iterator->arg1  
				 << setw(8) << iterator->arg2 
				 << setw(8) << iterator->result
				 <<endl;
		}
	}
} Q;


vector<string> varTable;

void printVar(){
	cout<<"varTable size is "<<varTable.size()<<endl;
	for (auto iterator = varTable.begin(); iterator != varTable.end(); iterator++) {
		cout << (*iterator) <<endl;
	}
}

string file_str;
int pos,getSymbolEndPos,C,L;


void iniFile(string fileName);
void iniError();
void printError();
string getSymbol(vector<string> table);
void skipNone();
void _skipNone();
void p_main();
void p_programe();
void p_varTable();
string get_varSymbol();
void p_varSymbol();
void p_varSymbolCheck(string varName);
void p_statementPart();
void p_statement();
void p_assignment();
void p_condition();
void p_expression();
void p_item();
enum factorType {
	TvarSym,
	Tconst,
	Texp,
	Tother
};
factorType get_factorType();
void p_factor();
void p_const();
void p_relationship();
string revRelationship( string r );
void p_mulStatement();
void p_statement1();
void p_if();
void p_while();


void iniFile(string fileName){
	ifstream is (fileName);
	if(is.is_open()){
		pos = 0;
		char buffer[10000];
		is.read(buffer, 9998);
		file_str = buffer;
		is.close();
	}
	else{
		cout<<"can not open file"<<endl;
	}
}


void iniError(){
	Error.cnt = 0;
	Error.pos = 0;
	Error.handle = true;
}
void printError(){
	if(Error.handle == false){
		char buffer[100];
		sprintf(buffer, "%s  %s  在%d行%d列", Error.Model.c_str(), Error.Info.c_str(), L + 1 , C );
		cout<<buffer<<endl;
		Error.handle = true;
		Error.cnt++;
	}
}

/*
* table 一个可接受的输入表，总是返回第一个匹配
*/
string getSymbol(vector<string> table){
	skipNone();
	int i = 0,i_end = table.size();
	string ret;
	while ( i != i_end ) {
		int j = 0, j_end = table[i].length();
		while(file_str[pos + j] == table[i][j]) ++j;
		if( j == j_end ) {
			ret = table[i];
			getSymbolEndPos = pos + j;
			return ret;
		}
		++i;
	}
	Error.Info = "getSymbol Error , 没有匹配到的输入";
	return ret;
}
void skipNone(){
	//cout<<"---------ship begin----------"<<endl;
	//printFilePos;
	_skipNone();_skipNone();//_skipNone();_skipNone();
	//cout<<"---------ship end----------"<<endl;
	//printFilePos;
	//cout<<"---------ship out----------"<<endl;
}
void _skipNone(){
	bool mark = true;
	while ( mark ) {
		switch ( file_str[pos] ) {
		case '\n': ++L;C = 0;
		case '\r':
		case '\t':
		case ' ' : ++pos;++C;
			  break;
		default:
			mark = false;
		}
	}
}
//<程序>::＝main（）{<分程序>}
void p_main(){
	printPos(__FUNCTION__);
	
	string symbol;
	vector<string> inTable;

	inTable.push_back("main()");
	symbol = getSymbol(inTable);
	pos = getSymbolEndPos;
	inTable.clear();
	//debug("after main");
	inTable.push_back("{");
	symbol = getSymbol(inTable);
	inTable.clear();
	pos = getSymbolEndPos;
	p_programe();
	/*
	inTable.push_back("}");
	symbol = getSymbol(inTable);
	inTable.clear();
	pos = getSymbolEndPos;
	*/
}
//<分程序>::=<变量说明部分>；<语句部分>
void p_programe(){
	printPos(__FUNCTION__);
	
	string symbol;
	vector<string> inTable;

	inTable.push_back("int");
	symbol = getSymbol(inTable);
	inTable.clear();

	if(symbol == "int"){
		pos = getSymbolEndPos;
		p_varTable();
	}
	else{
		//Error
		printFilePos;
		Error.Model = "解析符号表";
		Error.Info = "未找到符号表";
		Error.handle = false;
		printError();
	}
	p_statementPart();
}
//<变量说明部分>::=<变量说明><标识符表>
//<变量说明>::=int
//<标识符表>::=<标识符>，<标识符表>
//<标识符表>::=<标识符>
void p_varTable(){
	printPos(__FUNCTION__);
	
	Error.Model = "解析标识符表";
	
	string symbol;
	vector<string> inTable;
	
	inTable.push_back(";");
	inTable.push_back(",");
	p_varSymbol();
	debug("第一次解析标识符结束");
	int mark = true;
	while (mark) {
		symbol = getSymbol(inTable);
		if ( symbol == ",") {
			pos = getSymbolEndPos;
			p_varSymbol();
			debug("循环内解析标识符结束");
		}
		else if ( symbol == ";" ) {
			pos = getSymbolEndPos;
			mark = false;
		}
		else{
			//Error
			Error.handle = false;
			printError();
		}
	}
	debug("标识符表结束");
}
//<标识符>::=<字母><_标识符>
//<_标识符>::=<_标识符><数字>
//<_标识符>::=<_标识符><字母>
string get_varSymbol(){
	printPos(__FUNCTION__);
	string symbol;
	string varName;
	vector<string> inTable;
	pushAlpha;
	symbol = getSymbol(inTable);
	if(symbol.length()){
		pos = getSymbolEndPos;
		varName += symbol;
		pushDigit;
		symbol = getSymbol(inTable);
		while (symbol.length()) {
			pos = getSymbolEndPos;
			varName += symbol;
			symbol = getSymbol(inTable);
		}		
	}
	debug(varName);
	//printFilePos;
	//system("pause");
	return varName;
}
void p_varSymbol(){
	printPos(__FUNCTION__);
	Error.Model = "解析标识符 定义时";

	string varName;
	string symbol;

	symbol = get_varSymbol();
	debug("获取标识符结束");
	if(symbol.length()){
		varName = symbol;
		//pos = getSymbolEndPos;
		//若varName返回不为空，则get中已跳过该部分
		{
			//处理重名问题
			int i = 0, i_end = varTable.size();
			while ( i != i_end ) {
				if(varName == varTable[i]) break;
				++i;
			}
			if( i == i_end ){
				varTable.push_back(varName);
			}
			else{
				Error.Info = "变量名重复";
				Error.handle = false;
				printError();
			}
		}
	}
	else{
		Error.handle = false;
		printError();
	}
}
void p_varSymbolCheck(string varName){
	printPos(__FUNCTION__);
	
	Error.Model = "解析标识符 使用时";

	//string varName;
	string symbol(varName);

	//symbol = get_varSymbol();
	if(symbol.length()){
		//varName = symbol;
		//pos = getSymbolEndPos;
		{
			//处理重名问题
			int i = 0, i_end = varTable.size();
			while ( i != i_end ) {
				if(varName == varTable[i]) break;
				++i;
			}
			if( i == i_end ){
				Error.Info = string("未知变量名 ") + varName;
				Error.handle = false;
				printError();
				varTable.push_back(varName);
			}
			else{
				Q.varS.push_back(varName);
				debug("变量入栈");
				debug(varName);
			}
		}
	}
	else{
		Error.handle = false;
		printError();
	}
}
//<语句部分>::=<语句>|<语句><语句部分>
void p_statementPart(){
	printPos(__FUNCTION__);
	p_statement();
	
	string symbol;
	vector<string> inTable;
	inTable.push_back("}");
	symbol = getSymbol(inTable);

	while (symbol != "}") {
		p_statement();
		symbol = getSymbol(inTable);
	}
}
//<语句>::＝<赋值语句>|<条件语句>|<循环语句>
void p_statement(){
	printPos(__FUNCTION__);
	string symbol;
	vector<string> inTable;
	inTable.push_back("if");
	inTable.push_back("while");
	inTable.push_back("}");
	symbol = getSymbol(inTable);
	if(symbol == "if"){
		pos = getSymbolEndPos;
		p_if();
	}else if( symbol == "while"){
		pos = getSymbolEndPos;
		p_while();
	}else if ( symbol == "}") {
		//语句部分结束
		//pos = getSymbolEndPos;
	}
	else{
		p_assignment();
	}
	debug(string("endof ")  + string(__FUNCTION__));
}
//<赋值语句>::=<标识符>=<表达式>;|
void p_assignment(){
	printPos(__FUNCTION__);
	Error.Model = "解析赋值语句";
	
	string symbol;
	vector<string> inTable;
	//printFilePos;
	symbol = get_varSymbol();
	if( symbol.length() ){
		p_varSymbolCheck(symbol);
		inTable.push_back("=");
		symbol = getSymbol(inTable);
		if( symbol == "=" ){
			pos = getSymbolEndPos;
			p_expression();
			string var,result;
			int varIndex = Q.varS.size() - 1;
			debug("varS size"); debug(varIndex);
			var = Q.varS[varIndex];
			result = Q.varS[varIndex - 1];
			Q.varS.pop_back();
			Q.varS.pop_back();
			Q.build( symbol, var, "", result);

			inTable.clear();
			inTable.push_back(";");
			symbol = getSymbol(inTable);
			if(symbol ==  ";"){
				pos = getSymbolEndPos;
			}
			else{
				Error.Info = string("期望的字符为 ; ，但并不是");
				Error.handle = false;
				printError();
			}
		}
		else{
			Error.Info = string("期望的字符为 = ，但并不是  ") + symbol;
			Error.handle = false;
			printError();
		}
	}
	debug(string("endof ")  + string(__FUNCTION__));
}
//<条件>::=<表达式><关系运算符><表达式>
void p_condition(){
	Error.Model = "解析条件";
	p_expression();

	string symbol;
	vector<string> inTable;

	inTable.push_back("==");
	inTable.push_back("<=");
	inTable.push_back(">=");
	inTable.push_back("!=");
	inTable.push_back(">");
	inTable.push_back("<");
	
	symbol = getSymbol(inTable);

	if ( symbol.length() ) {
		pos = getSymbolEndPos;
		Q.setWhileCPos();
		p_expression();
		Q.setFillBackPos();
		string op = revRelationship( symbol ), var1, var2, result = "";
		int varIndex = Q.varS.size() - 1;
		var2 = Q.varS[varIndex];
		var1 = Q.varS[varIndex - 1];
		Q.varS.pop_back();
		Q.varS.pop_back();
		Q.build(op, var1, var2, result);

		
	}
	else{
		Error.Info = "期望一个关系运算符 但不是";
		Error.handle = false;
		printError();
	}
}
//<表达式>::=<项>|<项><加法运算符><表达式>
//<项>{<加法运算符<项>}
void p_expression(){
	printPos(__FUNCTION__);
	string symbol;
	vector<string> inTable;

	p_item();
	//debug("");
	inTable.push_back("+");
	inTable.push_back("-");

	symbol = getSymbol(inTable);
	debug( string("获取加法运算符 ") + symbol );
	while (symbol.length()) {
		debug("获取加法运算符后面的项");
		pos = getSymbolEndPos;
		p_item();

		string op = symbol, var1, var2, result;
		printVarS;
		result = Q.getTempVar();
		int varIndex = Q.varS.size() - 1;
		var2 = Q.varS[varIndex];
		var1 = Q.varS[varIndex - 1];
		Q.varS.pop_back();
		Q.varS.pop_back();
		Q.build(op, var1, var2, result);
		Q.varS.push_back(result);
		
		symbol = getSymbol(inTable);
	}
	debug(string("endof ")  + string(__FUNCTION__));
	printFilePos;
}
//<项>::=<因子>|<因子><乘法运算符><项>
//<因子>{<乘法运算符><因子>}
void p_item(){
	printPos(__FUNCTION__);
	string symbol;
	vector<string> inTable;

	p_factor();

	inTable.push_back("*");
	inTable.push_back("/");

	symbol = getSymbol(inTable);
	debug(string("解析项 获得的运算符") + symbol );
	while (symbol.length()) {
		debug("获取乘法后面的因子");
		pos = getSymbolEndPos;
		p_factor();

		string op = symbol, var1, var2, result;
		result = Q.getTempVar();
		int varIndex = Q.varS.size() - 1;
		var2 = Q.varS[varIndex];
		var1 = Q.varS[varIndex - 1];
		Q.varS.pop_back();
		Q.varS.pop_back();
		Q.build(op, var1, var2, result);
		Q.varS.push_back(result);
		
		symbol = getSymbol(inTable);
	}
	debug(string("endof ")  + string(__FUNCTION__));
}
//<因子>::＝<标识符>|<常量>|(<表达式>)
factorType get_factorType(){
	vector<string> inTable;
	string symbol;
	
	inTable.push_back("(");
	pushAlpha;
	pushDigit;

	symbol = getSymbol(inTable);
	if (symbol.length()) {
		if( isalpha( symbol[0] ) ) return TvarSym;
		if( isdigit( symbol[0] ) ) return Tconst;
		if( symbol == "(" ) return Texp;
	}
	return Tother;
}
void p_factor(){
	printPos(__FUNCTION__);
	string symbol;
	vector<string> inTable;

	factorType type = get_factorType();
	switch ( type ) {
		case TvarSym:
			{
				string varName = get_varSymbol();
				p_varSymbolCheck(varName);
				break;
			}
		case Tconst:
			{
				p_const();
				break;
			}
		case Texp:
			{
				inTable.push_back("(");
				symbol = getSymbol(inTable);
				pos = getSymbolEndPos;
				
				p_expression();

				inTable.clear();
				inTable.push_back(")");
				symbol = getSymbol(inTable);
				if(symbol == ")"){
					pos = getSymbolEndPos;
				}
				else{
					Error.Info = "期待一个 ) 但并不是";
					Error.handle = false;
					printError();
				}
				break;
			}
		case Tother:
			{
				Error.Info = "不是合法的因子";
				Error.handle = false;
				printError();
			}
	}
	debug(string("endof ")  + string(__FUNCTION__));
}
//<常量>::＝<无符号整数>
void p_const(){
	printPos(__FUNCTION__);
	debug("--------------");
	printFilePos;
	debug("--------------");
	string symbol;
	vector<string> inTable;
	pushDigit;
	string constVal;

	symbol = getSymbol(inTable);
	while ( symbol.length() ) {
		pos = getSymbolEndPos;
		constVal += symbol;
		symbol = getSymbol(inTable);
	}
	if( constVal.length()  ){
		//pos = getSymbolEndPos; 应该是没用的
		debug(constVal);
		Q.varS.push_back(constVal);
	}
	else{
		Error.Info = "期望一个常量 但不是";
		Error.handle = false;
		printError();
	}
}
//<无符号整数>::=<数字序列>
//<数字序列>::<数字>=<数字序列>
//<数字序列>::=<数字>
//<加法运算符>::＝+|-
//<乘法运算符>::=*|／
//<关系运算符>::＝<|>|!=|>=|<=|==
void p_relationship(){
	printPos(__FUNCTION__);
	//to delete
	string symbol;
	vector<string> inTable;

	inTable.push_back("==");
	inTable.push_back("<=");
	inTable.push_back(">=");
	inTable.push_back("!=");
	inTable.push_back(">");
	inTable.push_back("<");
	
	symbol = getSymbol(inTable);

	if ( symbol.length() ) {
		pos = getSymbolEndPos;
		//some code
	}
	else{
		Error.Info = "期望一个关系运算符 但不是";
		Error.handle = false;
		printError();
	}
}
string revRelationship( string r ){
	if (r == "==") return "!=";
	if (r == "<=") return ">";
	if (r == ">=") return "<";
	if (r == "|=") return "==";
	if (r == ">") return "<=";
	if (r == "<") return ">=";
	return "233";
}
//<复合语句>::={<语句部分>}
void p_mulStatement(){
	printPos(__FUNCTION__);
	string symbol;
	vector<string> inTable;

	Error.Model = "解析复合语句";
	
	inTable.push_back("{");
	symbol = getSymbol( inTable );
	if ( symbol.length() ) {
		pos = getSymbolEndPos;
		
		p_statementPart();

		inTable.clear();
		inTable.push_back("}");

		symbol = getSymbol( inTable );
		if ( symbol.length() ) {
			//some code
			pos = getSymbolEndPos;
		}
		else{
			Error.Info = "期望一个} 但不是";
			Error.handle = false;
			printError();
		}
	}
	else{
		Error.Info = "期望一个{ 但不是";
		Error.handle = false;
		printError();
	}
}
//<语句1>::＝<语句>|<复合语句>
//语句不应以 { 复合语句必定以 { 开头
void p_statement1(){
	printPos(__FUNCTION__);
	string symbol;
	vector<string> inTable;

	inTable.push_back("{");

	symbol = getSymbol(inTable);

	if( symbol == "{" ) {
		debug(" 复合语句分支 ");
		p_mulStatement();
	}
	else{
		debug(" 语句分支 ");
		p_statement();
	}
}
//<条件语句>::=if（<条件>）<语句1>else<语句1>
void p_if(){
	Error.Model = "解析条件语句";
	string symbol;
	vector<string> inTable;

	inTable.push_back("(");

	symbol = getSymbol(inTable);

	if( symbol == "(" ){
		pos = getSymbolEndPos;
		
		p_condition();

		inTable.clear();
		inTable.push_back(")");

		symbol = getSymbol(inTable);
		if ( symbol == ")" ) {
			pos = getSymbolEndPos;
			p_statement1();

			string op = "GOTO";
			//Q.setFillBackPos();
			
			inTable.clear();
			inTable.push_back("else");

			symbol = getSymbol(inTable);
			if ( symbol == "else") {
				pos = getSymbolEndPos;
				Q.setIfGotoPos();
				Q.build(op,"","","");
				
				//设置跳转位置
				Q.setFillBackIf();
				p_statement1();
				Q.setIfGoto();
			}
			else{
				Error.Info = "期望一个 else 但不是";
				Error.handle = false;
				printError();
				debug(symbol);
			}
		}
		else{
			Error.Info = "期望一个 ) 但不是";
			Error.handle = false;
			printError();
		}
	}
	else{
		Error.Info = "期望一个 ( 但不是";
		Error.handle = false;
		printError();
	}
}
//<循环语句>::=while（<条件>）do<语句1>
void p_while(){
	Error.Model = "解析循环语句";
	string symbol;
	vector<string> inTable;

	inTable.push_back("(");

	symbol = getSymbol(inTable);
	if ( symbol == "(") {
		pos = getSymbolEndPos;
		
		p_condition();
		debug("while解析条件结束");
		inTable.clear();
		inTable.push_back(")");

		symbol = getSymbol(inTable);
		if ( symbol == ")" ) {
			pos = getSymbolEndPos;
			debug("while解析到了 )");
			debug("-------------");
			printFilePos;
			debug("-------------");
			inTable.clear();
			inTable.push_back("do");
			symbol = getSymbol(inTable);
			if( symbol == "do" ){
				pos = getSymbolEndPos;
				debug("while解析到了 do");
				debug("-------------");
				printFilePos;
				debug("-------------");
				debug("-------------");
				Q.printNode();
				debug("-------------");
				p_statement1();
				//设置跳转位置
				Q.setFillBack();
				Q.setWhileC();
				/*
				string op = "GOTO",gotoPos;
				{
					char buffer[5];
					sprintf(buffer, "<%d>", backPos);
					gotoPos = buffer;
				}
				Q.build(op, "", "", gotoPos);
				*/
			}
			else{
				Error.Info = "期望一个 do 但不是";
				Error.handle = false;
				printError();
			}
		}
		else{
			Error.Info = "期望一个 ) 但不是";
			Error.handle = false;
			printError();
		}
	}
	else{
		Error.Info = "期望一个 ( 但不是";
		Error.handle = false;
		printError();
		printFilePos;
	}
}
//<字母>::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
//<数字>::=0|1|2|3|4|5|6|7|8|9


int main(int argc, char *argv[]) {
	bool mark = true;
	while ( mark ) {
		string fileName;
		cout<<"输入一个文件名，或是输入 Q 退出"<<endl;
		cin>>fileName;
		if(fileName == "Q"){
			mark = false;
		}
		else{
			varTable.clear();
			iniFile(fileName);
			iniError();
			Q.clear();
			p_main();
			if(Error.cnt == 0){
				Q.build("END","","","");
				Q.printNode();
				printVar();
			}
		}
	}
	return 0;
}