编译原理，c++实现简易编译器

#pragma once
#include
#include
#include
using namespace std;
typedef struct Node
{
	string name;
	Node() {
		name = "";
	}
	Node(string _name) {
		name = _name;
	}
}Step;

typedef struct Edge
{
	Node start;
	Node end;
	char option;
	Edge(Node _start, Node _end, char _option) {
		start = _start;
		end = _end;
		option = _option;
	}
};

typedef struct Graph
{
	Node start;
	Node end;
	vector edges;
	Graph() {
		Node a = Node("");
		Node b = Node("");
		vector ed;
		start = a;
		end = b;
		edges = ed;
	}
	Graph(Node _start, Node _end, vector_edges) {
		start = _start;
		end = _end;
		edges = _edges;
	}
};

// 初始化操作，绘制操作的基本NFA
Graph create(char option, int step_index) {
	Node start = Node(to_string(step_index));
	Node end = Node(to_string(step_index + 1));
	Edge edge = Edge(start, end, option);
	vector edges;
	edges.push_back(edge);
	Graph temp = Graph(start, end, edges);
	return temp;
}

// 可选操作
Graph optional(Graph a, Graph b, int new_start_num) {
	// 新的开始结束节点
	Node new_start = Node(to_string(new_start_num));
	Node new_end = Node(to_string(new_start_num + 1));
	// 新的四条边
	Edge ed1 = Edge(new_start, b.start, '#');
	Edge ed2 = Edge(new_start, a.start, '#');
	Edge ed3 = Edge(b.end, new_end, '#');
	Edge ed4 = Edge(a.end, new_end, '#');
	vector edges;
	// 添加边
	edges.insert(edges.end(), a.edges.begin(), a.edges.end());
	edges.insert(edges.end(), b.edges.begin(), b.edges.end());
	edges.push_back(ed1);
	edges.push_back(ed2);
	edges.push_back(ed3);
	edges.push_back(ed4);
	Graph temp = Graph(new_start, new_end, edges);
	return temp;
}

// 联结操作
Graph coupling(Graph a, Graph b, int new_start_num) {
	Node node = Node(to_string(new_start_num));
	Edge ed1 = Edge(a.end, node, '#');
	Edge ed2 = Edge(node, b.start, '#');
	vector edges;
	edges.insert(edges.end(), a.edges.begin(), a.edges.end());
	edges.insert(edges.end(), b.edges.begin(), b.edges.end());
	edges.push_back(ed1);
	edges.push_back(ed2);
	Graph temp = Graph(a.start, b.end, edges);
	return temp;
}

// 重复操作
Graph repeat(Graph a, int new_start_num) {
	Node new_start = Node(to_string(new_start_num));
	Node new_end = Node(to_string(new_start_num + 1));
	Edge ed1 = Edge(new_start, a.start, '#');
	Edge ed2 = Edge(a.end, new_start, '#');
	Edge ed3 = Edge(new_start, new_end, '#');
	vector edges;
	edges.insert(edges.end(), a.edges.begin(), a.edges.end());
	edges.push_back(ed1);
	edges.push_back(ed2);
	edges.push_back(ed3);
	Graph temp = Graph(new_start, new_end, edges);
	return temp;
}

#include 
#include 
#include "MyHead.h"
using namespace std;

int step_number = 0;  // 统计step节点数量

vector createExp() {
	vector a;
	return a;
}

// 整理式子(去除空格，统一符号)
void CompleteSign(string &exp) {
	string temp = "";
	int length = exp.length();
	int num = 0;
	for (int i = 0; i < length; i++) {
		int asc = int(exp[i]);  // 字符转为ASCII码便于判断
		if (asc != 32) {  // 消去空格
			if (asc != 124) {  // 统一可选为+号
				temp += exp[i];
			}
			else {
				temp += '+';
			}
			num++;  // 消去后的字符数
		}
	}
	exp = temp;
	temp = "";
	for (int i = 0; i < num; i++) {
		int asc = int(exp[i]);
		temp += exp[i];
		// 当前为数字(字母)或*，且下一个字符为数字或(则需要添上联结号.
		if (i < num - 1 && ((asc >= 48 && asc <= 57) || asc == 42) && ((int(exp[i + 1]) >= 48 && int(exp[i + 1]) <= 57) || int(exp[i + 1]) == 40)) {
			temp += '.';
		}
	}
	exp = temp;
}

// 中缀表达式转后缀表达式
string toPostfix(string exp) {
	stack ope;
	string temp = "";
	int brackets = 0;  // 括号数
	int i = 0;
	int len = exp.length();
	while (i < len) {
		if (exp[i] == '(') {  // 遇到左括号直接入栈
			ope.push('(');
			brackets++;
			i++;
		}
		else if (exp[i] == '*') {  // *号直接入栈
			ope.push('*');
			i++;
		}
		else if (exp[i] == '.') {  // 遇到.
			if (ope.empty()) {  // 为空入栈
				ope.push('.');
				i++;
			}
			else {
				if (ope.top() == '*' || ope.top() == '.') {  // 为*或.出栈
					temp += ope.top();
					ope.pop();
				}
				else if (ope.top() == '(' || ope.top() == '+') {  // 入栈
					ope.push('.');
					i++;
				}
			}
		}
		else if (exp[i] == '+') {  // 遇到+
			if (ope.empty()) {  // 为空入栈
				ope.push('+');
				i++;
			}
			else {
				if (ope.top() == '*' || ope.top() == '.' || ope.top() == '+') {  // 出栈
					temp += ope.top();
					ope.pop();
				}
				else if (ope.top() == '(') {  // 入栈
					ope.push('+');
					i++;
				}
			}
		}
		else if (exp[i] == ')') {
			if (brackets <= 0) {
				return "Error";  // 括号数不匹配
			}
			else {
				if (ope.top() != '(') {  // 非左括号都出栈
					temp += ope.top();
					ope.pop();
				}
				else {
					ope.pop();  // 消去左右括号
					i++;
					brackets--;  // 左括号数减一
				}
			}
		}
		else {  // 操作数
			temp += exp[i];
			i++;
		}
	}
	// 最后输出运算符栈中的剩余运算符
	int size = ope.size();
	for (int k = 0; k < size; k++) {
		temp += ope.top();
		ope.pop();
	}
	return temp;
}

// 判断某个元素是否在vector中
bool sinv(vector a,string b) {
	for (int i = 0; i < a.size(); i++) {
		if (b == a[i]) {
			return true;
		}
	}
	return false;
}

// 判断两个一维vector是否乱序相等
bool judge(vector a, vector b) {
	for (int i = 0; i < a.size(); i++) {
		if (!sinv(b, a[i])) {
			return false;
		}
	}
	return true;
}

// 判断一维vector是否在二维vector中，顺序可打乱
int isIn(vector> save, vector a) {
	// 遍历二维vector每一个元素
	for (int i = 0; i < save.size(); i++) {
		// 如果遇到和待判断一维vector长度一致
		if (save[i].size() == a.size()) {
			// 判断这个数组和待判断数组是否一致
			if (judge(save[i], a)) {
				return i;
			}
		}
	}
	return 0;
}

bool judege(vector DFA,string sen) {
	return true;
}

