1. Toy模板网首页
  2. > Toy博客

编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）

10月前 作者：KeepCoding♪Toby♪ 分类：Toy博客 阅读(38) 违法举报

这篇具有很好参考价值的文章主要介绍了编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

从正则到自动机：正则表达式/正规式转换为NFA

【本文内容摘要】
（1）从中缀表达式转换为后缀表达式
（2）从后缀表达式转换为NFA
（3）打印NFA大致内容
（4）生成dot文件。
（5）完整代码
如果本文对各位看官有用的话，请记得给一个免费的赞哦（收藏也不错）！

一、从中缀表达式转换为后缀表达式

下面链接详细讲述了如何从中缀表达式转换为后缀表达式，与本文的区别为符号优先关系表中部分元素不同，看完链接中的内容，我想下面的代码也可以理解了~

中缀表达式构建后缀表达式

//类里的各类元素定义
infixToPostfix::infixToPostfix(const string& infix_expression) : infix(infix_expression), postfix("") {
	isp = { {'+', 3}, {'|', 5}, {'*', 7},  {'(', 1}, {')', 8}, {'#', 0} };
	icp = { {'+', 2}, {'|', 4}, {'*', 6}, {'(', 8}, {')', 1}, {'#', 0} };
}

int infixToPostfix::is_letter(char check) {
	if (check >= 'a' && check <= 'z' || check >= 'A' && check <= 'Z')
		return true;
	return false;
}

int infixToPostfix::ispFunc(char c) {
	int priority = isp.count(c) ? isp[c] : -1;
	if (priority == -1) {
		cerr << "error: 出现未知符号！" << endl;
		exit(1);  // 异常退出
	}
	return priority;
}

int infixToPostfix::icpFunc(char c) {
	int priority = icp.count(c) ? icp[c] : -1;
	if (priority == -1) {
		cerr << "error: 出现未知符号！" << endl;
		exit(1);  // 异常退出
	}
	return priority;
}

void infixToPostfix::inToPost() {
	string infixWithHash = infix + "#";
	stack<char> stack;
	int loc = 0;
	while (!stack.empty() || loc < infixWithHash.size()) {
		if (is_letter(infixWithHash[loc])) {
			postfix += infixWithHash[loc];
			loc++;
		}
		else {
			char c1 = (stack.empty()) ? '#' : stack.top();
			char c2 = infixWithHash[loc];
			if (ispFunc(c1) < icpFunc(c2)) { // 栈顶操作符优先级低于当前字符，将当前字符入栈
				stack.push(c2);
				loc++;
			}
			else if (ispFunc(c1) > icpFunc(c2)) {  // 栈顶操作符优先级高于当前字符，将栈顶操作符出栈并添加到后缀表达式
				postfix += c1;
				stack.pop();
			}
			else {
				if (c1 == '#' && c2 == '#') { // 遇到两个 #，表达式结束
					break;
				}
				stack.pop(); //其中右括号遇到左括号时会抵消，左括号出栈，右括号不入栈
				loc++;
			}
		}
	}
}

string infixToPostfix::getResult() {
	postfix = ""; // 清空结果
	inToPost();
	return postfix;
}

补充：关于在中缀表达式中添加"+"
add_join_symbol函数的作用是在正则表达式中添加连接符号+，以便于后续的中缀转后缀操作。这是因为正则表达式中的连接运算是隐含的，没有明确的符号表示，例如ab表示a和b的连接，但是在中缀转后缀的过程中，需要有一个明确的符号来表示连接运算的优先级，否则会导致歧义或错误。例如，如果没有添加连接符号，那么a|b*的后缀表达式可能是ab*|或者a|b*，前者表示a或者b的闭包，后者表示a或者b的连接，这两者的含义是不同的。因此，为了避免这种情况，需要在正则表达式中添加连接符号+，表示连接运算的优先级高于或运算和闭包运算，举个栗子~，a(a|b)* ，加’+'后的表达式：a+(a|b)*，表示a和(a|b)*是拼接起来的。

//添加连接符号
string add_join_symbol(string add_string)
{
	int length = add_string.size();
	int return_string_length = 0;
	char* return_string = new char[2 * length + 2];//最多是两倍
	char first, second;
	for (int i = 0; i < length - 1; i++)
	{
		first = add_string.at(i);
		second = add_string.at(i + 1);
		return_string[return_string_length++] = first;
		//要加的可能性如ab 、 *b 、 a( 、 )b 等情况
		//若第二个是字母、第一个不是'('、'|'都要添加
		if (first != '(' && first != '|' && is_letter(second))
		{
			return_string[return_string_length++] = '+';
		}
		//若第二个是'(',第一个不是'|'、'(',也要加
		else if (second == '(' && first != '|' && first != '(')
		{
			return_string[return_string_length++] = '+';
		}
	}
	//将最后一个字符写入second
	return_string[return_string_length++] = second;
	return_string[return_string_length] = '\0';
	string STRING(return_string);
	cout << "加'+'后的表达式：" << STRING << endl;
	return STRING;
}

二、从后缀表达式转换为NFA

