#include<cstdio>
#include"semantic.h"
using namespace std;
vector<int> ids;
static int instr=1;  // 指令序号从1开始

int offset; // 偏移量 - 声明语句对于
int type;   // 类型
int width;  // 变量size信息
static int tmpId = 1;

struct Gen
{
	string instruction; // 指令名称
	int instr;    //序号
	bool back;    //是否需要回填
	int backinstr;//回填的序号
	Gen(string i,int in,bool b,int bin): instruction(i),instr(in),back(b),backinstr(bin) {}
};
struct Code{
	int op;
	int num1;
	int num2;
};

queue<Gen> gens;//指令缓冲队列 便于回填
vector<Code> codes;//三地址码
/*
	C++ stack不支持遍历，只能通过另外一个栈进行辅助
	从栈中获取元素
*/
void getSymbol(stack<Symbol> &symStack,vector<Symbol>& outList,int size){
	stack<Symbol> tmp;
	for(int i = 0;i<size;++i){
		tmp.push(symStack.top());
		symStack.pop();
		outList.push_back(tmp.top());
	}// 栈顶第一个 栈顶第二个 。。。
	for (int i = 0;i<size;++i){
		symStack.push(tmp.top());
		tmp.pop();
	}
}
// 生成新字
string newTemp(){
	string s="t";
	s = s + to_string(tmpId);
	tmpId += 1;
	return s;
}
void printInstr(){ // 在缓冲队列中打印
	while(!gens.empty()){
		Gen g = gens.front();
		if (!g.back&&g.backinstr==0){
			gens.pop();
			cout<<g.instr<<":"<<g.instruction<<endl;
		}
		else if (!g.back){
			gens.pop();
			cout<<g.instr<<":"<<g.instruction<<g.backinstr<<endl;
		}
		else{
			gens.pop();
			cout<<g.instr<<":"<<g.instruction<<instr<<endl;	
		}
		// else break;
	}
	cout<<instr<<":"<<endl;
}
// 制造列表
vector<int> makelist(int i){
	vector<int> arr;
	arr.push_back(i);
	return arr;
}
// 合并列表
vector<int> merge(vector<int> arr1,vector<int> arr2){
	vector<int> arr;
	for (int i = 0;i<arr1.size();++i){
		arr.push_back(arr1[i]);
	}
	for (int i = 0;i<arr2.size();++i){
		if (find(arr.begin(),arr.end(),arr2[i])==arr.end()){
			arr.push_back(arr2[i]);
		}
	}
	return arr;
}
// 回写
void backpatch(vector<int> arr,int instr1){
	const int n = gens.size();
	for (int i = 0;i<n;++i){
		Gen g = gens.front();
		if(find(arr.begin(),arr.end(),g.instr)!=arr.end()){
			g.back = false;
			g.backinstr = instr1;
		}
		gens.pop();
		gens.push(g);
	}
	// printInstr();
}


int max(int a,int b){
	return a>b?a:b;
}
// 检查在符号表中是否存在且有效
void checkTable(Symbol sym,vector<table_item> &table){
	bool find = false;
	for (int i = 0;i<table.size();++i){
		if (table[i].w_name==sym.attr.assignType.addr){
			find = true;
			sym.attr.assignType.type = table[i].w_type;
			break;
		}
	}
	if (!find || sym.attr.assignType.type == 0){
		printf("undefine %s!\n",sym.attr.assignType.addr.c_str());
		exit(0);//提出
	}
}

/*
	根据不同编号产生式确定执行的语义动作
*/

/*
	@参数 产生式编号 产生式集合 符号栈 符号表
	要考虑增广文法中新加了一条产生式
*/

