LR分析-demo2

"E>E+T",
"E>T",
"T>T*F",
"T>F",
"F>(E)",
"F>id",

//LR分析-demo2
/*2018/11/24
*by lzh
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<stack>
#include<map>
using namespace std;
stack<string>stk, tmp, com;		//stk是存入s0x1，即状态和符号的栈，tmp是用来输出的栈，
								//com是在归约时确定归约式子的栈(防止错误弹出元素)
string input, w;			//输入串
string slr[15][15];		//slr表
string action[] = {		//slr表横轴动作+转换
	"id","+","*","(",")","$","E","T","F"
};
//i就是id
string handle[] = {   //文法
	" ",
	"E>E+T",
	"E>T",
	"T>T*F",
	"T>F",
	"F>(E)",
	"F>id",
};
map<string, int> act, status;		//转移表
bool flag = false;					//accept状态
int now = 0, handle_index = 0;	//当前扫描字符位置	//选中的规约式序号
void init() {						//初始化，
	int i = 0;
	for (i = 0; i < 9;i++) {
		act.insert(make_pair(action[i], i));	//建立分析表
	}
	int j = 0;
	while (j<12) {
		int i = j;
		string t;
		if (i < 10) t = '0' + i;
		else {
			t = ('0' + (i / 10));
			t += ('0' + i % 10);
		}
		status.insert(make_pair(t, j));		//将状态和数字对应
		j++;
	}
	slr[0][0] = slr[4][0] = slr[6][0] = slr[7][0] = "s5";		//保存slr表
	slr[1][1] = slr[8][1] = "s6";
	slr[2][1] = slr[2][4] = slr[2][5] = "r2";
	slr[2][2] = slr[9][2] ="s7";
	slr[0][3] = slr[6][3] = slr[4][3] = slr[7][3] = "s4";
	slr[1][5] = "acc";
	slr[3][1] = slr[3][2] = slr[3][4] = slr[3][5] = "r4";
	slr[5][1] = slr[5][2] = slr[5][4] = slr[5][5] = "r6";
	slr[9][1] = slr[9][4] = slr[9][5] = "r1";
	slr[8][4] = "s11";
	slr[10][1] = slr[10][2] = slr[10][4] = slr[10][5] = "r3";
	slr[11][1] = slr[11][2] = slr[11][4] = slr[11][5] = "r5";
	slr[0][6] = "1";
	slr[0][7] = slr[4][7] = "2";
	slr[0][8] = slr[4][8] = slr[6][8] = "3";
	slr[4][6] = "8";
	slr[6][7] = "9";
	slr[7][8] = "10";
}
void show() {				
	int count_two_char = 0;	//数栈中超过两个字符的元素
	while (!stk.empty()) {		//用两个栈来回倒，输出字符
		tmp.push(stk.top());
		stk.pop();
	}
	while (!tmp.empty()) {
		cout << tmp.top();
		if (tmp.top().size()>1)
			count_two_char++;
		stk.push(tmp.top());
		tmp.pop();
	}
	cout.setf(ios::right);
	cout.width(11 - stk.size()- count_two_char);
	cout << "|";
	cout.setf(ios::right);	//设置字符对其方式
	cout.width(10);		//设置字符宽度
	cout << w;
	cout << "|";
	cout.setf(ios::left);
	cout.width(10);
}
//参数1是状态，参数2是符号，符号包括终结符和非终结符，作用是找到slr表中项目
string slrFind(string stat,string ActionAndTransfer) {				
	int t1 = status[stat];				//取出状态对应下标
	int t2 = act[ActionAndTransfer];	//取出符号对应下标
	string tmp;
	if (slr[t1][t2] != "") 			//如果slr表中存在此项
		tmp = slr[t1][t2];	
	else
		tmp = "";
	return tmp;						//返回slr表中的项目
}
//参数1和2同slrFind函数，index是选中的规约式子序号
bool judge(string stat, string Transfer,int &index) {		
	string judg = slrFind(stat, Transfer);	//得到slr表中项目
	if (judg[0] != 'r')						//如果这个项不是r开头，就不是归约
		return false;							//非归约直接返回
	int i = judg[1] - '0';						//如果是归约，得到归约式子序号
	index = i;
	return true;								//可以发起归约
}
void change_t_for_slr(string &t1,string &t2) {
	t1 = stk.top();
	if (w[now] == 'i') {	//移进符号为id
		t2 = "id";
		now = 2;
	}
	else {					//移进符号不为id
		t2 = w[now];
		now = 1;
	}
}
void analysis(string s) {				
	w = s;
	printf("----------|----------|----------\n");
	printf("    栈    |   输入   |    动作  \n");
	printf("----------|----------|----------\n");
	while (!flag) {						//处于非接受状态
		now = 0;							//正在处理的输入串中的字符
		if (stk.empty()) {					//一开始栈为空，直接移进符号
			stk.push("0");
			cout << "0         |";
			cout.setf(ios::right);			//设置字符对其方式
			cout.width(10);					//设置字符宽度
			cout << w;
			cout << "|移进" << endl;
			printf("----------|----------|----------\n");
			string t1, t2;		//t1为栈顶符号，t2为输入串当前符号
			change_t_for_slr(t1, t2);
			stk.push(t2);							//将符号压入栈
			w = w.substr(now, w.size() - now);	//丢弃已扫描的字符	
			string lr = slrFind(t1, t2);			//找到对应的动作
			if (lr[0] == 's')						//此时是移进
				lr = lr.substr(1, lr.size() - 1);
				stk.push(lr);
			continue;
		}
		show();
		string serach;
		if(w[0]!='i')		//获取输入串的开头符号
			serach =w.substr(0,1);
		else
			serach = w.substr(0, 2);
		//cout << w[0]+""<< endl;		//转换字符串不能这么做
		if(judge(stk.top(), serach, handle_index)) {	//归约，优先级最高
			cout << "按" + handle[handle_index] + "归约" << endl;
			printf("----------|----------|----------\n");
			string RightSymbol = handle[handle_index].substr(2, handle[handle_index].size() - 2);  //得到产生式右部符号
			while (RightSymbol != "") {		
				if (RightSymbol[0] == 'i'){	//将产生式右部所有符号暂时压入一个栈中
					com.push("id");
					RightSymbol=RightSymbol.substr(2, RightSymbol.size() - 2);
				}
				else{
					string t5;
					t5 = RightSymbol[0];
					com.push(t5);
					RightSymbol=RightSymbol.substr(1, RightSymbol.size() - 1);
				}
			}
			while (!com.empty()) {//用这个有产生式右部所有符号的栈和当前栈比对，
									//确定归约式正确
				stk.pop();
				string cmp1 = stk.top();
				if (com.top()==cmp1) {
					stk.pop();
					com.pop();
				}
			}
			string t3 = handle[handle_index];
			t3 = t3[0];								//得到归约式的左部符号
			string t4 = slrFind(stk.top(),t3);		//用此时左部符号和当前栈顶
														//确认下一个动作
			stk.push(t3);
			stk.push(t4);
			continue;
		}
		else {  //移进操作--或者acc	
			string t1, t2;
			change_t_for_slr(t1, t2);				//t1为栈顶符号，t2为输入串当前符号
			stk.push(t2);							//将符号压入栈
			w = w.substr(now, w.size() - now);	//丢弃已扫描的字符	
			string lr = slrFind(t1, t2);			//找到对应的动作
			if (lr[0] == 's'){						//如果是移进操作
				lr = lr.substr(1, lr.size() - 1);
				cout << "移进" << endl;
			}
			else if (lr == "acc") {				//或者是接受状态
				cout << "接受" << endl;
				flag = true;
			}
			else if (lr == "")
			{
				cout << "拒绝" << endl;
				flag = true;
			}
			stk.push(lr);
			printf("----------|----------|----------\n");
			continue;
		}
	}
}
int main(void) {
	init();
	input = "id*id+id";		//输入串
	input += "$";
	analysis(input);
	return 0;
}