// NFA转化为DFA
Graph NFAtoDFA(Graph graph) {
	vector> save;  // 存放新节点包含的旧节点
	vector> edge;  // 存放DFA的边
	vector DFA_start;  // 开始的节点
	DFA_start.push_back(graph.start.name);
	int node_num = 1;  // 节点数
	int i = 0;
	while (i < DFA_start.size()) {
		// 每次往vector中加入元素，每次后移判断，直到没有新的元素加入
		for (int k = 0; k < graph.edges.size(); k++) {
			// 如果是空操作
			if (graph.edges[k].option == '#' && graph.edges[k].start.name == DFA_start[i]) {
				DFA_start.push_back(graph.edges[k].end.name);
			}
		}
		i++;
	}
	save.push_back(DFA_start);
	i = 0;
	// 遍历新的结点
	while (i < save.size()) {
		// save存储新的结点
		vector temp0;  // 操作为0
		vector temp1;  // 操作为1
		for (int m = 0; m < save[i].size(); m++) {
			for (int k = 0; k < graph.edges.size(); k++) {
				// 如果边中有当前新结点的相同start
				if (graph.edges[k].start.name == save[i][m]) {
					// 加到临时存储数组temp中
					if (graph.edges[k].option == '0') {
						temp0.push_back(graph.edges[k].end.name);
					}
					else if (graph.edges[k].option == '1') {
						temp1.push_back(graph.edges[k].end.name);
					}
				}
			}
		}

		if (!temp0.empty()) {
			// 对于temp0和temp1，寻找空操作，和上面的DFA_start一样
			int flag = 0;
			while (flag < temp0.size()) {
				for (int k = 0; k < graph.edges.size(); k++) {
					if (graph.edges[k].option == '#' && graph.edges[k].start.name == temp0[flag]) {
						if (!sinv(temp0, graph.edges[k].end.name)) {
							temp0.push_back(graph.edges[k].end.name);
						}
					}
				}
				flag++;
			}
		}

		if (!temp1.empty()) {
			int flag = 0;
			while (flag < temp1.size()) {
				for (int k = 0; k < graph.edges.size(); k++) {
					if (graph.edges[k].option == '#' && graph.edges[k].start.name == temp1[flag]) {
						if (!sinv(temp1, graph.edges[k].end.name)) {
							temp1.push_back(graph.edges[k].end.name);
						}
					}
				}
				flag++;
			}
		}

		if (isIn(save, temp0)) {  // 如果在save中
			vector ed;
			ed.push_back(to_string(i + 1));  // 边的start为当前这个节点
			ed.push_back(to_string(isIn(save, temp0)));  // end为save中的那个节点
			ed.push_back("0");  // 操作为0
			edge.push_back(ed);
		}
		else {
			if (!temp0.empty()) {
				save.push_back(temp0);  // 不在save中就加入
				node_num++;
				vector ed;
				ed.push_back(to_string(i + 1));  // 边的start为当前这个节点
				ed.push_back(to_string(node_num));  // end为新加入的那个节点
				ed.push_back("0");
				edge.push_back(ed);
			}	
		}
		// 同操作0
		if (isIn(save, temp1)) {
			vector ed;
			ed.push_back(to_string(i + 1));
			ed.push_back(to_string(isIn(save, temp1)));
			ed.push_back("1");
			edge.push_back(ed);
		}
		else {
			if (!temp1.empty()) {
				save.push_back(temp1);
				node_num++;
				vector ed;
				ed.push_back(to_string(i + 1));
				ed.push_back(to_string(node_num));
				ed.push_back("1");
				edge.push_back(ed);
			}
		}
		i++;
	}
	cout << "DFA起始点为1" << endl;
	cout << "终点为";
	// 包含有图的end的节点就是结束点
	for (int i = 0; i < save.size(); i++) {
		string end = graph.end.name;
		if (sinv(save[i], end)) {
			cout << i + 1 << " ";
		}
	}
	cout << endl;
	for (int i = 0; i < save.size(); i++) {
		cout << i + 1 << "包含有结点：";
		for (int j = 0; j < save[i].size(); j++) {
			cout << save[i][j] << " ";
		}
		cout << endl;
	}
	
	
	vector> matrix;
	// vector初始化为 -
	for (int i = 0; i < node_num; i++) {
		vector temp;
		for (int j = 0; j < 2; j++) {
			temp.push_back("-");
		}
		matrix.push_back(temp);
	}
	// 状态矩阵赋值
	for (int i = 0; i < edge.size(); i++) {
		int x_index = atoi(edge[i][0].c_str()) - 1;
		int y_index = atoi(edge[i][2].c_str());
		matrix[x_index][y_index] = edge[i][1];
	}
	// 打印
	cout << "DFA状态矩阵：" << endl;
	cout << "     ";
	for (int i = 0; i < 2; i++) {
		cout << i << "    ";
	}
	cout << endl;
	for (int i = 0; i < node_num; i++) {
		cout << i + 1 << "    ";
		for (int j = 0; j < 2; j++) {
			cout << matrix[i][j] << "    ";
		}
		cout << endl;
	}
	return Graph();
}

// 根据NFA图计算状态矩阵
vector> CalMatrix(Graph graph, int opt_num) {
	vector> matrix;
	// vector初始化为 -
	for (int i = 0; i < step_number; i++) {
		vector temp;
		for (int j = 0; j < opt_num + 1; j++) {
			temp.push_back("-");
		}
		matrix.push_back(temp);
	}
	// 遍历边
	for (int i = 0; i < graph.edges.size(); i++) {
		if (graph.edges[i].option == '#') {
			// 对于空操作，横坐标为起始节点 - 1(从零开始)，纵坐标为最后一列，操作为 #
			if (matrix[stoi(graph.edges[i].start.name) - 1][opt_num] == "-") {
				matrix[stoi(graph.edges[i].start.name) - 1][opt_num] = graph.edges[i].end.name;
			}
			else {
				matrix[stoi(graph.edges[i].start.name) - 1][opt_num] += " ";
				matrix[stoi(graph.edges[i].start.name) - 1][opt_num] += graph.edges[i].end.name;
			}
		}
		else {
			// 对于空操作，横坐标为起始节点，纵坐标为操作数(认为字典为0~9)，操作为 #
			if (matrix[stoi(graph.edges[i].start.name) - 1][opt_num] == "-") {
				// char 转 int 使用ASCII码转换， 0~9 的ASCII码对应48~57
				matrix[stoi(graph.edges[i].start.name) - 1][int(graph.edges[i].option) - 48] = graph.edges[i].end.name;
			}
			else {
				matrix[stoi(graph.edges[i].start.name) - 1][opt_num] += " ";
				matrix[stoi(graph.edges[i].start.name) - 1][int(graph.edges[i].option) - 48] += graph.edges[i].end.name;
			}
		}
	}
	return matrix;
}

// 绘制NFA的状态矩阵
void drawNFA(vector> vec) {
	cout << "     ";
	for (int i = 0; i < 2; i++) {
		cout << i << "    ";
	}
	cout << "#" << endl;
	for (int i = 0; i < step_number; i++) {
		cout << i + 1 << "    ";
		for (int j = 0; j < 3; j++) {
			cout << vec[i][j] << "    ";
		}
		cout << endl;
	}
}