（A）本文用到的结构体

  1. node：
    node 表示NFA中的节点，每个节点有一个名称 nodeName，用于标识唯一的状态。

  2. edge：
    edge 表示NFA中的边，包括起始节点 startName、目标节点 endName 和转换符号 tranSymbol。
    startName 表示边的起始状态。
    endName 表示边的目标状态。
    tranSymbol 表示边上的转换符号，即从起始状态到目标状态的转换条件。

  3. elem：
    elem 表示NFA的组成单元，它是一个大的NFA单元，可以由多个小单元通过规则拼接而成。
    edgeCount 表示该NFA拥有的边的数量。
    edgeSet 是一个包含边的数组，最多存储100条边。
    startName 表示NFA的开始状态。
    endName 表示NFA的结束状态。

（B）一些准备工作（后续需要用到的函数）

（a）创建新节点函数

//创建新节点
node new_node()
{
	node newNode;
	newNode.nodeName = nodeNum + 65;//将名字用大写字母表示
	nodeNum++;
	return newNode;
}

这里通过nodeNum + 65的方式为新节点分配一个唯一的名称，其中nodeNum是一个全局变量，表示节点的数量。比如第一个节点（nodeNum = 0时），这里将数字转换为大写字母（ASCII码为0+65 = 65），初始值为 ‘A’。

（b）组成单元拷贝函数 elem_copy
用于将一个 NFA 组成单元（elem 结构体）的内容复制到另一个组成单元中。

//组成单元拷贝函数
void elem_copy(elem& dest, elem source)
{
	for (int i = 0; i < source.edgeCount; i++) {
		dest.edgeSet[dest.edgeCount+i] = source.edgeSet[i];
	}
	dest.edgeCount += source.edgeCount;
}

（C）Thompson构造法（一些运算关系）

Thompson构造法（from 百度百科）

  1. 递归终点
    对于正则表达式为ε或者只由一个符号构成的情况，则无需继续递归，对应的NFA可以直接由下列规则给出：
    空表达式ε直接转化为：
    编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构

    字母表中的单个符号a直接转化为：
    编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构

2.子表达式运算的构造规则

  1. 并运算 (s|t):

    • 通过 ε 转移，状态 q 可以直接到达 N(s) 或 N(t) 的初态。
    • N(s) 或 N(t) 原来的终态可以通过 ε 转移直接到达整个 NFA 的新终态。
      编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构

  2. 连接运算 (st):

    • N(s) 的初态成为新的 NFA 的初态。
    • 原来 N(s) 的终态成为 N(t) 的初态。
    • 原来 N(t) 的终态成为新的 NFA 的终态。
      编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构

  3. Kleene闭包 (s):

    • 将新表达式的初态和终态以及夹在中间的子表达式的 NFA N(s) 连接起来的 ε 转移，使得可以选择经过或者不经过子表达式。
    • 从 N(s) 的终态到初态的 ε 转移，使得 s 可以重复任意多次。
      编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构

  4. 加括号的表达式 (s):

    • 直接转化为 N(s) 自身即可。

下面根据Thompson构造法的规则来实现各种算法：

（a）处理单个字符（规则1）
编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构
上图为a

//处理 a
elem act_Elem(char c) 
{
	//新节点
	node startNode = new_node();
	node endNode = new_node();

	//新边
	edge newEdge;
	newEdge.startName = startNode;
	newEdge.endName = endNode;
	newEdge.tranSymbol = c;

	//新NFA组成元素（小的NFA元素/单元)
	elem newElem;
	newElem.edgeCount = 0;	//初始状态
	newElem.edgeSet[newElem.edgeCount++] = newEdge;
	newElem.startName = newElem.edgeSet[0].startName;
	newElem.endName = newElem.edgeSet[0].endName;
	
	return newElem;
}

（b）处理a|b（规则2.1）
编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构
上图为a|b
step1：创建一个新的elem结构体，用于存储或运算的NFA的边集合、边数量、开始节点和结束节点。然后，创建两个新的节点，分别作为开始节点和结束节点，并调用了一个自定义的函数new_node()，它会给每个节点分配一个唯一的名称（用大写字母表示）。
step2：创建了四条空串转换的边，分别连接开始节点和两个子表达式的开始节点，以及两个子表达式的结束节点和结束节点。这样就可以从开始节点通过空串转换选择进入任意一个子表达式，然后从子表达式的结束节点通过空串转换到达结束节点。
step3：将两个子表达式的边集合合并到新的边集合中，并更新边的数量。这样就可以保留两个子表达式的内部转换关系。

//处理a|b
elem act_Unit(elem fir, elem sec)
{
	elem newElem;
	newElem.edgeCount = 0;
	edge edge1, edge2, edge3, edge4;
	
	//获得新的状态节点
	node startNode = new_node();
	node endNode = new_node();
	
	//构建e1（连接起点和AB的起始点A）
	edge1.startName = startNode;
	edge1.endName = fir.startName;
	edge1.tranSymbol = '#';

	//构建e2（连接起点和CD的起始点C）
	edge2.startName = startNode;
	edge2.endName  = sec.startName;
	edge2.tranSymbol = '#';

	//构建e3（连接AB的终点和终点）
	edge3.startName = fir.endName;
	edge3.endName = endNode;
	edge3.tranSymbol = '#';

	//构建e4（连接CD的终点和终点）
	edge4.startName = sec.endName;
	edge4.endName = endNode;
	edge4.tranSymbol = '#';

	//将fir和sec合并
	elem_copy(newElem, fir);
	elem_copy(newElem, sec);

	//新构建的4条边
	newElem.edgeSet[newElem.edgeCount++] = edge1;
	newElem.edgeSet[newElem.edgeCount++] = edge2;
	newElem.edgeSet[newElem.edgeCount++] = edge3;
	newElem.edgeSet[newElem.edgeCount++] = edge4;

	newElem.startName = startNode;
	newElem.endName = endNode;

	return newElem;
}

