转载

简易正则表达式引擎的实现

正则表达式基本每个程序员都会用到，实现正则表达式引擎却似乎是一个很难的任务。实际上，掌握《编译原理》前端的词法分析部分知识就能够实现一个简单的正则表达式引擎。这里推荐一下网易云课堂的课程。 http://mooc.study.163.com/course/USTC-1000002001?tid=1000003000#/info

基本的正则表达式正则表达式由字符与元字符组成，整个表达式用于描述符合某些特定特征的一类字符串，比如说表达式：abc，它表示 "abc" 这个字符串，由 'a', 'b', 'c' 三个字符按顺序连接在一起。本文要实现的正则表达式比较简单，只实现连接、选择、闭包的功能。定义直接从ppt里截图：

简易正则表达式引擎的实现

实现的大概步骤如下：

简易正则表达式引擎的实现

NFA指的是非确定自动机，对任意的字符，有多个状态可以转换。DFA指的是确定自动机，对任意的字符，最多只有一个状态可以转换。

Thompson算法是一个递归算法，先将单个字符转换为nfa，再根据规则将nfa组合起来。单个字符（比如c）的转化如下

简易正则表达式引擎的实现

两个字符（比如e1e2）则中间用ε连接

简易正则表达式引擎的实现

接下来是选择（比如e1|e2）

简易正则表达式引擎的实现

闭包(比如e1*)比较复杂

简易正则表达式引擎的实现

知道了如何将小的nfa组合成大的nfa，那怎么处理正则表达式，将其转换为nfa呢？我们可以像处理四则运算那样，用两个栈来解决，但这只能应对简单情况。还可以用递归下降分析构建抽象语法树，a|b的语法树如下，递归下降分析的具体做法可以看前面推荐的视频或直接看源码

简易正则表达式引擎的实现

由于nfa对任意的字符，有多个状态可以转换，我们需要将其转换为dfa。我们的nfa实际上是ε-NFA，有很多ε边，而dfa是没有ε边的，所以我们可以通过子集构造算法去除这些ε边。子集构造算法的大概思路是将从状态A出发接收某个字符能到达的所有状态（包括接收字符后再通过ε边到达）构成一个子集，这个子集所能到达的所有状态又构成一个子集，到最后就能消除ε边，得到dfa。

对于下图的nfa

简易正则表达式引擎的实现