// 根据后缀表达式计算NFA图
Graph CalculateNFA(string exp) {
	Graph error;
	int len = exp.length();
	stack cal;  // 运算栈
	int step_num = 1;
	for (int i = 0; i < len; i++) {
		if (exp[i] == '+') {  // 取两个操作数运算
			if (!cal.empty()) {
				Graph a = cal.top();
				cal.pop();
				Graph b = cal.top();
				cal.pop();
				Graph temp = optional(a, b, step_num);
				cal.push(temp);
				step_num += 2;  // 可选操作会增加两个step节点
			}
		}
		else if (exp[i] == '.') {  // 取两个操作数运算
			if (!cal.empty()) {
				Graph a = cal.top();
				cal.pop();
				Graph b = cal.top();
				cal.pop();
				Graph temp = coupling(a, b, step_num);
				cal.push(temp);
				step_num += 1;  // 联结操作增加一个step节点
			}
		}
		else if (exp[i] == '*') {  // 取一个操作数运算
			if (!cal.empty()) {
				Graph a = cal.top();
				cal.pop();
				Graph temp = repeat(a, step_num);
				cal.push(temp);
				step_num += 2;  // 重复操作增加两个step节点
			}
		}
		else {
			// 操作符
			Graph temp = create(exp[i], step_num);  // 创建单操作的NFA
			cal.push(temp);
			step_num += 2;  // 创建操作会增加两个节点
		}
	}
	step_number = step_num - 1;  // 最终操作数
	if (!cal.empty()) {
		return cal.top();  // 栈顶的元素就是最后的计算结果
	}
	else {
		return error;
	}
}

int main() {
	vector exps = createExp();
	vector DFA;
	for (int i = 0; i < exps.size(); i++) {
		CompleteSign(exps[i]); // 整理式子
		exps[i] = toPostfix(exps[i]); // 转化为后缀表达式 
		DFA.push_back(NFAtoDFA(CalculateNFA(exps[i])));  // 生成DFA
	}
	string sen = "1001 101";
	if (judege(DFA, sen)) {
		cout << "匹配成功" << endl;
	}
	else {
		cout << "匹配失败" << endl;
	}
	
	return 0;
}

#pragma once
#include
#include
using namespace std;



// 标识符
struct Symbol {
	string name;  // 名称
	int is_terminal;  // 是否是终止符 1是，0不是，2为空, 3未初始化
	Symbol() {
		this->name = "";
		this->is_terminal = 3;
	}
	Symbol(string _name, int _is_terminal) {
		this->name = _name;
		this->is_terminal = _is_terminal;
	}
};

// 产生式，结构为 left -> right
struct Grammar {
	string left;  // 左部
	vector rigth;  // 右部
	Grammar() {
		this->left = "";
	}
	Grammar(string _left) {
		this->left = _left;
	}
	Grammar(string _left, vector _rigth) {
		this->left = _left;
		this->rigth = _rigth;
	}
};

bool have_ele(vector content, Symbol sb) {
	int len = content.size();
	for (int i = 0; i < len; i++) {
		if (content[i].name == sb.name) {
			return true;
		}
	}
	return false;
}

// First/Follow集结构
struct Set {
	Symbol name;  // 哪一个标识符的First/Follow集
	vector content;  // First/Follow集中的标识符集合
	Set() {
		this->name = Symbol();
	}
	Set(Symbol _name) {
		this->name = _name;
	}
	Set(Symbol _name, vector _content) {
		this->name = _name;
		this->content = _content;
	}
	Set(Symbol _name, Symbol _content) {
		this->name = _name;
		this->content.push_back( _content);
	}
	void Append(vector vec) {  // 添加函数，往集合后添加集合，去重添加
		
		int len = vec.size();
		for (int i = 0; i < len; i++) {
			if (!have_ele(this->content, vec[i])) {
				this->content.push_back(vec[i]);
			}
		}
	}
};

// 计算Follow集的时候的一个辅助数据结构
struct backNum {
	int start;
	int len;
	backNum(int _start, int _len) {
		this->start = _start;
		this->len = _len;
	}
};

// ll分析表行列与表
struct LlTable {
	vector rows;
	vector columns;
	vector> ll_table;
	LlTable(vector _rows, vector _columns, vector> _ll_table) {
		this->rows = _rows;
		this->columns = _columns;
		this->ll_table = _ll_table;
	}
};

// 多叉树结构
struct Node {
	Symbol name;
	vector vec;
	Node(){}
	Node(string _name) {
		this->name = Symbol(_name, 3);
	}
	Node(Symbol sym) {
		this->name = sym;
	}
};

#pragma once
#include
#include "head.h"
#include "auxiliary.h"



// 初始化First集合，生成终结符的集合，非终结符初始化为空
vector Initialize(vector gra) {
	vector ini_set;
	int len = gra.size();
	// 遍历所有产生式
	for (int i = 0; i < len; i++) {
		// 判断左部的标识符是否已经有了初始化的First集
		if (!have_set(gra[i].left, ini_set)) {
			// 产生式左部一定是非终结符
			ini_set.push_back(Set(Symbol(gra[i].left, 0)));  // 将非终结符的First集初始化放入集合中
		}
		// 对于右部
		int len2 = gra[i].rigth.size();
		// 判断右部每一个标识符是否有初始化的First集
		for (int j = 0; j < len2; j++) {
			if (!have_set(gra[i].rigth[j].name, ini_set)) {
				// 判断是否为终结符
				if (gra[i].rigth[j].is_terminal == 1) {
					// 如果是终结符，First集合为它自己
					ini_set.push_back(Set(gra[i].rigth[j], gra[i].rigth[j]));
				}
				else if (gra[i].rigth[j].is_terminal == 0) {
					// 如果是非终结符，First集合初始化为空
					ini_set.push_back(Set(Symbol(gra[i].rigth[j].name, 0)));
				}
				else {
					if (gra[i].rigth[j].is_terminal != 2) {
						// 为2是空
						if (gra[i].rigth[j].is_terminal == 3) {
							// 3未初始化
							cout << "产生式输入有未初始化的标识符，请检查后再尝试！" << endl;
						}
						else {
							// 其他为错误
							cout << "产生式输入有误，请检查后再尝试！" << endl;
						}
					}
				}
			}
		}
	}
	return ini_set;
}

