正则语言是一种可以由正则表达式定义的形式语言，也可以被定义为由有限自动机识别的一种语言。而正则表达式，是一种文本模式， 通常被用来检索、替换那些符合某个模式（规则）的文本。在我们实际编程应用的时候，正则表达式的识别与分析是绕不过的一个问题。 许多语言都提供了分析正则表达式的引擎，并且提供了很多传统正则表达式以外的功能支持。本项目探寻了通过正则表达式生成NFA与DFA的算法， 并使用C++作为编程语言实现了正则表达式的构造、NFA生成与推理、NFA向DFA的转化和DFA的推理。在实现过程中加深了对于正则表达式与NFA 、DFA的理解，深入研究了实现细节，通过自己动手造轮子的方式实现了类似正则表达式引擎的功能。
在理论计算机科学和形式语言理论中，正则语言（也称为理性语言）是一种可以由正则表达式定义的形式语言。另外，正则语言也可以被定义为由有限自动机识别的 一种语言。正则表达式，又称规则表达式,（Regular Expression），是一种文本模式，包括普通字符和特殊字符（称为"元字符"），是计算机科学的一个概念。 正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串，通常被用来检索、替换那些符合某个模式（规则）的文本。
在我们实际编程应用的时候，正则表达式的识别与分析是绕不过的一个问题。许多语言都提供了分析正则表达式的引擎，并且提供了很多传统正则表达式以外的功能 支持。
我研究的主要问题是，如何通过给定的正则表达式构造出对应的有穷状态自动机，并使用构造出的有穷状态自动机完成输入串的识别与分析。宿主语言我使用的是 C++，采用面向对象的思想完成正则语言的分析与有穷状态自动机的生成以及最终的推理。
系统整体的设计思路是，首先通过给定的正则表达式进行语法分析与语法检查，然后构造语法树，最后根据构造出的语法树构造有穷状态自动机。并且有穷状态自动 机从NFA开始，再向DFA转换，最终输出的结果是转换完成的DFA。
在开始之前，我们需要完成一些约定。首先系统可供使用的字母表定义为ASCII码字符表，即对应0~127号字符。空符号定义为0号字符。并且系统提供针对任意数 字、任意小写字母、任意大写字母、任意字母的通配符。
系统的第一步要接受给定的正则语言来构造语法树。为了简便起见，我选择省略解析字符串的部分，集中精力来实现通过解析完成的字符串来构造语法树的部分。因 此我们不妨假定字符串解析已经完成，我们已经将字符与符号转化成了编程语言中的变量与结构体。同时我也省去了处理括号与运算顺序的繁琐，而直接借用了编程 语言中对于运算符顺序的处理。最终我们需要做的就是实现各个正则语言表达式中不同算符的处理，并且将算符正确的转化为语法树的节点。
算符的转化思路上大同小异，对于与和或，我们直接构造一个新的节点，并将子节点分别设为参与运算的两个字串。对于正闭包，我们在构造语法树时先不做处理， 只是标记闭包算符并且将闭包算符作用的子串设为子结点。而克林闭包算符可以通过正闭包并上空符号生成。
最后，我们在重载后的运算符函数中按照上述方式完成新节点的生成，并将新节点返回，就可以实现语法树的构建。
接下来我们需要将语法树转化为NFA。实际上总体的转化思想就是分治递归。首先从语法树的根节点开始，我们认为可以将根节点看作一个抽象状态，那么NFA的节 点图就是从起始状态接受这个抽象的状态通向结束状态。实际上这个抽象的状态我个人认为用英文中的meta来称呼比较合适，即它是一个复合状态，表示的不是一 个单一的字符或者串，而是串的集合。此时的NFA从起始状态接受这个串的集合可以到达终止状态。而我们接下来就是要不断的拆解这个串的集合，把抽象的集合拆 解成具体的字符，那么NFA就狗仔完成了。拆解的过程就是对应于我们前面建立语法树的过程，从根节点开始，不断向下寻找子结点，即不断拆解串的集合，将抽 象串具体化的过程。
而具体的拆解过程又分为以下几种情况：
-
对于单个字符构成的表达式，它只有起始状态和接受状态，其中起始状态到接受状态之间有一条标为该字符的路径。
-
对于正则表达式c->a|b，c的起始状态有两条标记为ε（空字符）的路径分别通向a和b，而a、b的接受状态则分别有一条标记为ε的路径通向c的接受状态。
-
对于正则表达式c->a+b，c的起始状态即a的起始状态，c的接受状态即b的接受状态。同时a的接受状态到b的起始状态之间有一条标记为ε的路径。
-
对于正则表达式b->+(a)，b的起始状态到a的起始状态、a的接受状态到b的接受状态之间各有一条标记为ε的路径，同时a的接受状态到b的起始状态之间也有一
-
条标记为ε的路径。
最后我们要完成从NFA向DFA的转换。从NFA构造DFA，本质上是对任意可接收输入后所有可能的NFA的状态的穷举。所以DFA的起始状态是空输入后的NFA状态集合 S = e-closure(A)。DFA的一个状态X接受输入a后的状态X' = U e-closure(s)，其中s 属于X含有的NFA状态接受输入a后到达的NFA状态集合。按照以上思 路，我们可以构造出一个DFA。
但是需要注意的是，对于只有空输入的NFA结点，他们没有必要出现在DFA中。首先，相邻的只含有空输入的结点，可以合并成一个结点。他们的e-closure完全 相同。所以他们在DFA里的价值一样。因为同样输入可以达到相同的e-closure。其次，他们在DFA的状态中对可接受的输入没有影响。只有非空的NFA结点，可以 选择输入。一个DFA状态，只受它包含的NFA非空输入状态的影响。
所以整体思路是，我们首先要确定在NFA中都有哪些转移条件（即所有可能可以接受的字符），然后从NFA的开始状态开始，将开始状态的e-closure求出作为DFA 的开始状态，然后对于每一个转移条件，求出开始状态中每一个原NFA状态的对应下一个状态的e-closure。这些状态的并就是下一个DFA状态。
用一个简单的例子说明。假设开始状态包括q0、q1，可能的接受的字符为0、1，那么q0接受0后的状态为q2，q2的e-closure为q2、q3，q1接受0后的状态为 q3，q3的e-closure为q3、q4，那么DFA的开始状态即{q0, q1}接受0后的下一个状态就是{q2, q3, q4}。同理，我们可以递归的求出来整个DFA所有状态。 需要注意的是对于包含同样NFA状态的新DFA状态要和原有状态进行合并，否则会出现两个一模一样的DFA状态。为了实现这一点，在转换前我们还需要为所有的NFA 状态标号，这样才能在后续的转换过程中区分不同的NFA状态。该过程可以与遍历NFA统计字符表的过程合并。
同时我们还要注意当NFA生成DFA后，可能会有DFA状态出度不完全，需要手动增加陷阱状态。
最后 我们还需要完成DFA的推理。事实上DFA的推理应该是整个工程中最简单的部分，我们在约定好DFA的数据结构以后只需要解析输入的串，按照DFA状态转移图 完成状态转移即可。当串的输入结束时若DFA位于终止状态则接受这个串，否则不接受。
该项目起源于大学形式语言课程的结课作业，我选定的题目是正则表达式的解析与有穷自动机的生成， 该项目中部分代码参考于网络上博客中的实现。由于个人能力有限，该项目中还有很多问题， 包括NFA的生成会占用大量内存空间，尤其是对于字母表庞大且逻辑复杂的正则表达式来说。如有 错误或bug，欢迎PR以及Issue。