void semanticAnalysis(int expid,vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	switch(expid){
		case 0: printInstr(); break;//0号规约成功了就
		case 1: //P->DS
		func01(exps,symStack,table,sym);
		break;
		case 2: //D->L id;D
		func02(exps,symStack,table,sym);
		break;
		case 3: //D -> @
		func03(exps,symStack,table,sym);
		break;
		case 4: //L -> int
		func04(exps,symStack,table,sym);
		break;
		case 5: //L -> float
		func05(exps,symStack,table,sym);
		break;
		case 6: //S -> id=E;
		func06(exps,symStack,table,sym);
		break;
		case 7: //S -> if(C) S
		func07(exps,symStack,table,sym);
		break;
		case 8: //S -> if(C) S else S
		func08(exps,symStack,table,sym);
		break;
		case 9: //S -> while(C) S
		func09(exps,symStack,table,sym);
		break;
		case 10://S -> S;S
		func10(exps,symStack,table,sym);
		break;
		case 11://C -> E>E
		func11(exps,symStack,table,sym);
		break;
		case 12://C -> E<E
		func12(exps,symStack,table,sym);
		break;
		case 13://C -> E==E
		func13(exps,symStack,table,sym);
		break;
		case 20://E -> E+T
		func14(exps,symStack,table,sym);
		break;
		case 21://E -> E-T
		func15(exps,symStack,table,sym);
		break;
		case 22://E -> T
		func16(exps,symStack,table,sym);
		break;
		case 23://T -> F
		func17(exps,symStack,table,sym);
		break;
		case 24://T -> T*F
		func18(exps,symStack,table,sym);
		break;
		case 25://T -> T/F
		func19(exps,symStack,table,sym);
		break;
		case 26://F -> (E)
		func20(exps,symStack,table,sym);
		break;
		case 27://F -> id
		func21(exps,symStack,table,sym);
		break;
		case 28://F -> digits
		func22(exps,symStack,table,sym);
		break;
		case 29: //M1 {D.offset=0}
		func23(exps,symStack,table,sym);
		break;
		case 30: //N1 {D.offset=0}
		func24(exps,symStack,table,sym);
		break;
		case 31: //M1 {D.offset=0}
		func25(exps,symStack,table,sym);
		break;
		case 32: //M1 {D.offset=0}
		func26(exps,symStack,table,sym);
		break;
		case 33: //M1 {D.offset=0}
		func27(exps,symStack,table,sym);
		break;
		case 34: //M1 {D.offset=0}
		func28(exps,symStack,table,sym);
		break;
		case 35: //M1 {D.offset=0}
		func29(exps,symStack,table,sym);
		break;
		case 36: //M1 {D.offset=0}
		func30(exps,symStack,table,sym);
		break;
		case 37: //M1 {D.offset=0}
		func31(exps,symStack,table,sym);
		break;

		case 14: // C C || M7 C
		func32(exps,symStack,table,sym);
		break;
		case 15: //C C && M7 C
		func33(exps,symStack,table,sym);
		break;
		case 16: //C ( C )
		func34(exps,symStack,table,sym);
		break;
		case 17: // C true 
		func35(exps,symStack,table,sym);
		break;
		case 18: // C false
		func36(exps,symStack,table,sym);
		break;
		case 19: // C false
		func37(exps,symStack,table,sym);
		break;
		default:
		break;
		// cout<<"error-expid!"<<endl;
	}
}

/*
	这个需要用户自己根据自己的文法进行编写
*/

