#include <iostream>       // std::cout
#include <stack>          // std::stack
#include <vector>         // std::vector
#include <string>
#include <utility>
#include <map>
#include <sstream>

using namespace std;
using std::vector;

vector <string> parse_input(vector<string> non_terminals);
string get_next_token (int index);
void push_tokens ();
bool is_non_terminal(string stack_data,vector<string> non_terminals);
vector<string> tokens;
vector<string> non_terminals;
std::map<string, std::map<string, vector<string> > > parser_table;
void build_table ();
void print_production(string stack_data,vector<string> production);
void generate_error(string error_message);
vector<string> get_production(string non_terminal, string cur_token);

int main(){

build_table();
push_tokens();
non_terminals.push_back("S");
non_terminals.push_back("R");
non_terminals.push_back("U");
non_terminals.push_back("V");
non_terminals.push_back("T");
parse_input(non_terminals);

}

vector<string> parse_input(vector<string> non_terminals){

	stack<string> my_stack ;
	//push $ followed by start symbol.
	vector<string> output;
	my_stack.push("$");
	my_stack.push(non_terminals[0]);

	int token_index = 0;
	string cur_token = get_next_token(token_index++);

		while( my_stack.size() ){

			string stack_data = my_stack.top();
			my_stack.pop();

			if( is_non_terminal(stack_data,non_terminals) ){
				vector<string> production = get_production(stack_data,cur_token);
				if(production.size() == 1 && (production[0].compare("error") == 0)){
					//generate error for excess symbol in input.
					generate_error("excess " + cur_token);cur_token = get_next_token(token_index++);
					output.push_back("excess " + cur_token);
					my_stack.push(stack_data);
				}else if(production.size() == 1 && (production[0].compare("synch") == 0)){
					//synchronization error
					generate_error("synchronization error");
					output.push_back("synchronization error");
				}else{
					// in this case a production is get from table and want to push into stack.
					print_production(stack_data,production);
					std::stringstream ss;ss<<stack_data;ss<< "-->";for(int i =0 ;i < production.size(); i++){ss<<production[i];}
					output.push_back(ss.str());
					if( !( production[0].compare("epsilon") ) == 0 ){
						for(int i =production.size() - 1 ;i >=0; i--){
							my_stack.push(production[i]);
						}
					}
				}
			}else{
				if(stack_data.compare(cur_token) == 0){
					//token matched get next token to match.
					cout<<"match "<< stack_data <<endl;
					std::stringstream ss;ss << "match ";ss << stack_data;
					output.push_back(ss.str());
					if(cur_token.compare("$")==0){
						cout<<"input finished successfully"<<endl;
						output.push_back("input finished successfully");
					}else{
					cur_token = get_next_token(token_index++);
					}
				}else{
					//two unmatched terminals move to next pop from the stack to get next match.
					if(cur_token.compare("$") == 0){

						std::stringstream ss;ss << "missing token";ss << " ' ";ss << stack_data;ss << "'";
						generate_error(ss.str());
						output.push_back(ss.str());

					}else{
						generate_error("unmatching terminals");
						output.push_back("unmatching terminals");

					}

				}
			}

		}
		return output;
}

void print_production(string stack_data, vector<string> production){
	cout<<stack_data<< "-->";
	for(int i =0 ;i < production.size(); i++){
		cout<<production[i];
			}
	cout<<"\n";
}

void generate_error(string error_message){
	cout<<error_message<<endl;
}
bool is_non_terminal(string stack_data,vector<string> non_terminals){

	bool exist = false;

	for(int i=0 ;i< non_terminals.size();i++){
		if(stack_data.compare(non_terminals[i]) == 0) exist = true;
	}
return exist;
}
string get_next_token (int index){
	return tokens[index];
}

void push_tokens (){

	tokens.push_back("s");
		tokens.push_back("s");
			tokens.push_back("u");
				tokens.push_back("u");
					tokens.push_back("b");
						tokens.push_back("b");
							tokens.push_back("t");
								tokens.push_back("v");
									tokens.push_back("t");
										tokens.push_back("$");
}

vector<string> get_production(string non_terminal, string cur_token){

	std::map<string, vector<string> > non_terminal_map;
	non_terminal_map =  parser_table[non_terminal] ;
	return  non_terminal_map[cur_token];
}
void build_table (){

	std::vector<string> error;
	error.push_back("error");

	std::vector<string> synch;
	synch.push_back("synch");

	// std::vector<string> id;
	// id.push_back("id");

	std::vector<string> epsilon;
	epsilon.push_back("epsilon");


	std::vector<string> RT;
	RT.push_back("R");
	RT.push_back("T");

	std::vector<string> sURb;
	sURb.push_back("s");
	sURb.push_back("U");
	sURb.push_back("R");
	sURb.push_back("b");

	std::vector<string> uU;
	uU.push_back("u");
	uU.push_back("U");


	std::vector<string> vV;
	vV.push_back("v");
	vV.push_back("V");

	std::vector<string> VtT;
	VtT.push_back("V");
	VtT.push_back("t");
	VtT.push_back("T");

	// std::vector<string> parenthesesE;
	// parenthesesE.push_back("(");
	// parenthesesE.push_back("E");
	// parenthesesE.push_back(")");



 std::map<string, vector<string> >  map1;
 map1["s"] = RT;
 map1["u"] = error;
 map1["v"] = RT;
 map1["b"] = error;
 map1["t"] = RT;
 map1["$"] = epsilon;




 std::map<string, vector<string> >  map2;

 map2["s"] = sURb;
 map2["u"] = error;
 map2["v"] = epsilon;
 map2["b"] = epsilon;
 map2["t"] = epsilon;
 map2["$"] = epsilon;


 std::map<string, vector<string> >  map3;


 map3["s"] = epsilon;
 map3["u"] = uU;
 map3["v"] = error;
 map3["b"] = epsilon;
 map3["t"] = error;
 map3["$"] = error;

 std::map<string,  std::vector<string>>  map4;

 map4["s"] = error;
 map4["u"] = error;
 map4["v"] = vV;
 map4["b"] = error;
 map4["t"] = epsilon;
 map4["$"] = error;

 std::map<string, vector<string> >  map5;

 map5["s"] = error;
 map5["u"] = error;
 map5["v"] = VtT;
 map5["b"] = error;
 map5["t"] = VtT;
 map5["$"] = epsilon;

parser_table["S"] = map1;
parser_table["R"] = map2;
parser_table["U"] = map3;
parser_table["V"] = map4;
parser_table["T"] = map5;



}