（c）处理N(s)N(t)（规则2.2）

编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构
上图为N(s)N(t)即(a|b)(c|d)
step1：函数接收两个elem结构体作为参数，分别表示两个子表达式的NFA，我们可以用N(s)和N(t)来表示它们。
step2：函数的目标是将N(s)和N(t)连接起来，形成一个新的NFA，我们可以用N(st)来表示它。N(st)的开始状态就是N(s)的开始状态，N(st)的结束状态就是N(t)的结束状态。
step3：函数的关键步骤是将N(s)的结束状态和N(t)的开始状态合并为一个状态（图中这个合并后的状态就是F），这样就可以从N(s)的结束状态直接转移到N(t)的开始状态，实现连接运算。为了做到这一点，函数遍历了N(t)的所有边，如果边的起始节点或结束节点是N(t)的开始状态，就将它们替换为N(s)的结束状态。
step4：函数将N(t)的边集合复制到N(s)的边集合中，并更新边的数量。这样，就可以保留N(s)和N(t)的内部转换关系，同时添加了N(s)和N(t)之间的转换关系。
step5：函数将N(s)的开始状态和N(t)的结束状态赋值给一个新的elem结构体，并将其返回作为函数的输出。

//处理 N(s)N(t)
elem act_join(elem fir, elem sec)
{
	//将fir的结束状态和sec的开始状态合并，将sec的边复制给fir，将fir返回
	//将sec中所有以StartState开头的边全部修改
	for (int i = 0; i < sec.edgeCount; i++) {
		if (sec.edgeSet[i].startName.nodeName.compare(sec.startName.nodeName) == 0)
		{
			sec.edgeSet[i].startName = fir.endName; //该边e1的开始状态就是N(t)的起始状态
		}
		else if (sec.edgeSet[i].endName.nodeName.compare(sec.startName.nodeName) == 0) {
			sec.edgeSet[i].endName = fir.endName; //该边e2的结束状态就是N(t)的起始状态
		}
	}
	sec.startName = fir.endName;

	elem_copy(fir, sec);

	//将fir的结束状态更新为sec的结束状态
	fir.endName = sec.endName;
	return fir;
}

（d）处理a*（规则2.3）
编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构
上图为a*
step1：首先，创建一个新的elem结构体，用于存储闭包运算的NFA的边集合、边数量、开始节点和结束节点。
step2：然后，创建两个新的节点，分别作为开始节点和结束节点，并调用了一个自定义的函数new_node()，它会给每个节点分配一个唯一的名称（用大写字母表示）。
step3：接着，创建了四条空串转换的边，分别连接开始节点和结束节点，开始节点和子表达式的开始节点，子表达式的结束节点和子表达式的开始节点，子表达式的结束节点和结束节点。这样就可以从开始节点通过空串转换到结束节点，或者从开始节点通过空串转换到子表达式，然后从子表达式的结束节点通过空串转换回子表达式的开始节点，重复任意次，最后从子表达式的结束节点通过空串转换到结束节点，实现闭包运算。
step4：然后，将子表达式的边集合复制到新的边集合中，并更新边的数量。这样就可以保留子表达式的内部转换关系。
step5：将开始节点和结束节点的名称赋值给新的elem结构体，并将其返回作为函数的输出。

//处理a*
elem act_star(elem Elem)
{
	elem newElem;
	newElem.edgeCount = 0;
	edge edge1, edge2, edge3, edge4;

	//获得新状态节点
	node startNode = new_node();
	node endNode = new_node();

	//e1
	edge1.startName = startNode;
	edge1.endName = endNode;
	edge1.tranSymbol = '#';	//闭包取空串

	//e2
	edge2.startName = Elem.endName;
	edge2.endName = Elem.startName;
	edge2.tranSymbol = '#';

	//e3
	edge3.startName = startNode;
	edge3.endName = Elem.startName;
	edge3.tranSymbol = '#';

	//e4
	edge4.startName = Elem.endName;
	edge4.endName = endNode;
	edge4.tranSymbol = '#';

	//构建单元
	elem_copy(newElem, Elem);

	//将新构建的四条边加入EdgeSet
	newElem.edgeSet[newElem.edgeCount++] = edge1;
	newElem.edgeSet[newElem.edgeCount++] = edge2;
	newElem.edgeSet[newElem.edgeCount++] = edge3;
	newElem.edgeSet[newElem.edgeCount++] = edge4;

	//构建NewElem的启示状态和结束状态
	newElem.startName = startNode;
	newElem.endName = endNode;

	return newElem;
}

（e）规则2.4：N（s）转换为自身即可

（D）将正则表达式转换为NFA

这里解释代码即可：

