【形式语言与自动机】正则表达式到 ε-NFA 的转化

课本上只会讲给你算法，而这个小实验本身也挺有意思，所以就想要把具体实现的过程和代码记录下来。

正则表达式转换为最小化 DFA 简单来讲可以分为三个步骤

1. 由原始正则表达式转化为 ε-NFA
2. 由 ε-NFA 转化为 DFA
3. 由 DFA 转化最小化 DFA

下面我们一步一步来。

1.Tompson 构造法

正则表达式的形式非常简单，总共只涉及并运算、串联运算和闭包运算三种运算。这三种运算都很容易由 ε-NFA 表示出来，于是汤普森设计了一套规则用来机械地将正则表达式转化为 ε-NFA。形式规范的 ε-NFA 也为后续的化简处理提供了便利。

这些规则中有两条基本规则：

1. 表达式 ε

2. 表达式 a

   

然后是归纳部分，所有正则表达式中的终极符号构成一个表达式a，然后根据运算符号对应的归纳部分规则合并在一起。

1. 并联

   

2. 串联

   

3. 闭包

   

可以来看一个简单的例子来感受合并的过程

a|(ab*)

第一个 a :

第二个 a :

第一个 b :

此时可以想象成构造栈里压入三个元素，每个元素代表了这个表达式的起始状态和终止状态。每次构造出新的式子就将新式子的起始和终止状态作为一个新元素压入构造栈，最后栈中只剩下一个元素时，就是最终结果的起始和终止状态。这是之后具体代码的基础。当然到时候的构造顺序会有所不同，毕竟现在是我们凭空想象的，计算机处理的时候使用的是后缀表达式。但只要递归关系写对了顺序并无所谓。

对于 b* :

对于 ab* :

最后 a|(ab*) :

那么我们的构造就完成了，一个形式标准易于计算机后续处理的 ε-NFA 。

图里漏了一些 ε ，问题不大。

---

接下来就进行具体的代码书写