// 生成First集
vector GenerateFirst(vector gra) {
	vector First = Initialize(gra); // 生成所有标识符初始化的First集

	while (true) {
		int start_num = getLength(First);  // 开始集合总长度

		// 对于每一个First集
		int first_len = First.size();
		for (int i = 0; i < first_len; i++) {
			// 遍历每一条产生式
			int gra_len = gra.size();
			for (int j = 0; j < gra_len; j++) {
				// 如果是非终结符并且左部和当前标识符相同
				if (gra[j].left == First[i].name.name && First[i].name.is_terminal == 0) {

					// 如果产生式右边第一个标识符为终结符或空
					if (gra[j].rigth[0].is_terminal == 1 || gra[j].rigth[0].is_terminal == 2) {
						// 如果集合中没有这个元素在当前First集中加上这个终结符或空
						if (!haveElement(First[i], gra[j].rigth[0].name)) {
							First[i].content.push_back(gra[j].rigth[0]);
						}
					}

					// 如果是非终结符
					else if (gra[j].rigth[0].is_terminal == 0) {
						bool flag = false;  // 标记
						// 遍历右部元素
						int right_length = gra[j].rigth.size();
						for (int k = 0; k < right_length; k++) {
							// 如果是非终结符
							if (gra[j].rigth[k].is_terminal == 0) {
								// 如果这个非终结符的First中有空,falg设置为真,否则为假
								if (haveElement(findFirst(First, gra[j].rigth[k].name),"#")) { flag = true; }
								else { flag = false; }
								// 去空加到first集中
								First[i].Append(removeEmpty(findFirst(First, gra[j].rigth[k].name).content));
							}
							// 如果有没有空的first，跳出循环
							if (!flag) {
								break;
							}
							// 如果遇到终结符，看flag
							if (gra[j].rigth[k].is_terminal == 1) {
								if (flag) {
									if (!haveElement(First[i], gra[j].rigth[k].name)) {
										// 如果遇到flag为真，并且first集中没有这个元素
										First[i].content.push_back(gra[j].rigth[k]);
									}
								}
								break;
							}
						}
						// 如果遍历所有结果都符合，加入#
						if (flag) {
							if (!haveElement(First[i], "#")) {
								First[i].content.push_back(Symbol("#", 2));
							}
						}
					}
					else {
						cout << "产生式未初始化，或产生式输入有误" << endl;
					}
				}
			}
		}
		
		int end_num = getLength(First);  // 结束集合总长度
		if (end_num <= start_num) {
			break;  // 如果集合长度停止增长，说明可以结束了
		}
	}

	return First;
}

// 生成Follow集
vector GenerateFollow(vector gra, vector First) {
	vector Follow;
	// 初始化所有非终结符的Follow集
	int f_len = First.size();
	for (int i = 0; i < f_len; i++) {
		if (First[i].name.is_terminal == 0) {
			// 如果是开始的非终结符，初始化加上$
			if (First[i].name.name == gra[0].left) {
				Follow.push_back(Set(First[i].name, Symbol("$", 4)));
			}
			// 其他的非终结符初始化为空
			else {
				Follow.push_back(Set(First[i].name));
			}
		}
	}

	while (true) {
		int start_num = getLength(Follow);  // 开始集合总长度

		// 对于每一个非终结符
		int fo_len = Follow.size();
		for (int i = 0; i < fo_len; i++) {
			// 遍历每一个产生式
			int gr_len = gra.size();
			for (int j = 0; j < gr_len; j++) {
				// 如果右部有这个元素
				if (isIn(gra[j], Follow[i].name)) {
					// 获取这个元素在集合中的
					int ele_start = leftNum(gra[j], Follow[i].name).start;
					int left_num = leftNum(gra[j], Follow[i].name).len;
					// 如果后面没有,将产生式左部的Follow加到当前Follow中
					if (left_num == 0) {
						Follow[i].Append(findFollow(Follow, gra[j].left).content);
					}
					// 如果后面是终结符，将这个终结符加到当前Follow中
					else if (gra[j].rigth[ele_start+1].is_terminal == 1) {
						// 如果没有这个终结符,添加
						if (!haveElement(Follow[i], gra[j].rigth[ele_start + 1].name)) {
							Follow[i].content.push_back(gra[j].rigth[ele_start + 1]);
						}
					}
					// 如果后面是非终结符
					else if (gra[j].rigth[ele_start + 1].is_terminal == 0) {
						bool flag = false;  // 标记
						// 遍历右部剩余的元素
						int right_length = gra[j].rigth.size();
						for (int k = ele_start + 1; k < right_length; k++) {
							// 如果是非终结符
							if (gra[j].rigth[k].is_terminal == 0) {
								// 如果这个非终结符的First中有空,falg设置为真,否则为假
								if (haveElement(findFirst(First, gra[j].rigth[k].name), "#")) { flag = true; }
								else { flag = false; }
								// 去空加到Follow集中
								Follow[i].Append(removeEmpty(findFirst(First, gra[j].rigth[k].name).content));
							}
							// 如果有没有空的First，跳出循环
							if (!flag) {
								break;
							}
							// 如果遇到终结符，看flag
							if (gra[j].rigth[k].is_terminal == 1) {
								if (flag) {
									if (!haveElement(Follow[i], gra[j].rigth[k].name)) {
										// 如果遇到flag为真，并且Follow集中没有这个元素
										Follow[i].content.push_back(gra[j].rigth[k]);
									}
								}
								break;
							}
						}
						// 如果右边所有标识符的First中都有空，将文法左部元素的Follow加入
						if (flag) {
							Follow[i].Append(findFollow(Follow, gra[j].left).content);
						}
					}
					else {
						cout << "产生式未初始化，或产生式输入有误" << endl;
					}
				}
			}
		}

		int end_num = getLength(Follow);  // 结束集合总长度
		if (end_num <= start_num) {
			break;  // 如果集合长度停止增长，说明可以结束了
		}
	}

	return Follow;
}

// 构造ll(1)分析表
LlTable createTable(vector gra, vector First, vector Follow) {
	vector> ll_table;
	vector rows;
	vector columns;
	// 终结符为列，非终结符为行
	int first_len = First.size();
	for (int i = 0; i < first_len; i++) {
		if (First[i].name.is_terminal == 0) {
			rows.push_back(First[i].name.name);
		}
		else if (First[i].name.is_terminal == 1) {
			columns.push_back(First[i].name.name);
		}
	}
	// 表项初始化为 -
	int row_len = rows.size();
	int column_len = columns.size();
	for (int i = 0; i < row_len; i++) {
		vector temp;
		for (int j = 0; j < column_len; j++) {
			temp.push_back("-");
		}
		ll_table.push_back(temp);
	}
	for (int i = 0; i < row_len; i++) {
		ll_table[i].push_back("-");
	}

	//对于所有First集
	for (int i = 0; i < first_len; i++) {
		if (First[i].name.is_terminal == 0) {
			// 对于First中的每个元素
			int con_len = First[i].content.size();
			for (int j = 0; j < con_len; j++) {
				// 如果是终结符
				if (First[i].content[j].is_terminal == 1) {
					int gra_len = gra.size();
					// 如果只有一个产生式
					if (is_unque(gra, First[i].name.name)) {
						// 遍历每一个产生式
						for (int k = 0; k < gra_len; k++) {
							if (gra[k].left == First[i].name.name) {
								ll_table[getIndex(First[i].name, rows, columns)][getIndex(First[i].content[j], rows, columns)] = to_string(k + 1);
							}
						}
					}
					else {
						// 遍历每一个产生式
						for (int k = 0; k < gra_len; k++) {
							// 如果名称相等并且左部第一个元素相同
							if (gra[k].left == First[i].name.name && gra[k].rigth[0].name == First[i].content[j].name) {
								ll_table[getIndex(First[i].name, rows, columns)][getIndex(First[i].content[j], rows, columns)] = to_string(k + 1);
							}
						}
					}
				}
				// 如果是空
				else if (First[i].content[j].is_terminal == 2) {
					// 找对应的Follow集
					int fo_len = Follow.size();
					for (int k = 0; k < fo_len; k++) {
						// 如果找到了
						if (First[i].name.name == Follow[k].name.name) {
							// 遍历Follow中所有元素
							int fcon_len = Follow[k].content.size();
							for (int m = 0; m < fcon_len; m++) {
								ll_table[getIndex(First[i].name, rows, columns)][getIndex(Follow[k].content[m], rows, columns)] = "#";
							}
						}
					}
				}
				else {
					cout << "Error!" << endl;
				}
			}
		}
	}
	LlTable table = LlTable(rows, columns, ll_table);
	return table;
}