/**表达式转NFA处理函数,返回最终的NFA集合
*/
elem express_to_NFA(string expression)
{
	int length = expression.size();
	char element;
	elem Elem, fir, sec;
	stack<elem> STACK;
	for (int i = 0; i < length; i++)
	{
		element = expression.at(i);
		switch (element)
		{
		case '|':
			sec = STACK.top();
			STACK.pop();
			fir = STACK.top();
			STACK.pop();
			Elem = act_Unit(fir, sec);
			STACK.push(Elem);
			break;
		case '*':
			fir = STACK.top();
			STACK.pop();
			Elem = act_star(fir);
			STACK.push(Elem);
			break;
		case '+':
			sec = STACK.top();
			STACK.pop();
			fir = STACK.top();
			STACK.pop();
			Elem = act_join(fir, sec);
			STACK.push(Elem);
			break;
		default:
			Elem = act_Elem(element);
			STACK.push(Elem);
		}
	}
	cout << "已将正则表达式转换为NFA!" << endl;
	Elem = STACK.top();
	STACK.pop();

	return Elem;
}

  1. 变量定义以及含义：

    • expression: 输入的正则表达式字符串。
    • element: 正则表达式中的单个符号。
    • Elem: elem结构体，表示一个NFA的组成单元。
    • fir和sec: 两个子表达式的NFA。
    • STACK: 存储和操作NFA的组成单元的栈。

  2. 遍历正则表达式：

    • 对于每个符号执行不同的操作。
      • 如果符号是 |，弹出两个NFA，调用 act_Unit(fir, sec) 构造或运算的NFA，将结果压入栈。
      • 如果符号是 *，弹出一个NFA，调用 act_star(fir) 构造闭包运算的NFA，将结果压入栈。
      • 如果符号是 +，弹出两个NFA，调用 act_join(fir, sec) 构造连接运算的NFA，将结果压入栈。
      • 如果符号是其他字符，调用 act_Elem(element) 构造单个字符的NFA，将结果压入栈。

  3. 返回结果：

    • 从栈中弹出最后一个NFA的组成单元，赋值给 Elem，并将其作为函数的输出返回。

三、生成dot文件

NFA经过上面步骤已经基本成型了，下面讲一讲dot文件。

根据百度百科：graphviz （英文：Graph Visualization Software的缩写）是一个由AT&T实验室启动的开源工具包，用于绘制DOT语言脚本描述的图形。

简单理解，生成这个dot文件丢给这个工具就可以实现可视化，我依据我的NFA实现了一个生成dot文件的函数。

//生成NFAdot文件
void generateDotFile_NFA(const elem& nfa) {
	std::ofstream dotFile("nfa_graph.dot");

	if (dotFile.is_open()) {
		dotFile << "digraph NFA {\n";
		dotFile << "  rankdir=LR;  // 横向布局\n\n";
		dotFile << " node [shape = circle];   // 状态节点\n\n";

		dotFile << nfa.endName.nodeName << " [shape=doublecircle];\n";
		// 添加 NFA 状态
		dotFile << "  " << nfa.startName.nodeName << " [label=\"Start State: " << nfa.startName.nodeName << "\"];\n";
		dotFile << "  " << nfa.endName.nodeName << " [label=\"End State: " << nfa.endName.nodeName << "\"];\n";

		// 添加 NFA 转移
		for (int i = 0; i < nfa.edgeCount; i++) {
			const edge& currentEdge = nfa.edgeSet[i];
			dotFile << "  " << currentEdge.startName.nodeName << " -> " << currentEdge.endName.nodeName << " [label=\"" << currentEdge.tranSymbol << "\"];\n";
		}

		dotFile << "}\n";

		dotFile.close();
		std::cout << "NFA DOT file generated successfully.\n";
	}
	else {
		std::cerr << "Unable to open NFA DOT file.\n";
	}
}

代码思路：
step1：创建一个输出流对象dotFile，并尝试打开一个名为"nfa_graph.dot"的文件，用于存储dot文件的内容。
step2：如果文件打开成功，向文件中写入了一些dot语法的规则，例如：

  • digraph NFA表示这是一个有向图，图的名字是NFA。
  • rankdir=LR表示图的布局方向是从左到右。
  • node [shape = circle]表示图中的节点的形状是圆形。
  • nfa.endName.nodeName [shape=doublecircle]表示NFA的结束状态的节点的形状是双圆形。

Step3：向文件中写入了NFA的状态和转移的信息，例如：

  • nfa.startName.nodeName [label="Start State: nfa.startName.nodeName"]表示NFA的开始状态的节点的标签是"Start State: nfa.startName.nodeName"，其中nfa.startName.nodeName是节点的名称。
  • nfa.endName.nodeName [label="End State: nfa.endName.nodeName"]表示NFA的结束状态的节点的标签是"End State: nfa.endName.nodeName"，其中nfa.endName.nodeName是节点的名称。
  • currentEdge.startName.nodeName -> currentEdge.endName.nodeName [label="currentEdge.tranSymbol"]表示NFA的一条转移的边，从currentEdge.startName.nodeName节点指向currentEdge.endName.nodeName节点，边上的标签是currentEdge.tranSymbol，表示转移的符号。