在这之前呢要先对输入的正则表达式进行一些处理，首先添加连接运算符。原先的正则表达式连接运算是直接将两个式子连在一起，没有运算符的话代码不太好写。需要添加的地方有形如 ab、a(、)(、*( 等等好几种情况，这个这个想想就行了。遍历一遍表达式在相应位置中间添加一个 “.”, 或者 “&” 都可以，按个人喜好。

另外就是中缀转后缀，这个我就不多说了，也可以自行百度。

拿到了我们处理完成的后缀正则表达式之后，着手下一步。

用一个 vector 存储图：

vector<vector<pair<int, char>>>* NFA_map = new vector<vector<pair<int, char>>>()

vector 是有顺序的，这里将 vector 中元素下标作为一个状态的标记。一个状态也以一个 vector 存储，其元素类型为 pair<int, char>, 表示通过某 (char) 可以转移到某状态 (int)。也就是一条边。

之后用一个整形存储状态数量，然后用一个状态栈来实现我们在上边想象的操作

int stateNum = 0;
stack<pair<int, int>>* st = new stack<pair<int, int>>();

然后我们遍历后缀表达式，分别对这些情况写代码

基础规则需要新建开始和结束状态，并从添加一条从开始状态到结束状态的边，转移条件是什么不用多说了吧

int state_begin = stateNum++;  // 新增的开始状态(仅仅对于这个表达式来说的开始状态)
NFA_map->push_back(vector<pair<int, char>>());  // 与stateNum同步push一个元素，即第一个状态
int state_end = stateNum++;
NFA_map->push_back(vector<pair<int, char>>());
st->push(make_pair(state_begin, state_end));  // 将第一个基础表达式的起始与结束状态 makepair 后塞进栈
NFA_map->at(state_begin).push_back(make_pair(state_end, tc)); 添加边

连接运算 “.”

连接运算的对象是两个子表达式，根据后缀表达式的特点我们毫无顾虑地从状态栈中弹出最上边两个元素，它们肯定是这个运算符的作用对象。并且是由下边的状态连接到栈顶状态。

pair<int, int> t_NFAy = st->top(); // 栈顶
st->pop();
pair<int, int> t_NFAx = st->top(); // 第二个
st->pop();

// 此时不用为两个部分构造新的状态，只需把两个状态中间部分相连, '$' 代表ε
NFA_map->at(t_NFAx.second).push_back(make_pair(t_NFAy.first, '$'));
// 然后整体的新部分的开始和结束作为下一个入栈的状态元素
st->push(pair<int, int>(t_NFAx.first, t_NFAy.second));

闭包运算 “*”

闭包运算的作用对象是一个子表达式，弹出栈顶元素。

// 闭包运算，根据后缀表达式的特点，状态栈中上一个元素
// 其开始状态与结束状态之间的 N(x) 对应的正则表达式
// 即是需要进行构造的部分。
pair<int, int> t_NFA = st->top();
st->pop();
// 新建这个新的构造出来的 NFA 部分  的开始结束状态
int state_begin = stateNum++;
NFA_map->push_back(vector<pair<int, char>>());
int state_end = stateNum++;
NFA_map->push_back(vector<pair<int, char>>());
// 同样压入状态栈
st->push(pair<int, int>(state_begin, state_end));
// 添加边，看一看上边的图就能体会到是怎么加的了，很简单
NFA_map->at(state_begin).push_back(make_pair(t_NFA.first, '$'));
NFA_map->at(state_begin).push_back(make_pair(state_end, '$'));
NFA_map->at(t_NFA.second).push_back(make_pair(state_end, '$'));
NFA_map->at(t_NFA.second).push_back(make_pair(t_NFA.first, '$'));

并运算 “|”

并运算的作用对象也是两个元素，并且这回需要新建状态。

// 现在应该很显然了
pair<int, int> t_NFAy = st->top();
st->pop();
pair<int, int> t_NFAx = st->top();
st->pop();

int state_begin = stateNum++;
NFA_map->push_back(vector<pair<int, char>>());
int state_end = stateNum++;
NFA_map->push_back(vector<pair<int, char>>());

NFA_map->at(state_begin).push_back(make_pair(t_NFAx.first, '$'));
NFA_map->at(state_begin).push_back(make_pair(t_NFAy.first, '$'));
NFA_map->at(t_NFAx.second).push_back(make_pair(state_end, '$'));
NFA_map->at(t_NFAy.second).push_back(make_pair(state_end, '$'));
st->push(pair<int, int>(state_begin, state_end));

那么我们在正则表达式转换为 ε-NFA 这步的所有工作就做完了，下面贴上完整代码作为参考

#include <algorithm>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <stack>

using namespace std;
map<char, int> form;

void init_form()
{
	form.insert(pair<char, int>('(', 0));
	form.insert(pair<char, int>(')', 0));
	form.insert(pair<char, int>('*', 3));
	form.insert(pair<char, int>('.', 2));
	form.insert(pair<char, int>('+', 1));
}

bool isleagal(char op)
{
	if (op == '(' || op == ')' ||
		op == '.' || op == '*' || op == '+') {

		return true;
	}

	return false;
}

bool myIsSupper(char c)
{
	return ('0' <= c && c <= '1');
}

string init_expre(string expre)
{
	string res = "";
	char last_char = '$';
	for (int i = 0; i < expre.length(); i++) {
		if (0 == i) {
			last_char = expre[i];
			res += expre[i];
		}
		else {
			if (myIsSupper(last_char)) {
				if (myIsSupper(expre[i]) || expre[i] == '(') {
					res += '.';
				}
			}
			else if (last_char == ')') {
				if (myIsSupper(expre[i]) || '(' == expre[i]) {
					res += '.';
				}
			}
			else if (last_char == '*') {
				if (myIsSupper(expre[i]) || expre[i] == '(') {
					res += '.';
				}
			}
			last_char = expre[i];
			res += expre[i];
		}
	}
	return res;
}

queue<char>* infix_to_postfix(string expre)
{
	init_form();
	queue<char>* postfix = new queue<char>();
	stack<char>* op = new stack<char>();

	for (int i = 0; i < expre.length(); i++) {
		if ('0' <= expre[i] && expre[i] <= '1') {
			postfix->push(expre[i]);
		}
		else {
			// 字母直接入队
			if (!isleagal(expre[i])) {
				return nullptr;
			}
			else {
				if (expre[i] == '(') {
					op->push(expre[i]);
				}
				else if (expre[i] == ')') {
					// 右括号则运算符栈出栈，直到遇到左括号
					while (!op->empty() && op->top() != '(') {
						postfix->push(op->top());
						op->pop();

					}
					// 如果没有遇到左括号，表达式不合法
					if (op->empty()) {
						return nullptr;
					}
					op->pop();
				}
				else if (op->empty() || form[expre[i]] > form[op->top()]) {
					// 空栈或者优先级大于栈顶运算符则入栈
					op->push(expre[i]);
				}
				else {
					// 否则依次出栈直到遇到低于自己优先级的
					char tp = op->top();
					while (!op->empty() && form[expre[i]] <= form[tp]) {
						postfix->push(tp);
						op->pop();
						if (!op->empty()) {
							tp = op->top();
						}
					}
					op->push(expre[i]);
				}
			}
		}
	}
	// 剩余运算符依次出栈
	while (!op->empty()) {
		postfix->push(op->top());
		op->pop();
	}

	return postfix;
}

vector<vector<pair<int, char>>>* make_e_NFA(string expre, pair<int, int>& begin_end, int& maxStates)
{
	// 空字符用 $ 表示
	vector<vector<pair<int, char>>>* NFA_map = new vector<vector<pair<int, char>>>();

	// 用来存储状态数量
	int stateNum = 0;
	// 状态栈 用来存储一次构造之后的 N(x) 的起始和中止状态
	stack<pair<int, int>>* st = new stack<pair<int, int>>();


	expre = init_expre(expre);
	queue<char>* postfix = infix_to_postfix(expre);

	while (!postfix->empty()) {
		char tc = postfix->front();
		postfix->pop();
         // 用你自己的字母表 
		if ('0' <= tc && tc <= '1') {
			// 一个字母，新建其开始状态和结束状态
			int state_begin = stateNum++;
			NFA_map->push_back(vector<pair<int, char>>());
			int state_end = stateNum++;
			NFA_map->push_back(vector<pair<int, char>>());
			// 压入状态栈
			st->push(pair<int, int>(state_begin, state_end));
			// 用本字符连接开始状态和结束状态
			NFA_map->at(state_begin).push_back(make_pair(state_end, tc));
		}
		else {
			if (tc == '*') {
				// 闭包运算，根据后缀表达式的特点，状态栈中上一个元素
				// 其开始状态与结束状态之间的 N(x) 对应的正则表达式
				// 即是需要进行构造的部分。
				pair<int, int> t_NFA = st->top();
				st->pop();
				// 新建这个新的构造出来的 NFA 部分  的开始结束状态
				int state_begin = stateNum++;
				NFA_map->push_back(vector<pair<int, char>>());
				int state_end = stateNum++;
				NFA_map->push_back(vector<pair<int, char>>());
				// 同样压入状态栈
				st->push(pair<int, int>(state_begin, state_end));
				NFA_map->at(state_begin).push_back(make_pair(t_NFA.first, '$'));
				NFA_map->at(state_begin).push_back(make_pair(state_end, '$'));
				NFA_map->at(t_NFA.second).push_back(make_pair(state_end, '$'));
				NFA_map->at(t_NFA.second).push_back(make_pair(t_NFA.first, '$'));
			}
			else if (tc == '.') {
				// 连接运算，作用对象是两个操作数
				// 也就是状态栈中的最上两个元素，即待连接的 N(x) 与 N(y)
				pair<int, int> t_NFAy = st->top();
				st->pop();
				pair<int, int> t_NFAx = st->top();
				st->pop();

				// 此时不用为两个部分构造新的状态，只需把两个状态中间部分相连
				// 然后整体的新部分的开始和结束作为下一个入栈的状态元素
				NFA_map->at(t_NFAx.second).push_back(make_pair(t_NFAy.first, '$'));
				st->push(pair<int, int>(t_NFAx.first, t_NFAy.second));
			}
			else {
				// 最后是并运算，也是双目运算符
				pair<int, int> t_NFAy = st->top();
				st->pop();
				pair<int, int> t_NFAx = st->top();
				st->pop();

				// 此时需要为两个部分新建共同的起始状态与终结状态
				int state_begin = stateNum++;
				NFA_map->push_back(vector<pair<int, char>>());
				int state_end = stateNum++;
				NFA_map->push_back(vector<pair<int, char>>());

				NFA_map->at(state_begin).push_back(make_pair(t_NFAx.first, '$'));
				NFA_map->at(state_begin).push_back(make_pair(t_NFAy.first, '$'));
				NFA_map->at(t_NFAx.second).push_back(make_pair(state_end, '$'));
				NFA_map->at(t_NFAy.second).push_back(make_pair(state_end, '$'));
				st->push(pair<int, int>(state_begin, state_end));
			}
		}
		// 注意，正则表达式接收完毕后，状态栈中仅存的一个元素即是 带空转移的NFA 的开始与结束状态
	}
	maxStates = stateNum;
	begin_end = st->top();
	return NFA_map;
}

然后就要开始我们的子集构造法了

2. 子集构造法

(未完待续…)