bool Verification(vector gra, vector sen, LlTable table, Node &root) {
	stack s1;
	stack s2;  // 输入
	stack tree;  // 树结构
	tree.push(&root);  // 压入根节点
	s1.push(Symbol("$", 4));  // 先压入$
	s1.push(Symbol(gra[0].left, 0));  // 压入开始符号
	s2.push(Symbol("$", 4));
	ReverseOrder(s2, sen);  // 将输入语句反序入栈
	while (true) {
		Symbol temp1 = s1.top();  // 两个栈的栈顶
		Symbol temp2 = s2.top();
		// 如果temp1为非终结符
		if (temp1.is_terminal == 0) {
			//Grammar temp_gra= gra[atoi(table.ll_table[getIndex(temp1,table.rows,table.columns)][getIndex(temp2, table.rows, table.columns)].c_str())];
		// 查询ll分析表得出当前操作
			string func = table.ll_table[getIndex(temp1, table.rows, table.columns)][getIndex(temp2, table.rows, table.columns)];
			// 如果遇到"-",说明错误
			if (func == "-") {
				return false;
			}
			// 遇到空
			else if (func == "#") {
				// s1弹出栈顶
				s1.pop();
				tree.pop();
			}
			// 如果是产生式
			else {
				// 获取对应的产生式，下标要减一
				Grammar temp_gra = gra[atoi(func.c_str()) - 1];
				// s1弹出栈顶
				s1.pop();
				Node* pre = new Node();
				int r_len = temp_gra.rigth.size();
				for (int m = 0; m < r_len; m++) {
					pre->name = temp_gra.rigth[m];
					vector vec;
					pre->vec = vec;
					tree.top() -> vec.push_back(pre);
				}
				tree.pop();
				// s1反序入栈产生式的右部
				ReverseOrder(s1, temp_gra.rigth);
				ReverseOrder2(tree, temp_gra.rigth);
			}
		}
		// 如果是终结符
		else if (temp1.is_terminal == 1) {
			// 如果两个栈的栈顶相等
			if (temp2.is_terminal == 1 && temp1.name == temp2.name) {
				// 弹出栈顶
				s1.pop(); 
				tree.pop();
				s2.pop();
			}
			else {
				return false;
			}
		}
		// 如果是$
		else if (temp1.is_terminal == 4) {
			// 如果输入栈顶也为$
			if (temp2.is_terminal == 4) {
				return true;
			}
			// 不为$
			else {
				return false;
			}
		}
	}
}

#pragma once
#include "head.h"



// 判断标识符在Set集合中是否存在
bool have_set(string name, vector my_set) {
	int len = my_set.size();
	for (int i = 0; i < len; i++) {
		if (my_set[i].name.name == name) {
			return true;
		}
	}
	return false;
}

// 获取所有标识符First/Follow集的长度
int getLength(vector s) {
	int len = s.size();
	int num = 0;
	for (int i = 0; i < len; i++) {
		int temp = s[i].content.size();
		num += temp;
	}
	return num;
}

// 去标识符集合中的空
vector removeEmpty(vector vec) {
	int len = vec.size();
	for (int i = 0; i < len; i++) {
		if (vec[i].name == "#") {
			vector::iterator empty = vec.begin() + i;
			vec.erase(empty);
			break;
		}
	}
	return vec;
}


// 在所有标识符的First集中找name的First集
Set findFirst(vector First, string name) {
	int len = First.size();
	for (int i = 0; i < len; i++) {
		if (First[i].name.name == name) {
			return First[i];
		}
	}
	return Set();
}

// 判断某个First集中是否有某个元素
bool haveElement(Set first, string name) {
	int len = first.content.size();
	for (int i = 0; i < len; i++) {
		if (first.content[i].name == name) {
			return true;
		}
	}
	return false;
}

// 判断产生式右部是否有某个元素
bool isIn(Grammar gra, Symbol sym) {
	int len = gra.rigth.size();
	for (int i = 0; i < len; i++) {
		if (gra.rigth[i].name == sym.name) {
			return true;
		}
	}
	return false;
}



// 如果产生式右部有这个元素，获取后面还有的元素个数
backNum leftNum(Grammar gra, Symbol sym) {
	int len = gra.rigth.size();
	int k = 0;
	for (int i = 0; i < len; i++) {
		if (gra.rigth[i].name == sym.name) {
			k = i;
			break;
		}
	}
	return backNum(k, len - k - 1);
}

// 在所有标识符的Follow集中找name的Follow集(和找First一样，因为不好取名字所以写了两个函数)
Set findFollow(vector Follow, string name) {
	int len = Follow.size();
	for (int i = 0; i < len; i++) {
		if (Follow[i].name.name == name) {
			return Follow[i];
		}
	}
	return Set();
}

// 生成分析表时获取对应符号的下标
int getIndex(Symbol sym, vector rows, vector columns) {
	if (sym.is_terminal == 0) {
		int row_len = rows.size();
		for (int i = 0; i < row_len; i++) {
			if (rows[i] == sym.name) {
				return i;
			}
		}
		return -1;
	}
	else if (sym.is_terminal == 1) {
		int col_len = columns.size();
		for (int i = 0; i < col_len; i++) {
			if (columns[i] == sym.name) {
				return i;
			}
		}
		return -1;
	}
	else if (sym.is_terminal == 4) {
		int col_len = columns.size();
		return col_len;
	}
	else {
		return -1;
	}
}

// 判断非终结符在产生式中有一条还是多条产生式
bool is_unque(vector gra, string name) {
	int num = 0;
	int len = gra.size();
	for (int i = 0; i < len; i++) {
		if (gra[i].left == name) {
			num++;
		}
	}
	if (num > 1) {
		return false;
	}
	else {
		return true;
	}
}

// 反序入栈
void ReverseOrder(stack &s1,vector vec) {
	int len = vec.size();
	for (int i = len - 1; i >= 0; i--) {
		s1.push(vec[i]);
	}
}

void ReverseOrder2(stack &tree, vector vec) {
	int len = vec.size();
	for (int i = len - 1; i >= 0; i--) {
		Node* temp = new Node();
		temp->name = vec[i];
		tree.push(temp);
	}
}

#include
#include"function.h"
using namespace std;