step4：向文件中写入了一个右花括号，表示图的结束，然后关闭文件，并输出一条提示信息，表示NFA的dot文件生成成功。如果文件打开失败，输出一条错误信息，表示无法打开NFA的dot文件。

四、案例测试

  1. (a|b|c)*
    编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构

编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构
上面为在命令提示符中到指定目录下（你dot文件所在的目录下）输入指令将dot文件生成图片，然后打开visual studio目录，找到nfa.png：
编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构

编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构
编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构文章来源地址https://www.toymoban.com/news/detail-795799.html

  1. a(b|c)*de
    编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构
    编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）,编译原理,算法,编译原理,数据结构

五、C++代码完整实现

//head.h
#ifndef HEAD_H
#define HEAD_H

#include <iostream>
#include <stdio.h>
#include <cctype>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <vector>
#include<iterator>
#include <fstream>

using namespace std;

//NFA的节点
struct node
{
	string nodeName;
};

//NFA的边
struct edge
{
	node startName;	//起始点
	node endName;	//目标点
	char tranSymbol;	//转换符号
};

//NFA的组成单元，一个大的NFA单元可以是由很多小单元通过规则拼接起来
struct elem
{
	int edgeCount;	//边数
	edge edgeSet[100];	//该NFA拥有的边
	node startName;	//开始状态
	node endName; //结束状态
};

//创建新节点
node new_node();

//处理 a
elem act_Elem(char);

//处理a|b
elem act_Unit(elem,elem);

//组成单元拷贝函数
void elem_copy(elem&, elem);

//处理ab
elem act_join(elem, elem);

//处理 a*
elem act_star(elem);

void input(string&);

string add_join_symbol(string);	//两个单元拼接在一起相当于一个+

class infixToPostfix {
public:
	infixToPostfix(const string& infix_expression);

	int is_letter(char check);
	int ispFunc(char c);
	int icpFunc(char c);
	void inToPost();
	string getResult();

private:
	string infix;
	string postfix;
	map<char, int> isp;
	map<char, int> icp;
};

elem express_to_NFA(string);

void Display(elem);

int is_letter(char check);

void generateDotFile_NFA(const elem& nfa);
#endif

//Func.cpp
#include "head.h"

int nodeNum = 0;

//创建新节点
node new_node()
{
	node newNode;
	newNode.nodeName = nodeNum + 65;//将名字用大写字母表示
	nodeNum++;
	return newNode;
}

//接收输入正规表达式
void input(string& RE)
{
	cout << "请输入正则表达式：  （操作符：() * |;字符集：a~z A~Z）" << endl;
	cin >> RE;
}


//组成单元拷贝函数
void elem_copy(elem& dest, elem source)
{
	for (int i = 0; i < source.edgeCount; i++) {
		dest.edgeSet[dest.edgeCount+i] = source.edgeSet[i];
	}
	dest.edgeCount += source.edgeCount;
}

//处理 a
elem act_Elem(char c) 
{
	//新节点
	node startNode = new_node();
	node endNode = new_node();

	//新边
	edge newEdge;
	newEdge.startName = startNode;
	newEdge.endName = endNode;
	newEdge.tranSymbol = c;

	//新NFA组成元素（小的NFA元素/单元)
	elem newElem;
	newElem.edgeCount = 0;	//初始状态
	newElem.edgeSet[newElem.edgeCount++] = newEdge;
	newElem.startName = newElem.edgeSet[0].startName;
	newElem.endName = newElem.edgeSet[0].endName;
	
	return newElem;
}

//处理a|b
elem act_Unit(elem fir, elem sec)
{
	elem newElem;
	newElem.edgeCount = 0;
	edge edge1, edge2, edge3, edge4;
	
	//获得新的状态节点
	node startNode = new_node();
	node endNode = new_node();
	
	//构建e1（连接起点和AB的起始点A）
	edge1.startName = startNode;
	edge1.endName = fir.startName;
	edge1.tranSymbol = '#';

	//构建e2（连接起点和CD的起始点C）
	edge2.startName = startNode;
	edge2.endName  = sec.startName;
	edge2.tranSymbol = '#';

	//构建e3（连接AB的终点和终点）
	edge3.startName = fir.endName;
	edge3.endName = endNode;
	edge3.tranSymbol = '#';

	//构建e4（连接CD的终点和终点）
	edge4.startName = sec.endName;
	edge4.endName = endNode;
	edge4.tranSymbol = '#';

	//将fir和sec合并
	elem_copy(newElem, fir);
	elem_copy(newElem, sec);

	//新构建的4条边
	newElem.edgeSet[newElem.edgeCount++] = edge1;
	newElem.edgeSet[newElem.edgeCount++] = edge2;
	newElem.edgeSet[newElem.edgeCount++] = edge3;
	newElem.edgeSet[newElem.edgeCount++] = edge4;

	newElem.startName = startNode;
	newElem.endName = endNode;

	return newElem;
}


