正则表达式引擎的实现

我照着《engineering a compiler》中词法分析部分的内容做了一个正则表达式引擎，仅支持实现基本的连接，并联，闭包操作，和单字母字符集。

按照书中的内容，我选择的做法是先把正则表达式用Thompson构造法解析成ε-NFA，然后再用子集构造法转换为DFA，再用Brzozowski 算法最小化DFA。

1.Thompson构造法

 

 

这一步骤是用于将正则表达式解析成ε-NFA，具体实现上我用了两个栈，字符栈和符号栈，然后优先级设置为括号>闭包>连接>并联。然后根据thompson构造法的构造方法去连接状态节点。就能得到初步的带ε的非确定性有限自动机。

2.子集构造法

子集构造法的作用是将我们刚刚得到的ε-NFA转换为确定性的DFA。

这个过程要怎么实现呢？

这个转换过程的目的是去掉状态图中不确定状态转移边ε，要怎么去掉呢？这个问题有一点复杂，我们慢慢分析。

首先先看非确定性有限自动机的定义

有穷自动机是一个5元组（Q，Σ，δ，q0，F），其中

1）Q是一个有限集合，叫做状态集。

2）Σ是一个有限集合，叫做字母表。

3）δ：Q×Σ→Q是转移函数。

4）q0∈Q是起始状态。

5）F⊆Q是接受状态集。

 从上述的定义中我们可以看出自动机的状态节点是用集合的概念来描述的，状态节点的总和被定义为Q，是一个有限集合。

然后这个有限集合通过一个转移函数δ：Q×Σ→Q，会转换成另一个有限集合。

子集构造法是把根据一个状态通过一个字母表元素能到达的所有状态的集合，作为新的状态图的一个状态节点。遍历一遍NFA状态图能得到新的DFA状态图。

 

3.Brzozowski 算法

Brzozowski 算法用于最小化DFA，它的思想很简单，我们用子集构造法得到的DFA的总是不包含重复前缀的，因为我们是从前往后合并状态节点，一个状态通过一个字母表元素能到达的所有状态都被构造为一个新节点。那么顺着这个思路，我们只要先求子集构造，再将得到的DFA反转方向，再求一遍子集构造法就能得到最小DFA。

•给定NFA n，等价的最小DFA的表达式：

•Reachable(subset(reverse(reachable(subset(reverse(n))))))

附github地址：https://github.com/lheing/Regex