void inputGrammar(vector& gra) {
	vector right;
	right.push_back(Symbol("T", 0)); right.push_back(Symbol("X", 0));
	gra.push_back(Grammar("E", right));  // E -> TX
	right.clear();
	right.push_back(Symbol("(", 1)); right.push_back(Symbol("E", 0)); right.push_back(Symbol(")", 1));
	gra.push_back(Grammar("T", right));  // T -> ( E )
	right.clear();
	right.push_back(Symbol("int", 1)); right.push_back(Symbol("Y", 0));
	gra.push_back(Grammar("T", right));  // T -> intY
	right.clear();
	right.push_back(Symbol("+", 1)); right.push_back(Symbol("E", 0));
	gra.push_back(Grammar("X", right));  // X -> +E
	right.clear();
	right.push_back(Symbol("#", 2));
	gra.push_back(Grammar("X", right));  // X -> #
	right.clear();
	right.push_back(Symbol("*", 1)); right.push_back(Symbol("T", 0));
	gra.push_back(Grammar("Y", right));  // Y -> *T
	right.clear();
	right.push_back(Symbol("#", 2));
	gra.push_back(Grammar("Y", right));  // Y -> #
}

void printGrammar(vector gra) {
	int len = gra.size();
	for (int i = 0; i < len; i++) {
		cout << "(" << i + 1 << ") ";
		cout << gra[i].left << " " << "-> ";
		int num = gra[i].rigth.size();
		for (int j = 0; j < num; j++) {
			cout << gra[i].rigth[j].name;
		}
		cout << endl;
	}
}

void pringSet(vector First) {
	int len = First.size();
	for (int i = 0; i < len; i++) {
		cout << First[i].name.name << "：{ ";
		int len2 = First[i].content.size();
		for (int j = 0; j < len2; j++) {
			cout << First[i].content[j].name << " ";
		}
		cout << "}" << endl;
	}
}

void printTable(LlTable table) {
	int co_len = table.columns.size();
	cout << " ";
	for (int i = 0; i < co_len; i++) {
		cout << "      " << table.columns[i];
	}
	cout << "      " << "$";
	cout << endl;
	int len1 = table.ll_table.size();
	for (int i = 0; i < len1; i++) {
		cout << table.rows[i] << "      ";
		int len2 = table.ll_table[i].size();
		for (int j = 0; j < len2; j++) {
			cout << table.ll_table[i][j] << "      ";
		}
		cout << endl;
	}
}

int main() {
	vector gra; 
	inputGrammar(gra);
	cout << "输入的产生式是：" << endl;
	printGrammar(gra);
	cout << endl;
	
	cout << "First集" << endl;
	vector First = GenerateFirst(gra);
	pringSet(First);
	cout << endl;

	cout << "Follow集" << endl;
	vector Follow = GenerateFollow(gra, First);
	pringSet(Follow);
	cout << endl;

	cout << "ll分析表" << endl;
	LlTable table = createTable(gra, First, Follow);
	printTable(table);
	cout << endl;

	vector sen;
	sen.push_back(Symbol("int", 1));
	sen.push_back(Symbol("*", 1));
	sen.push_back(Symbol("int", 1));
	sen.push_back(Symbol("+", 1));
	sen.push_back(Symbol("int", 1));
	// sen = int * int + int

	int sen_len = sen.size();
	cout << "要匹配的句子是：";
	for (int i = 0; i < sen_len; i++) {
		cout << sen[i].name << " ";
	}
	cout << endl;

	Node root = Node(gra[0].left);

	if (Verification(gra, sen, table, root)) {
		cout << "匹配成功" << endl;
	}
	else {
		cout << "匹配失败" << endl;
	}

	// 生成语法树的根节点为root

	return 0;
}

#pragma once
#include 
#include "head.h"
using namespace std;

// 构造文法
vector createGrammar() {
	vector Grammar;
	vector right;
	right.push_back(Symbol("A", 0));
	Grammar.push_back(Production(Symbol("S", 0), right));  // S -> A
	right.clear();
	right.push_back(Symbol("A", 0)); right.push_back(Symbol("+", 1)); right.push_back(Symbol("B", 0));
	Grammar.push_back(Production(Symbol("A", 0), right));  // A -> A + B
	right.clear();
	right.push_back(Symbol("a", 1));
	Grammar.push_back(Production(Symbol("A", 0), right));  // A -> a
	right.clear();
	right.push_back(Symbol("b", 1));
	Grammar.push_back(Production(Symbol("B", 0), right));  // B -> b
	right.clear();
	return Grammar;
}

//int getStatesLength(vector states) {
//	int num = 0;
//	int sLength = states.size();
//	for (int i = 0; i < sLength; i++) {
//		int iLength = states[i].items.size();
//		for (int j = 0; j < iLength; j++) {
//			num++;
//		}
//	}
//	return num;
//}

// 获取终止符
Symbol getLookahead(Item item, int index) {
	unsigned int iSize = item.production.rigth.size();
	// 如果后面没有了，返回item的终止符
	if (index + 1 >= iSize) {
		return item.lookahead;
	}
	// 否则返回后面的那一个终结符
	else {
		return item.production.rigth[index + 1];
	}
}

// 判断某个状态中是否有某个项
bool haveElement(State state, Item item) {
	for (unsigned int i = 0; i < state.items.size(); i++) {
		if (state.items[i].production.left.name == item.production.left.name && state.items[i].production.rigth.size() == item.production.rigth.size() && state.items[i].lookahead.name == item.lookahead.name) {
			return true;
		}
	}
	return false;
}

// 打印状态
void printItem(Item i) {
	cout << i.production.left.name << "->";
	for (unsigned int k = 0; k < i.production.rigth.size(); k++) {
		cout << i.production.rigth[k].name;
	}
	cout << "  index=" << i.index << "   终结符为" << i.lookahead.name;
}

// 判断两个vector是否相同
bool judge(vector a, vector b) {
	int al = a.size();
	int bl = b.size();
	if (al != bl) {
		return false;
	}
	else {
		for (int i = 0; i < al; i++) {
			if (a[i].name != b[i].name) {
				return false;
			}
		}
	}
	return true;
}

// 在文法中找对应的归约下标
int findReduce(vector Grammar, Item i) {
	for (unsigned int k = 0; k < Grammar.size(); k++) {
		if (Grammar[k].left.name == i.production.left.name && judge(Grammar[k].rigth, i.production.rigth)) {
			return k;
		}
	}
	return -1;
}

// 判断输入的string是终结符还是非终结符
bool isEnd(string a, vector Grammar) {
	for (unsigned int i = 0; i < Grammar.size(); i++) {
		if (Grammar[i].left.name == a) {
			return false;
		}
	}
	return true;
}

// 判断s是否在vec中
bool isIn(vector vec, string s) {
	for (unsigned int i = 0; i < vec.size(); i++) {
		if (vec[i] == s) {
			return true;
		}
	}
	return false;
}

// 构造分析表获取列名，所有标识符
vector getSymbols(vector Grammar) {
	vector res;
	for (unsigned int i = 0; i < Grammar.size(); i++) {
		for (unsigned int j = 0; j < Grammar[i].rigth.size(); j++) {
			if (Grammar[i].rigth[j].is_terminal == 1) {
				if (!isIn(res, Grammar[i].rigth[j].name)) {
					res.push_back(Grammar[i].rigth[j].name);  // 获取所有终结符
				}
			}
		}
	}
	res.push_back("$");
	for (unsigned int i = 1; i < Grammar.size(); i++) {
		if (!isIn(res, Grammar[i].left.name)) {
			res.push_back(Grammar[i].left.name);  // 获取所有非终结符
		}
	}
	return res;
}