//处理 N(s)N(t)
elem act_join(elem fir, elem sec)
{
	//将fir的结束状态和sec的开始状态合并，将sec的边复制给fir，将fir返回
	//将sec中所有以StartState开头的边全部修改
	for (int i = 0; i < sec.edgeCount; i++) {
		if (sec.edgeSet[i].startName.nodeName.compare(sec.startName.nodeName) == 0)
		{
			sec.edgeSet[i].startName = fir.endName; //该边e1的开始状态就是N(t)的起始状态
		}
		else if (sec.edgeSet[i].endName.nodeName.compare(sec.startName.nodeName) == 0) {
			sec.edgeSet[i].endName = fir.endName; //该边e2的结束状态就是N(t)的起始状态
		}
	}
	sec.startName = fir.endName;

	elem_copy(fir, sec);

	//将fir的结束状态更新为sec的结束状态
	fir.endName = sec.endName;
	return fir;
}

elem act_star(elem Elem)
{
	elem newElem;
	newElem.edgeCount = 0;
	edge edge1, edge2, edge3, edge4;

	//获得新状态节点
	node startNode = new_node();
	node endNode = new_node();

	//e1
	edge1.startName = startNode;
	edge1.endName = endNode;
	edge1.tranSymbol = '#';	//闭包取空串

	//e2
	edge2.startName = Elem.endName;
	edge2.endName = Elem.startName;
	edge2.tranSymbol = '#';

	//e3
	edge3.startName = startNode;
	edge3.endName = Elem.startName;
	edge3.tranSymbol = '#';

	//e4
	edge4.startName = Elem.endName;
	edge4.endName = endNode;
	edge4.tranSymbol = '#';

	//构建单元
	elem_copy(newElem, Elem);

	//将新构建的四条边加入EdgeSet
	newElem.edgeSet[newElem.edgeCount++] = edge1;
	newElem.edgeSet[newElem.edgeCount++] = edge2;
	newElem.edgeSet[newElem.edgeCount++] = edge3;
	newElem.edgeSet[newElem.edgeCount++] = edge4;

	//构建NewElem的启示状态和结束状态
	newElem.startName = startNode;
	newElem.endName = endNode;

	return newElem;
}

int is_letter(char check) {
	if (check >= 'a' && check <= 'z' || check >= 'A' && check <= 'Z')
		return true;
	return false;
}
//添加连接符号
string add_join_symbol(string add_string)
{
	int length = add_string.size();
	int return_string_length = 0;
	char* return_string = new char[2 * length + 2];//最多是两倍
	char first, second;
	for (int i = 0; i < length - 1; i++)
	{
		first = add_string.at(i);
		second = add_string.at(i + 1);
		return_string[return_string_length++] = first;
		//要加的可能性如ab 、 *b 、 a( 、 )b 等情况
		//若第二个是字母、第一个不是'('、'|'都要添加
		if (first != '(' && first != '|' && is_letter(second))
		{
			return_string[return_string_length++] = '+';
		}
		//若第二个是'(',第一个不是'|'、'(',也要加
		else if (second == '(' && first != '|' && first != '(')
		{
			return_string[return_string_length++] = '+';
		}
	}
	//将最后一个字符写入second
	return_string[return_string_length++] = second;
	return_string[return_string_length] = '\0';
	string STRING(return_string);
	cout << "加'+'后的表达式：" << STRING << endl;
	return STRING;
}

//类里的各类元素定义
infixToPostfix::infixToPostfix(const string& infix_expression) : infix(infix_expression), postfix("") {
	isp = { {'+', 3}, {'|', 5}, {'*', 7},  {'(', 1}, {')', 8}, {'#', 0} };
	icp = { {'+', 2}, {'|', 4}, {'*', 6}, {'(', 8}, {')', 1}, {'#', 0} };
}

int infixToPostfix::is_letter(char check) {
	if (check >= 'a' && check <= 'z' || check >= 'A' && check <= 'Z')
		return true;
	return false;
}

int infixToPostfix::ispFunc(char c) {
	int priority = isp.count(c) ? isp[c] : -1;
	if (priority == -1) {
		cerr << "error: 出现未知符号！" << endl;
		exit(1);  // 异常退出
	}
	return priority;
}

int infixToPostfix::icpFunc(char c) {
	int priority = icp.count(c) ? icp[c] : -1;
	if (priority == -1) {
		cerr << "error: 出现未知符号！" << endl;
		exit(1);  // 异常退出
	}
	return priority;
}

void infixToPostfix::inToPost() {
	string infixWithHash = infix + "#";
	stack<char> stack;
	int loc = 0;
	while (!stack.empty() || loc < infixWithHash.size()) {
		if (is_letter(infixWithHash[loc])) {
			postfix += infixWithHash[loc];
			loc++;
		}
		else {
			char c1 = (stack.empty()) ? '#' : stack.top();
			char c2 = infixWithHash[loc];
			if (ispFunc(c1) < icpFunc(c2)) { // 栈顶操作符优先级低于当前字符，将当前字符入栈
				stack.push(c2);
				loc++;
			}
			else if (ispFunc(c1) > icpFunc(c2)) {  // 栈顶操作符优先级高于当前字符，将栈顶操作符出栈并添加到后缀表达式
				postfix += c1;
				stack.pop();
			}
			else {
				if (c1 == '#' && c2 == '#') { // 遇到两个 #，表达式结束
					break;
				}
				stack.pop(); //其中右括号遇到左括号时会抵消，左括号出栈，右括号不入栈
				loc++;
			}
		}
	}
}

string infixToPostfix::getResult() {
	postfix = ""; // 清空结果
	inToPost();
	return postfix;
}