// P -> D S
void func01(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	
}
// D L id ; N1 D
void func02(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){

}
//D @
void func03(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){

}
// L -> int
void func04(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.stateType.type = 1;
	sym.attr.stateType.width = 4;
}
// L->float
void func05(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.stateType.type = 2;
	sym.attr.stateType.width = 8;
}
// S -> id = E ;
void func06(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,5);
	checkTable(Slist[3],table);
	string s = Slist[3].attr.assignType.addr + "=" + Slist[1].attr.assignType.addr;
	gens.push(Gen(s,instr++,false,0));//缓冲队列中加入指令
}
// S -> if(C) S
void func07(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,4);
	backpatch(Slist[3].attr.controlType.trueList,Slist[1].attr.controlType.instr);
	sym.attr.controlType.nextList = merge(Slist[3].attr.controlType.falseList,Slist[0].attr.controlType.nextList);
}
// S -> if (C) S else S
void func08(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,8);
	backpatch(Slist[7].attr.controlType.trueList,Slist[5].attr.controlType.instr);
	backpatch(Slist[7].attr.controlType.falseList,Slist[1].attr.controlType.instr);
	sym.attr.controlType.nextList = merge(Slist[0].attr.controlType.nextList,merge(Slist[3].attr.controlType.nextList,Slist[4].attr.controlType.nextList));
	// printInstr();
}
// S -> while(C) S
void func09(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,6);
	backpatch(Slist[0].attr.controlType.nextList,Slist[5].attr.controlType.instr);
	backpatch(Slist[3].attr.controlType.trueList,Slist[1].attr.controlType.instr);
	sym.attr.controlType.nextList = Slist[3].attr.controlType.falseList;
	gens.push(Gen("goto ",instr++,false,Slist[5].attr.controlType.instr));
	// printInstr();
}
// S -> S S
void func10(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	
}
// C -> E>E
void func11(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,3);
	sym.attr.controlType.trueList = makelist(instr);
	sym.attr.controlType.falseList = makelist(instr+1);
	string s = "if "+ Slist[2].attr.assignType.addr +">"+Slist[0].attr.assignType.addr+" goto ";
	gens.push(Gen(s,instr++,true,0));
	s = "goto ";
	gens.push(Gen(s,instr++,true,0));
	// sym.attr.
}
// C->E<E
void func12(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,3);
	sym.attr.controlType.trueList = makelist(instr);
	sym.attr.controlType.falseList = makelist(instr+1);
	string s = "if "+ Slist[2].attr.assignType.addr +"<"+Slist[0].attr.assignType.addr+" goto ";
	gens.push(Gen(s,instr++,true,0));
	s = "goto ";
	gens.push(Gen(s,instr++,true,0));
}
// C->E==E
void func13(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,3);
	sym.attr.controlType.trueList = makelist(instr);
	sym.attr.controlType.falseList = makelist(instr+1);
	string s = "if "+ Slist[2].attr.assignType.addr +"=="+Slist[0].attr.assignType.addr+" goto ";
	gens.push(Gen(s,instr++,true,0));
	s = "goto ";
	gens.push(Gen(s,instr++,true,0));
}
// E->E+T
void func14(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,3);
	sym.attr.assignType.addr = newTemp();
	sym.attr.assignType.type = max(Slist[2].attr.assignType.type,Slist[0].attr.assignType.type);
	string s = sym.attr.assignType.addr + "=" + Slist[2].attr.assignType.addr + "+" + Slist[0].attr.assignType.addr;
	gens.push(Gen(s,instr++,false,0));//缓冲队列中加入指令
	// printf("%s=%s+%s\n", sym.attr.assignType.addr.c_str(),Slist[2].attr.assignType.addr.c_str(),Slist[0].attr.assignType.addr.c_str());
}
// E->E-T
void func15(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,3);
	sym.attr.assignType.addr = newTemp();
	sym.attr.assignType.type = max(Slist[2].attr.assignType.type,Slist[0].attr.assignType.type);
	// printf("%s=%s-%s\n", sym.attr.assignType.addr.c_str(),Slist[2].attr.assignType.addr.c_str(),Slist[0].attr.assignType.addr.c_str());
	string s = sym.attr.assignType.addr + "=" + Slist[2].attr.assignType.addr + "-" + Slist[0].attr.assignType.addr;
	gens.push(Gen(s,instr++,false,0));//缓冲队列中加入指令
	// printInstr();
}
// E -> T
void func16(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,1);
	sym.attr.assignType.type = Slist[0].attr.assignType.type;
	sym.attr.assignType.addr = Slist[0].attr.assignType.addr;
}
// T -> F
void func17(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,1);
	sym.attr.assignType.type = Slist[0].attr.assignType.type;
	sym.attr.assignType.addr = Slist[0].attr.assignType.addr;
}
// T->T*F
void func18(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,3);
	sym.attr.assignType.addr = newTemp();
	sym.attr.assignType.type = max(Slist[2].attr.assignType.type,Slist[0].attr.assignType.type);
	// printf("%s=%s*%s\n", sym.attr.assignType.addr.c_str(),Slist[2].attr.assignType.addr.c_str(),Slist[0].attr.assignType.addr.c_str());
	string s = sym.attr.assignType.addr + "=" + Slist[2].attr.assignType.addr + "*" + Slist[0].attr.assignType.addr;
	gens.push(Gen(s,instr++,false,0));//缓冲队列中加入指令
	// printInstr();
}
// T->T/F
void func19(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,3);
	sym.attr.assignType.addr = newTemp();
	sym.attr.assignType.type = max(Slist[2].attr.assignType.type,Slist[0].attr.assignType.type);
	// printf("%s=%s/%s\n", sym.attr.assignType.addr.c_str(),Slist[2].attr.assignType.addr.c_str(),Slist[0].attr.assignType.addr.c_str());
	string s = sym.attr.assignType.addr + "=" + Slist[2].attr.assignType.addr + "/" + Slist[0].attr.assignType.addr;
	gens.push(Gen(s,instr++,false,0));//缓冲队列中加入指令
	// printInstr();
}
// F->(E)
void func20(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,2);
	sym.attr.assignType.type = Slist[1].attr.assignType.type;
	sym.attr.assignType.addr = Slist[1].attr.assignType.addr;
}
// F->id
void func21(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,1);
	sym.attr.assignType.addr = Slist[0].attr.assignType.addr;
	checkTable(sym,table);
}
// F -> digits
void func22(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,1);
	sym.attr.assignType.addr = Slist[0].attr.assignType.addr;
	sym.attr.assignType.type = 1;// 应该按照数字形态判断，简略期间就算了
}
//M1 {D.offset=0}
void func23(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	offset = 0;
}
//N1
void func24(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,3);
	// Slist[2].attr.stateType.type type
	// offset                       offset
	bool find = false;
	for (int i = 0;i<table.size();++i){
		if (table[i].w_name==Slist[1].attr.assignType.addr){
			find = true;
			table[i].w_addr = offset;
			table[i].w_type = Slist[2].attr.stateType.type;
			break;
		}
	}
	if (!find){
		cout<<"cannot find "<<Slist[1].attr.assignType.addr<<"in symbol table!"<<endl;
		exit(0);//提出
	}
	offset = offset + Slist[2].attr.stateType.width;
}
// M2
void func25(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.controlType.instr = instr;
	// cout<<"M2"<<endl;
}
//M3
void func26(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.controlType.instr = instr;
	// cout<<"M3"<<endl;
}
//N2
void func27(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	// cout<<"N2"<<endl;
	sym.attr.controlType.nextList = makelist(instr);
	string s = "goto ";
	gens.push(Gen(s,instr++,true,0));
}
// M4
void func28(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.controlType.instr = instr;
	// cout<<"M4"<<endl;
}
//M5
void func29(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.controlType.instr = instr;
	// cout<<"M5"<<endl;
}
//M6
void func30(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.controlType.instr = instr;
	// cout<<"M6"<<endl;
}
//M7
void func31(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.controlType.instr = instr;
	// cout<<"M7"<<endl;
}