// 获取下标
int getIndex(vector res, string a) {
	for (unsigned int i = 0; i < res.size(); i++) {
		if (res[i] == a) {
			return i;
		}
	}
	return -1;
}

// 根据传入的操作判断表应该填写什么内容
string writeTable(Option op) {
	if (op.option == 1) {  // 移进
		if (op.symbol.is_terminal == 0) {  // s?
			string res = "g";
			res += to_string(op.todo);
			return res;
		}
		else {  // g？
			string res = "s";
			res += to_string(op.todo);
			return res;
		}
	}
	else {  // 归约  r？
		if (op.todo == 0) {
			return "ac";
		}
		else {
			string res = "r";
			res += to_string(op.todo);
			return res;
		}
	}
}

// 打印LRtable
void printTable(LRTable LRtable) {
	int state_num = LRtable.table.size();
	int symbols_num = LRtable.symbols_vec.size();
	cout << "   ";
	for (int i = 0; i < symbols_num; i++) {
		cout << LRtable.symbols_vec[i] << "   ";
	}
	cout << endl;
	for (int i = 0; i < state_num; i++) {
		cout << i << "  ";
		for (int j = 0; j < symbols_num; j++) {
			cout << LRtable.table[i][j] << "  ";
		}
		cout << endl;
	}
}

// 产生式右部是否有非终结符
bool haveUnEnd(Production pro) {
	int len = pro.rigth.size();
	for (int i = 0; i < len; i++) {
		if (pro.rigth[i].is_terminal == 0) {
			return true;
		}
	}
	return false;
}

// 多叉树的遍历
void tranversal(Node* root) {
	vector nodes = root->vec;
	for (int i = 0; i < nodes.size(); ++i) {
		if (nodes[i]->vec.size() > 0)
			tranversal(nodes[i]);
		else
			cout << nodes[i]->name.name << ",";
	}
	cout << root->name.name << ",";
}

#pragma once
#include
#include
using namespace std;

// 标识符
struct Symbol {
	string name;  // 名称
	int is_terminal;  // 是否是终止符 1是，0不是，2为$，3未初始化
	Symbol() {
		this->name = "";
		this->is_terminal = 3;
	}
	Symbol(string _name, int _is_terminal) {
		this->name = _name;
		this->is_terminal = _is_terminal;
	}
};

// 产生式，结构为 left -> right
struct Production {
	Symbol left;  // 左部
	vector rigth;  // 右部
	Production() {
		this->left = Symbol();
	}
	Production(Symbol _left) {
		this->left = _left;
	}
	Production(Symbol _left, vector _rigth) {
		this->left = _left;
		this->rigth = _rigth;
	}
};

// LR表项
struct Item {
	Production production;  // 产生式
	int index;  // 当前的观察状态下标，代表当前已经看到了index-1，正在寻找index
	Symbol lookahead;  // 终止符
	Item(Production _production) {
		this->production = _production;
		this->index = 0;
		this->lookahead = Symbol("$",2);
	}
	Item(Production _production, int _index, Symbol _lookahead) {
		this->production = _production;
		this->index = _index;
		this->lookahead = _lookahead;
	}
};

// 状态
struct State {
	vector items;
	State(vector _items) {
		this->items = _items;
	}
};

// 记录移进归约
struct Option {
	int state;  // 状态
	Symbol symbol;  // 遇到的标识符
	int option;  // 移进归约还是goto
	int todo;  // 如果是移进，表示移进的状态，如果是归约，表示使用哪一条语句归约 
	Option(int _state, Symbol _symbol, int _option, int _todo) {
		this->state = _state;
		this->symbol = _symbol;
		this->option = _option;
		this->todo = _todo;
	}
};

// LR分析表结构
struct LRTable{
	vector symbols_vec;  // 表头
	vector> table;  // 表
	LRTable(vector _symbols_vec, vector> _table) {
		this->symbols_vec = _symbols_vec;
		this->table = _table;
	}
};

// 多叉树结构
struct Node {
	Symbol name;
	vector vec;
	int num;  // 树的层数
	Node() {
		this->num = -1;
	}
	Node(string _name) {
		this->name = Symbol(_name, 3);
	}
	Node(Symbol sym, int _num) {
		this->name = sym;
		this->num = _num;
	}
};

// 图结构
//struct Node {
//	Symbol name;
//	vector vec;
//	Node() {}
//	Node(string _name) {
//		this->name = Symbol(_name, 3);
//	}
//	Node(Symbol sym) {
//		this->name = sym;
//	}
//};

#pragma once
# include 
#include"auxiliary.h"

// 构造LR分析表
LRTable createTable(vector Grammar) {
	vector states;  // 状态集
	Item item0 = Item(Grammar[0]);  // 第一个LR表项, 观测下标为0, 终止符为$
	vector items0;  // 第0个状态
	items0.push_back(item0);  // 第0个状态放入第一个表项
	states.push_back(State(items0));  // 状态集中放入第0个状态
	vector options;
	unsigned m = 0;
	while (m < states.size()) {
		//cout << "状态:" << m << endl;
		unsigned int i = 0;
		while (i < states[m].items.size()) {
			//printItem(states[m].items[i]);
			//cout << endl;
			unsigned int index = states[m].items[i].index;
			// 如果观察的下一个符号为非终结符，判断时index + 1需要确保下标不越界
			if (index + 1 <= states[m].items[i].production.rigth.size() && states[m].items[i].production.rigth[index].is_terminal == 0) {
				// 从输入文法中寻找所有能从这个非终结符推导出的产生式
				for (unsigned int k = 0; k < Grammar.size(); k++) {
					if (Grammar[k].left.name == states[m].items[i].production.rigth[index].name) {
						// 这个项待加入, 观察下标0, 终止符为这个非终结符的下一个终结符
						Item temp_item = Item(Grammar[k], 0, getLookahead(states[m].items[i], index));
						// 如果没有这个项则加入
						if (!haveElement(states[m], temp_item)) {
							states[m].items.push_back(temp_item);
						}
					}
				}
			}
			i++;
		}

		set symbol_set;
		// 遍历所有项
		for (unsigned int j = 0; j < states[m].items.size(); j++) {
			// 如果观测的下一个不是结束，则状态转移
			if (states[m].items[j].index + 1 <= states[m].items[j].production.rigth.size()) {
				//cout << states[0].items[j].production.rigth[states[0].items[j].index].name << endl;
				// 这里先确定有多少个相同的状态
				symbol_set.insert(states[m].items[j].production.rigth[states[m].items[j].index].name);
			}
			// 否则归约
			else {
				// 归约
				//cout << "状态" << m << "遇到" << states[m].items[j].lookahead.name;
				//cout << "使用语句" << findReduce(Grammar, states[m].items[j]) << "进行归约" << endl;
				options.push_back(Option(m, states[m].items[j].lookahead, 0, findReduce(Grammar, states[m].items[j])));
			}
		}
		// 状态转移
		for (auto it = symbol_set.cbegin(); it != symbol_set.cend(); it++) {
			//cout << "状态" << m << "遇到" << *it << "转移到状态" << states.size() << endl;
			if (isEnd(*it, Grammar)) {  // 终结符
				options.push_back(Option(m, Symbol(*it, 1), 1, states.size()));
			}
			else {
				options.push_back(Option(m, Symbol(*it, 0), 1, states.size()));
			}
			vector items;
			// 再次遍历找符合条件的新states
			for (unsigned int j = 0; j < states[m].items.size(); j++) {
				// 如果下标那里的标识符相同则放入一个state中
				if (states[m].items[j].index + 1 <= states[m].items[j].production.rigth.size() && states[m].items[j].production.rigth[states[m].items[j].index].name == *it) {
					// 观测状态需要后移一位
					items.push_back(Item(states[m].items[j].production, states[m].items[j].index + 1, states[m].items[j].lookahead));
				}
			}
			states.push_back(State(items));
		}
		m++;
	}
	// 构造LR分析表
	int state_num = states.size();
	vector symbols_vec = getSymbols(Grammar);
	int symbols_num = symbols_vec.size();
	// 创建二维数组
	vector> LRtable;
	for (int i = 0; i < state_num; i++) {
		vector temp;
		LRtable.push_back(temp);
		for (int j = 0; j < symbols_num; j++) {
			LRtable[i].push_back("--");
		}
	}
	// 填写状态
	for (unsigned int i = 0; i < options.size(); i++) {
		LRtable[options[i].state][getIndex(symbols_vec, options[i].symbol.name)] = writeTable(options[i]);
	}
	return LRTable(symbols_vec, LRtable);
}