/**表达式转NFA处理函数,返回最终的NFA集合
*/
elem express_to_NFA(string expression)
{
	int length = expression.size();
	char element;
	elem Elem, fir, sec;
	stack<elem> STACK;
	for (int i = 0; i < length; i++)
	{
		element = expression.at(i);
		switch (element)
		{
		case '|':
			sec = STACK.top();
			STACK.pop();
			fir = STACK.top();
			STACK.pop();
			Elem = act_Unit(fir, sec);
			STACK.push(Elem);
			break;
		case '*':
			fir = STACK.top();
			STACK.pop();
			Elem = act_star(fir);
			STACK.push(Elem);
			break;
		case '+':
			sec = STACK.top();
			STACK.pop();
			fir = STACK.top();
			STACK.pop();
			Elem = act_join(fir, sec);
			STACK.push(Elem);
			break;
		default:
			Elem = act_Elem(element);
			STACK.push(Elem);
		}
	}
	cout << "已将正则表达式转换为NFA!" << endl;
	Elem = STACK.top();
	STACK.pop();

	return Elem;
}

//打印NFA
void Display(elem Elem) {
	cout << "NFA States:" << endl;
	cout << "Start State: " << Elem.startName.nodeName << endl;
	cout << "End State: " << Elem.endName.nodeName << endl;

	cout << "NFA Transitions:" << endl;
	for (int i = 0; i < Elem.edgeCount; i++) {
		cout << "Edge " << i + 1 << ": ";
		cout << Elem.edgeSet[i].startName.nodeName << " --(" << Elem.edgeSet[i].tranSymbol << ")--> ";
		cout << Elem.edgeSet[i].endName.nodeName << endl;
	}

	cout << "End" << endl;
}

//生成NFAdot文件
void generateDotFile_NFA(const elem& nfa) {
	std::ofstream dotFile("nfa_graph.dot");

	if (dotFile.is_open()) {
		dotFile << "digraph NFA {\n";
		dotFile << "  rankdir=LR;  // 横向布局\n\n";
		dotFile << " node [shape = circle];   // 状态节点\n\n";

		dotFile << nfa.endName.nodeName << " [shape=doublecircle];\n";
		// 添加 NFA 状态
		dotFile << "  " << nfa.startName.nodeName << " [label=\"Start State: " << nfa.startName.nodeName << "\"];\n";
		dotFile << "  " << nfa.endName.nodeName << " [label=\"End State: " << nfa.endName.nodeName << "\"];\n";

		// 添加 NFA 转移
		for (int i = 0; i < nfa.edgeCount; i++) {
			const edge& currentEdge = nfa.edgeSet[i];
			dotFile << "  " << currentEdge.startName.nodeName << " -> " << currentEdge.endName.nodeName << " [label=\"" << currentEdge.tranSymbol << "\"];\n";
		}

		dotFile << "}\n";

		dotFile.close();
		std::cout << "NFA DOT file generated successfully.\n";
	}
	else {
		std::cerr << "Unable to open NFA DOT file.\n";
	}
}

//main
#include "head.h" // 包含提供的头文件

int main() {
    string Regular_Expression;
    elem NFA_Elem;
    input(Regular_Expression);
    if (Regular_Expression.length() > 1)    Regular_Expression = add_join_symbol(Regular_Expression);
    infixToPostfix Solution(Regular_Expression);
    //中缀转后缀
    cout << "后缀表达式为：";
    Regular_Expression = Solution.getResult();
    cout << Regular_Expression << endl;
    //表达式转NFA
    NFA_Elem = express_to_NFA(Regular_Expression);
    //显示
    Display(NFA_Elem);
    //生成NFAdot文件
    generateDotFile_NFA(NFA_Elem);

    // 初始化 DFA 状态集合和转换关系
    vector<DFAState> dfaStates; //用于存储所有的DFA状态
    vector<DFATransition> dfaTransitions; //用于存储DFA状态之间的转移
    set<string> nfaInitialStateSet;   //存储NFA的初始状态
    nfaInitialStateSet.insert(NFA_Elem.startName.nodeName); 
    DFAState dfaInitialState = eClosure(nfaInitialStateSet,NFA_Elem);//计算NFA初始状态的ε闭包
    dfaStates.push_back(dfaInitialState);

    // 开始构建 DFA
    for (int i = 0; i < dfaStates.size(); i++)   {
        DFAState dfaState = dfaStates[i];
        for (int j = 0; j <NFA_Elem.edgeCount; j++) {
            char symbol = NFA_Elem.edgeSet[j].tranSymbol;
            DFAState nextState = move(dfaState, symbol,NFA_Elem);
            DFAState dfaNextState = eClosure(nextState.nfaStates, NFA_Elem);

            if (!nextState.nfaStates.empty()) {
                if (!isDFAStateInVector(dfaStates, dfaNextState)) {
                    dfaStates.push_back(dfaNextState);
                }
                //对于边也要去重，因为等于a的边可能会遍历到两次
                if (!isTransitionInVector(dfaState, dfaNextState, symbol, dfaTransitions)) {
                    dfaTransitions.push_back({ dfaState,dfaNextState, symbol });
                }
            }
        }
    }
    // 显示 DFA
    displayDFA(dfaStates, dfaTransitions);

    //生成DFAdot文件
    generateDotFile_DFA(dfaStates,dfaTransitions);
    return 0;
}

