正则表达式的DFA算法

正则表达式

1 正则表达式的定义

正则表达式（Regular Expression）是一种强大的，便捷的，高效的文本处理工具，它可以表示比单字符、字符串集合等更加复杂的搜索模式。下面首先给出正则表达式和它所表达语言的形式化定义。

一个正则表达式RE是符号集合Σ { ε, |,·, *, (, ) }上的一个字符串，它可以递归定义如下：

空字符ε是正则表达式。 任意字符α∈Σ是正则表达式。

如果RE1和RE2都是正则表达式，则（RE1），（RE1·RE2），（RE1 | RE2）和（RE1*）亦是正则表达式。

通常（RE1·RE2）可以简写为RE1RE2。符号“·”，“*”，“|”称为操作符，可以通过为每个操作符赋予优先级来消除更多的括号。为了方便起见，这里使用了额外的后缀操作符“+”，它的含义是RE+=RE·RE*。其他所使用的操作符如”?”，字符组，”.”等实际上都可以用上面的方式来表达。下面定义正则表达式所表达的语言。

正则表达式RE所表达的语言是Σ上的一个字符串集合。根据RE的结构，可以将它递归的定义如下：

如果RE是ε，则L(RE)={ε}，即空串。 如果RE是α∈Σ，则L(RE)={α}，即包含一个字符的单串。 如果RE是（RE1）这种形式，则L(RE) = L(RE1)。

如果RE是（RE1RE2）这种形式，则L(RE) = L(RE1) L(RE2)，其中W1W2可以看成是字符串集w的集合，其中，w = w1w2并且w1∈W1，w2∈W2。操作符表示字符串的连接。 如果RE是（RE1|RE2）这种形式，则L(RE) = L(RE1)∪L(RE2)，是这两种语言的并集，“|”称为并操作符。

如果RE是（RE1*）这种形式，则L(RE) = L(RE)* = ∪i ≥ 0L(RE)i，其中L0={ε}并且Li = LLi-1，它表示字符串集合是由0个或者多个RE1表达的字符串连接而成。“*“称为星操作符。

正则表达式RE的规模是指它所包含的属于字母表Σ的字符的个数，在算法复杂性分析中，它是一个重要的度量。

在文本T中搜索正则表达式RE的问题就是找到文本中所有属于语言L(RE)的字串。搜索的方法是首先将正则表达式解析成一颗表达式树，然后将表达式树转换成非确定性有限自动机（NFA）。直接使用NFA进行搜索是可行的，然而NFA算法处理速度通常比较慢，一般的，搜索过程最坏情况时间复杂度是O(mn)，但是所需存储空间并不多。另外一种策略是将NFA转变成确定性有限自动机（DFA），它的搜索时间是O(n)，但是构造这样的一个自动机所需的最坏情况时间和空间复杂度都是O(2m)。

2 构造解析树

通常来说，解析树并不是唯一的。在解析树中，每个叶节点都是使用Σ∪{ε}中的一个字符来标识的，而每个中间节点则使用操作符集合{|, ·, *}中的一个进行标识。

一种可能的解析树使用二叉树来表示，二叉树的父节点是一个操作符，两个子节点表示这个操作符作用的两个子表达式。如正则表达式(AT|GA)((AG|AAA)*)的解析树可以表示如下：

·|*|AA··ATG··GA·AA。

程序中使用这个二叉树的后序遍历序列来存储这个解析树，那么上面那个正则表达式的存储序列如下：

A T · G A · | A G · A A · A · | * ·。

函数re2post就是将输入的正则表达式字符串转换成解析树的后序遍历序列。解析过程中有两个重要的变量，natom和nalt，natom表示解析到这个字符为止，已经有多少个原子结构，而nalt表示解析到这个字符为止，已经有多少个分支结构。正则表达式中的括号表示一个子表达式，这个子表达式对于括号外面的表达式来说是一个原子结构，它内部的natom和nalt的值和外部的表达式的这些值没有关系。为了正确的处理这种括号及其嵌套，程序中使用堆栈来辅助解析，每当碰见“（“，将当前的natom和nalt压入栈中，新的natom和nalt从零开始；而解析到”）“时，则根据当前的natom和nalt值进行后续处理，然后从栈中弹出上一层的natom和nalt。具体的处理算法如下：

Parse( p = p1p2…pm, last) v = 0；

While plast ≠ $ Do

If plast ∈ Σ Then If (natom > 1) Then --natom; v ←v+'.';

EndIf

v ←v + plast; natom++;

Else If = '|' v ←v + (natom-1)×'.' nalt++;

Else If = '*' or '+' or '?' v ←v + plast;

Else If = '(' If (natom > 1) Then