// C C || M7 C
void func32(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,4);
	backpatch(Slist[3].attr.controlType.falseList,Slist[1].attr.controlType.instr);
	sym.attr.controlType.trueList = merge(Slist[3].attr.controlType.trueList,Slist[0].attr.controlType.trueList);
	sym.attr.controlType.falseList = Slist[0].attr.controlType.falseList;
}

//C C && M7 C
void func33(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,4);
	backpatch(Slist[3].attr.controlType.trueList,Slist[1].attr.controlType.instr);
	sym.attr.controlType.falseList = merge(Slist[3].attr.controlType.falseList,Slist[0].attr.controlType.falseList);
	sym.attr.controlType.trueList = Slist[0].attr.controlType.trueList;
}

//C ( C )
void func34(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,2);
	sym.attr.controlType.trueList = Slist[1].attr.controlType.trueList;
	sym.attr.controlType.falseList = Slist[1].attr.controlType.falseList;
}

// C true 
void func35(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.controlType.trueList = makelist(instr);
	string s = "goto ";
	gens.push(Gen(s,instr++,true,0));
}

// C false
void func36(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	sym.attr.controlType.falseList = makelist(instr);
	string s = "goto ";
	gens.push(Gen(s,instr++,true,0));
}
// C ! C
void func37(vector<ProductionExpression> &exps,stack<Symbol> &symStack,vector<table_item> &table,Symbol &sym){
	vector<Symbol> Slist;
	getSymbol(symStack,Slist,1);
	sym.attr.controlType.falseList = Slist[0].attr.controlType.trueList;
	sym.attr.controlType.trueList = Slist[0].attr.controlType.falseList;
}