到了这里，关于编译原理：正则表达式/正规式转NFA（原理+完整代码+可视化实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • Python Lambda表达式的底层原理详解：编译、执行与优化机制

    Python Lambda表达式的底层原理详解：编译、执行与优化机制

    昨天面试被问到了lambda表达式的底层是怎么实现的，我直接脑子就空白了，因为平时只关注lambda的应用方式 在Python中，无论是普通函数还是Lambda函数，都会经过编译转换成字节码，解释器再执行这些字节码。 1.1 示例代码 通过 dis 模块，可以查看Lambda函数的字节码。这些字节

    2024年04月28日
    浏览(43)

  • 【正则表达式】正则表达式常见匹配模式

    模式 描述 w 匹配字母数字及下划线 W 匹配非字母数字下划线 s 匹配任意空白字符，等价于 [tnrf]. S 匹配任意非空字符 d 匹配任意数字，等价于 [0-9] D 匹配任意非数字 A 匹配字符串开始 Z 匹配字符串结束，如果是存在换行，只匹配到换行前的结束字符串 z 匹配字符串结

    2024年02月09日
    浏览(81)

  • 【SQL-正则】利用正则表达式进行过滤操作（常用正则表达式）

    1、由数字、26个英文字母或者下划线组成的字符串 2、非负整数（正整数 + 0 ） 3、正整数 4、非正整数（负整数 + 0） 5、负整数 6、整数 7、非负浮点数（正浮点数 + 0） 8、正浮点数 9、非正浮点数（负浮点数 + 0） 10、负浮点数 11、浮点数 12、由26个英文字母组成的字符串 13、

    2024年02月12日
    浏览(81)

  • Python正则表达式之学习正则表达式三步曲

            正则表达式描述了一种字符串匹配的模式，可以用来检查一个串的有无某子串，或者做子串匹配替换，取出子串等操作。也可以说正则表达式就是字符串的匹配规则，也可以理解为是一种模糊匹配，匹配满足正则条件的字符串。         1、数据验证（eg:表单验

    2024年02月15日
    浏览(66)
  • Java 之正则表达式语法及常用正则表达式汇总

    Java 之正则表达式语法及常用正则表达式汇总

    正则表达式，又称规则表达式。（英语：Regular Expression，在代码中常简写为 regex、regexp 或 RE），计算机科学的一个概念。正则表达式通常被用来检索、替换那些符合某个模式（规则）的文本。 正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称

    2024年02月09日
    浏览(71)

  • 老夫的正则表达式大成了，桀桀桀桀！！！【Python 正则表达式笔记】

    特殊字符 .^$?+*{}[]()| 为特殊字符，若想要使用字面值，必须使用 进行转义 字符类 [] [] 匹配包含在方括号中的任何字符。它也可以指定范围，例： [a-zA-Z0-9] 表示a到z，A到Z，0到9之间的任何一个字符 [u4e00-u9fa5] 匹配 Unicode 中文 [^x00-xff] 匹配双字节字符（包括中文） 在 [] 中

    2024年02月04日
    浏览(60)
  • 机器学习与数据科学-专题1 Python正则表达式-【正则表达式入门-1】

    机器学习与数据科学-专题1 Python正则表达式-【正则表达式入门-1】

    为了完成本关任务，你需要掌握： 在 Python 中使用正则表达式； 最基础正则表达式； 正则匹配函数。 在 Python 中使用正则表达式 正可谓人生苦短，我用 Python。Python 有个特点就是库非常多，自然拥有正则匹配这种常见的库，并且此库已经嵌入在 Python 标准库中，使用起来非常

    2024年01月22日
    浏览(64)

  • 正则表达式 (用于灵活匹配文本的表达式)

    目录 . * 用于匹配任意单个字符，除了换行符。 例如使用正则表达式 a.b, 它可以匹配aab、acb、a#b 用于匹配前一个字符零次或多次。 例如，使用正则表达式 ab*c ，它可以匹配 \\\"ac\\\"、\\\"abc\\\"、\\\"abbc\\\"，因为 b* 表示匹配零个或多个字符 \\\"b\\\"。所以，这个表达式可以匹配 \\\"ac\\\"（零个 \\\"b\\\"），

    2024年01月16日
    浏览(64)

  • 利用正则表达式进行爬取数据以及正则表达式的一些使用方法

    Pattern：表示正则表达式 Matcher：文本匹配器，作用按照正则表达式的规则去读取字符串，从头开始读取。 在大串中去找符合匹配规则的子串。 代码示例： 需求： 把连接:https://m.sengzan.com/jiaoyu/29104.html?ivk sa=1025883i中所有的身份证号码都爬取出来。 代码示例： 需求： 把下面文

    2024年02月09日
    浏览(66)

  • 正则表达式、常用的正则

    正则表达式（Regular Expression，简称为Regex或RegExp）是用于匹配和搜索文本模式的工具。它是一个强大且灵活的字符串处理工具，可以用来检查一个字符串是否符合特定的模式，或者从一个文本中提取满足条件的部分。 在正则表达式中，可以使用不同的元字符和特殊符号来定义

    2024年02月14日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包