// 匹配每一步做的工作
void doNext(LRTable LRtable, vector Grammar, string next, string now_str, stack& state_stack, stack& symbol_stack, int& index, stack& pro_stack) {
	if (next == "ac") {
		cout << "接受" << endl;
		index++;
		//接受
		return;
	}
	else if (next == "--") {
		cout << "错误" << endl;
		index = INT_MAX;
		// 错误
		return;
	}
	else if (next[0] == 's') {
		// 转换状态,状态栈压入s后的状态,符号栈压入传入的符号,下标后移
		int state = int(next[1] - 48);  // ASCII码 - 48
		state_stack.push(state);
		symbol_stack.push(now_str);
		index++;
	}
	else if (next[0] == 'r') {
		// 归约 查询用哪一条产生式归约，状态栈符号栈弹出，符号栈压入归约的符号 状态栈查询goto语句压栈
		int reduce = int(next[1] - 48);
		pro_stack.push(Grammar[reduce]);  // 压入归约的产生式 
		int len = Grammar[reduce].rigth.size();
		for (int i = 0; i < len; i++) {  // 出栈
			state_stack.pop();
			symbol_stack.pop();
		}
		symbol_stack.push(Grammar[reduce].left.name);
		// 递归查询状态栈并压入 此时下标应该是两个栈的栈顶
		string next = LRtable.table[state_stack.top()][getIndex(LRtable.symbols_vec, symbol_stack.top())];
		// 递归压入状态栈
		doNext(LRtable, Grammar, next, now_str, state_stack, symbol_stack, index, pro_stack);
	}
	else if (next[0] == 'g') {
		// 转换到s后的那个状态 状态栈压入
		int state = int(next[1] - 48);
		state_stack.push(state);
	}
}

stack Matching(string sentence, LRTable LRtable, vector Grammar) {
	sentence += "$";  // 先给要匹配的句子加一个结束符
	stack state_stack;  // 状态栈
	stack symbol_stack;  // 符号栈
	stack pro_stack;  // 归约压栈，用来生成语法树
	state_stack.push(0);  // 状态栈初始压入0
	symbol_stack.push("$");  // 符号栈初始压入结束符
	int len = sentence.length();
	// 遍历要匹配的语句，下标只有移进才加一
	for (int i = 0; i < len; ) {
		string temp = "";
		temp += sentence[i];  // temp为当前语句遇到的标识符
		//cout << "此时遇到"<< temp << endl;
		//cout << "状态栈顶" << state_stack.top() << "  符号栈顶" << symbol_stack.top() << endl;
		// 查表得到下一步指示 此时下标是状态栈的栈顶和遍历到当前的标识符
		string next = LRtable.table[state_stack.top()][getIndex(LRtable.symbols_vec, temp)];
		//cout << "查询得到下一步为" << next << endl;
		//  根据查询的进行下一步操作
		doNext(LRtable, Grammar, next, temp, state_stack, symbol_stack, i, pro_stack);
	}
	return pro_stack;
}

vector createTree(stack pro_stack, vector Grammar) {
	// 第一个节点
	Node* root = new Node;
	root->name = Grammar[0].left;
	root->vec.push_back(new Node(Grammar[0].rigth[0], 1));
	root->num = 0;
	int i = 1;
	vectorsave_tree;
	save_tree.push_back(root);
	// 遍历所有栈内的产生式
	while (!pro_stack.empty()) {
		// 将当前产生式的右部作为左部的子节点连接
		Node* pre = new Node;
		pre->num = i;
		pre->name = pro_stack.top().left;
		int len = pro_stack.top().rigth.size();
		for (int i = 0; i < len; i++) {
			Node* temp = new Node;
			temp->name = pro_stack.top().rigth[i];
			temp->num = pre->num + 1;  // 下一层
			pre->vec.push_back(temp);
		}
		// 存储
		save_tree.push_back(pre);
		if (haveUnEnd(pro_stack.top())) {
			i++;
		}
		pro_stack.pop();
	}
	return save_tree;
}

void connect(vector save_tree) {
	int len = save_tree.size();
	// 从后往前遍历，当前要往后添加的
	for (int i = len -1 ; i > 0 ; i--) {
		//cout << "当前是" << save_tree[i]->name.name << "层数为" << save_tree[i]->num << endl;
		// 当前判断的层数在其他节点寻找相同的
		for (int j = 0; j < len; j++) {
			//cout << "寻找" << save_tree[j]->name.name << "层数为"<< save_tree[j]->num << "的子节点" << endl;
			int child_len = save_tree[j]->vec.size();
			for (int k = 0; k < child_len; k++) {
				//cout << "找子节点" << save_tree[j]->vec[k]->name.name << "层数为" << save_tree[j]->vec[k]->num << endl;
				// 如果某个子节点的层数和名称都和当前的这个相同
				if (save_tree[j]->vec[k]->name.name == save_tree[i]->name.name && save_tree[j]->vec[k]->num == save_tree[i]->num) {
					//cout << "连接" << endl;
					//cout << save_tree[i]->name.name << endl;
					//cout << save_tree[i]->num << endl;
					// 连接子节点数组
					save_tree[j]->vec[k]->vec = save_tree[i]->vec;
				}
			}
		}
	}
	tranversal(save_tree[0]);
}

#include 
#include "auxiliary.h"
#include "function.h"

int main() {
	vector Grammar = createGrammar();  // 文法
	LRTable LRtable = createTable(Grammar);
	cout << "LR分析表构造如下" << endl;
	printTable(LRtable);
	string sen = "a+b+b";
	cout << "输入: " << sen << endl;
	stack p = Matching(sen, LRtable, Grammar);
	// 语法树根节点
	vector a =  createTree(p,Grammar);
	cout << "遍历多叉树" << endl;
	connect(a);

}