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

2023-12-05 01:12
文章标签 分析 代码 编译 实现 可视化 原理 正则表达式 完整 正规 词法 nfa

本文主要是介绍编译原理词法分析：正则表达式/正规式转NFA（原理+完整代码+可视化实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

文章目录

  • 从正则到自动机：正则表达式/正规式转换为NFA
    • 一、从中缀表达式转换为后缀表达式
    • 二、从后缀表达式转换为NFA
      • （A）本文用到的结构体
      • （B）一些准备工作（后续需要用到的函数）
      • （C）Thompson构造法（一些运算关系）
      • （D）将正则表达式转换为NFA
    • 三、生成dot文件
    • 四、案例测试
    • 五、C++代码完整实现

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

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

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

//类里的各类元素定义
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++] = '+';}}//将最后一个字符写入secondreturn_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可以直接由下列规则给出：
    空表达式ε直接转化为：
    在这里插入图片描述

    字母表中的单个符号a直接转化为：
    在这里插入图片描述

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

  1. 并运算 (s|t):

    • 通过 ε 转移，状态 q 可以直接到达 N(s) 或 N(t) 的初态。
    • N(s) 或 N(t) 原来的终态可以通过 ε 转移直接到达整个 NFA 的新终态。
      在这里插入图片描述

  2. 连接运算 (st):

    • N(s) 的初态成为新的 NFA 的初态。
    • 原来 N(s) 的终态成为 N(t) 的初态。
    • 原来 N(t) 的终态成为新的 NFA 的终态。
      在这里插入图片描述

  3. Kleene闭包 (s):

    • 将新表达式的初态和终态以及夹在中间的子表达式的 NFA N(s) 连接起来的 ε 转移，使得可以选择经过或者不经过子表达式。
    • 从 N(s) 的终态到初态的 ε 转移，使得 s 可以重复任意多次。
      在这里插入图片描述

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

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

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

（a）处理单个字符（规则1）
在这里插入图片描述
上图为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）
在这里插入图片描述
上图为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）

(a|b)(c|d)
上图为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）
在这里插入图片描述
上图为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();//e1edge1.startName = startNode;edge1.endName = endNode;edge1.tranSymbol = '#';	//闭包取空串//e2edge2.startName = Elem.endName;edge2.endName = Elem.startName;edge2.tranSymbol = '#';//e3edge3.startName = startNode;edge3.endName = Elem.startName;edge3.tranSymbol = '#';//e4edge4.startName = Elem.endName;edge4.endName = endNode;edge4.tranSymbol = '#';//构建单元elem_copy(newElem, Elem);//将新构建的四条边加入EdgeSetnewElem.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)*
    在这里插入图片描述

在这里插入图片描述
上面为在命令提示符中到指定目录下（你dot文件所在的目录下）输入指令将dot文件生成图片，然后打开visual studio目录，找到nfa.png：
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

  1. a(b|c)*de
    在这里插入图片描述
    在这里插入图片描述

五、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();//e1edge1.startName = startNode;edge1.endName = endNode;edge1.tranSymbol = '#';	//闭包取空串//e2edge2.startName = Elem.endName;edge2.endName = Elem.startName;edge2.tranSymbol = '#';//e3edge3.startName = startNode;edge3.endName = Elem.startName;edge3.tranSymbol = '#';//e4edge4.startName = Elem.endName;edge4.endName = endNode;edge4.tranSymbol = '#';//构建单元elem_copy(newElem, Elem);//将新构建的四条边加入EdgeSetnewElem.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++] = '+';}}//将最后一个字符写入secondreturn_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;//表达式转NFANFA_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);// 开始构建 DFAfor (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 });}}}}// 显示 DFAdisplayDFA(dfaStates, dfaTransitions);//生成DFAdot文件generateDotFile_DFA(dfaStates,dfaTransitions);return 0;
}

这篇关于编译原理词法分析：正则表达式/正规式转NFA（原理+完整代码+可视化实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/455593。

相关文章

大模型研发全揭秘：客服工单数据标注的完整攻略

大模型研发全揭秘：客服工单数据标注的完整攻略

在人工智能（AI）领域，数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者，掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中，工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注，不仅能够帮助提升客服自动化系统的智能化水平，还能优化客户服务流程，提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
hdu4407(容斥原理)

hdu4407(容斥原理)

题意：给一串数字1,2，......n，两个操作:1、修改第k个数字，2、查询区间[l,r]中与n互质的数之和。 解题思路：咱一看，像线段树，但是如果用线段树做，那么每个区间一定要记录所有的素因子，这样会超内存。然后我就做不来了。后来看了题解，原来是用容斥原理来做的。还记得这道题目吗？求区间[1,r]中与p互质的数的个数，如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2