--natom; v ←v+'.'; EndIf

push(natom, nalt); nalt ← 0; natom ← 0; Else If = ')'

v ←v + (natom-1)×'.'

v ←v + nalt×'|' pop(natom, nalt); natom++; EndIf

Endwhile

v ←v + (natom-1)×'.'

v ←v + nalt×'|' Return v;

3 构造NFA

有多种方式用来从正则表达式构造NFA，最常见的两种，也是实践中经常使用的是Thompson构造法和Glushkov构造法。Thompson方法简单，并且构造的NFA中状态数量（最多2m个）和转移数量（最多4m个）都是线性的。这种自动机存在ε-转移，即空转移。

Thompson自动机

Thompson自动机构造的核心思想是先形成正则表达式RE对应的树表示Tre，然后自底向上地对树的每个节点v，构造一个自动机Th(v)来识别以v为根的子树所表达的语言。根据不同类型的中间节点和叶节点，有不同的自动机构造方法，具体情况如下。

空字的构造方法。自动机由连接两个节点而组成

单字符α的构造方法，与空字类似，只不过转移是使用字符来标识，而不是使用空字符串。

相连节点的构造法。将两个子节点vl和vr对应的Thompson自动机合并，即第一个自动机的终止状态成为第二个自动机的初始状态。

IεFIαFIvlvrF 联合节点的构造法。对于联合节点，则必须通过子节点对应的自动机Th(vl)和Th(vr)中的一个。这时需要ε-转移。构造过程中，必须添加两个新的状态：一个是初始状态I，从它有两个ε-转移分别到自动机Th(vl)和Th(vr)的初始状态；另一个是终止状态F，从自动机Th(vl)和Th(vr)的终止状态分别由ε-转移到达终止状态F。它表达的语言是REvl|REvr。

vlεIεFεvrε 星节点的构造方法，它使用了同联合节点构造方法相同的思想。首先，因为对于语言REv*，节点v的唯一子节点v*可以被重复任意多次，所以需要创建一个从自动机Th(v*)的终

止状态指向其初始状态的ε-转移。但是星符号也意味着自动机Th(v*)可以被忽略。因此需要创建初始节点I和终止节点F，并用一个ε-转移把它们连接起来。另外，再创建两条ε-转移分别用来从节点I指向Th(v*)的初始状态以及从Th(v*)的终止状态指向F。最终，自动机识别的语言是(REv*)* 。

εv*εIεεF 整个Thompson算法包含自底向上的树的遍历，同时保证根节点开始构造的自动机即为能够表示整个正则表达式的Thompson自动机。

在构造树表示中的每一个节点时，自动机中相应地最多增加2个状态和4个转移。因此，构造完成后，状态与转移的数量最多为2m和4m个。下面图表示了正则表达式(AT|GA)((AG|AAA)*)的构造过程。

IATF

εF

IGAF

ATεIεGAεAG FI

εFIAAAF AGεIεAAAε

εGAεεAAAεεεIεFε εε89A10G11ε16ε01A2Tε3ε712A13A14A15εε17εε4G5A6ε

Thompson算法由函数post2nfa实现。post2nfa函数输入一个数组表示的解析树，返回Thompson自动机，它使用了下面两种数据结构。

typedef struct _state {

int c; 表示状态的特性，小于256时，表示此状态输入c将转移到out指向的状态 struct _state *out; 下一个状态

struct _state *out1; c是Split时，指向下一个分支状态 int lastlist;

int stateid; 状态编号

} State;

typedef union _ptrlist {

union _ptrlist *next;

State *s; } Ptrlist;

typedef struct _frag {

State *start; Ptrlist *out; } Frag;

Frag结构是一个部分NFA，start指向NFA的开始状态，out指向一系列位置，这些位置需要被设置成这个部分NFA的下一个状态。函数中使用了一个Frag的栈来保存NFA的片段。

stackp = stack;

for(p=postfix; *p; p++){ switch(*p){ default: 单字符的构造 /* 生成一个新的状态s */ 中 */

s = state(g, *p, NULL, NULL);

/* 生成一个新的Frag，用s作为start状态，它的out作为终止状态，压入栈

push(frag(s, list1(&s->out))); break;

case '.'+256: 相连节点的构造 e2 = pop();

e1 = pop();

/* 连接两个相邻Frag，第一个的out指向第二个的start状态 */

patch(e1.out, e2.start);

/* 生成一个新的Frag，用e1的start状态作为start状态，e2的out作为终止状态，压入栈中 */

push(frag(e1.start, e2.out)); break;

case '|'+256: 联合节点的构造

e2 = pop(); e1 = pop();

本文来源：https://www.bwwdw.com/article/9rfh.html