正则表达式的DFA算法.docx

《正则表达式的DFA算法.docx》由会员分享，可在线阅读，更多相关《正则表达式的DFA算法.docx（32页珍藏版）》请在三一办公上搜索。

1、正则表达式的DFA算法正则表达式 1 正则表达式的定义 正则表达式是一种强大的，便捷的，高效的文本处理工具，它可以表示比单字符、字符串集合等更加复杂的搜索模式。下面首先给出正则表达式和它所表达语言的形式化定义。 一个正则表达式RE是符号集合 , |, *, (, ) 上的一个字符串，它可以递归定义如下： 空字符是正则表达式。 任意字符是正则表达式。 如果RE1和RE2都是正则表达式，则，和亦是正则表达式。 通常可以简写为RE1RE2。符号“”，“*”，“|”称为操作符，可以通过为每个操作符赋予优先级来消除更多的括号。为了方便起见，这里使用了额外的后缀操作符“+”，它的含义是RE+=RERE*。

2、其他所使用的操作符如”?”，字符组，”.”等实际上都可以用上面的方式来表达。下面定义正则表达式所表达的语言。 正则表达式RE所表达的语言是上的一个字符串集合。根据RE的结构，可以将它递归的定义如下： 如果RE是，则L(RE)=，即空串。 如果RE是，则L(RE)=，即包含一个字符的单串。 如果RE是这种形式，则L(RE) = L(RE1)。 如果RE是这种形式，则L(RE) = L(RE1) L(RE2)，其中W1W2可以看成是字符串集w的集合，其中，w = w1w2并且w1W1，w2W2。操作符表示字符串的连接。 如果RE是这种形式，则L(RE) = L(RE1)L(RE2)，是这两种语言的

3、并集，“|”称为并操作符。 如果RE是这种形式，则L(RE) = L(RE)* = i 0L(RE)i，其中L0=并且Li = LLi-1，它表示字符串集合是由0个或者多个RE1表达的字符串连接而成。“*“称为星操作符。 正则表达式RE的规模是指它所包含的属于字母表的字符的个数，在算法复杂性分析中，它是一个重要的度量。 在文本T中搜索正则表达式RE的问题就是找到文本中所有属于语言L(RE)的字串。搜索的方法是首先将正则表达式解析成一颗表达式树，然后将表达式树转换成非确定性有限自动机。直接使用NFA进行搜索是可行的，然而NFA算法处理速度通常比较慢，一般的，搜索过程最坏情况时间复杂度是O(mn)

4、，但是所需存储空间并不多。另外一种策略是将NFA转变成确定性有限自动机，它的搜索时间是O(n)，但是构造这样的一个自动机所需的最坏情况时间和空间复杂度都是O(2m)。 2 构造解析树 通常来说，解析树并不是唯一的。在解析树中，每个叶节点都是使用中的一个字符来标识的，而每个中间节点则使用操作符集合|, , *中的一个进行标识。 一种可能的解析树使用二叉树来表示，二叉树的父节点是一个操作符，两个子节点表示这个操作符作用的两个子表达式。如正则表达式(AT|GA)(AG|AAA)*)的解析树可以表示如下： |*|AAATGGAAA。 程序中使用这个二叉树的后序遍历序列来存储这个解析树，那么上面那个正则

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

6、一层的natom和nalt。具体的处理算法如下： Parse( p = p1p2pm, 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; nat

7、om 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中状态数量和转移数量都是线性的。这种自动机存在-转移，即空转移。 Thompson自动机 Thompson自动机构造的核心思想是先形成正则表达式RE对应的树表示Tre

8、，然后自底向上地对树的每个节点v，构造一个自动机Th(v)来识别以v为根的子树所表达的语言。根据不同类型的中间节点和叶节点，有不同的自动机构造方法，具体情况如下。 空字的构造方法。自动机由连接两个节点而组成 单字符的构造方法，与空字类似，只不过转移是使用字符来标识，而不是使用空字符串。 相连节点的构造法。将两个子节点vl和vr对应的Thompson自动机合并，即第一个自动机的终止状态成为第二个自动机的初始状态。 IFIFIvlvrF联合节点的构造法。对于联合节点，则必须通过子节点对应的自动机Th(vl)和Th(vr)中的一个。这时需要-转移。构造过程中，必须添加两个新的状态：一个是初始状态I，

9、从它有两个-转移分别到自动机Th(vl)和Th(vr)的初始状态；另一个是终止状态F，从自动机Th(vl)和Th(vr)的终止状态分别由-转移到达终止状态F。它表达的语言是REvl|REvr。 vlIFvr星节点的构造方法，它使用了同联合节点构造方法相同的思想。首先，因为对于语言REv*，节点v的唯一子节点v*可以被重复任意多次，所以需要创建一个从自动机Th(v*)的终止状态指向其初始状态的-转移。但是星符号也意味着自动机Th(v*)可以被忽略。因此需要创建初始节点I和终止节点F，并用一个-转移把它们连接起来。另外，再创建两条-转移分别用来从节点I指向Th(v*)的初始状态以及从Th(v*)的

10、终止状态指向F。最终，自动机识别的语言是(REv*)* 。 v*IF整个Thompson算法包含自底向上的树的遍历，同时保证根节点开始构造的自动机即为能够表示整个正则表达式的Thompson自动机。 在构造树表示中的每一个节点时，自动机中相应地最多增加2个状态和4个转移。因此，构造完成后，状态与转移的数量最多为2m和4m个。下面图表示了正则表达式(AT|GA)(AG|AAA)*)的构造过程。 IATFFIGAFATIGAAGFIFIAAAFAGIAAAGAAAAIF89A10G111601A2T3712A13A14A15174G5A6Thompson算法由函数post2nfa实现。post2n

11、fa函数输入一个数组表示的解析树，返回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

12、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, lis

13、t1(&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; /* 生成一个新的Split状态s，指向e1和e2的start状态*/ s = state(

14、g, Split, e1.start, e2.start); /* 生成一个新的Frag，用Split的start状态作为start状态，终止状态为e1和e2的终止状态的连接，压入栈中 */ push(frag(s, append(e1.out, e2.out); break; case ?+256: 问号节点的构造 e = pop; /* 生成一个新的Split状态s，指向e的start状态和-转移*/ s = state(g, Split, e.start, NULL); /* 生成一个新的Frag，用Split的start状态作为start状态，终止状态为e和s的终 push(frag(

15、s, append(e.out, list1(&s-out1); break; case *+256: 星节点的构造 e = pop; /* 生成一个新的Split状态s，指向e1的start状态和-转移*/ s = state(g, Split, e.start, NULL); /* e的下一个状态回指s */ patch(e.out, s); /* 生成一个新的Frag，用Split的start状态作为start状态，终止状态为s的止状态的连接，压入栈中 */ 终止状态，压入栈中 */ push(frag(s, list1(&s-out1); break; case +256: 加号节点的

16、构造 e = pop; /* 生成一个新的Split状态s，开始状态为e1的start状态和终止状态为-转移*/ s = state(g, Split, e.start, NULL); patch(e.out, s); /* 生成一个新的Frag，用e的start状态作为start状态，终止状态为s的终止push(frag(e.start, list1(&s-out1); break; 状态，压入栈中 */ 下面是正则表达式(AT|GA)(AG|AAA)*)的NFA。图中阴影的状态是Split状态。 G40A1T112G105A6A3A127A8A94 DFA构造 DFA算法的核心思想是，当使

17、用NFA遍历文本时，会经过很多转移，因此会激活一个状态集合。然而，DFA在一个时刻只有一个确定的活动状态，因此可以在NFA的状态集合上定义相对应的DFA。该思想的关键在于，确定性自动机的当前唯一状态就是NFA的当前活动状态集合。 在NFA中，E(s)表示状态s对应的闭包，它是在NFA中状态s能够通过-转移到达的所有状态的集合。 假设NFA为，那么DFA定义为： 其中，并且。 上述定义中的(S, )表示：对于S中所有可能的活动状态s，可以通过标记为字符的转移找到所有可能的状态s，然后再从跟随所有可能的-转移寻找其他状态。 算法中DFA状态使用数据结构 typedef struct _dState

18、 List l; 指向一个数组，数组中是这个DFA状态对应的NFA状态的集合 struct _dState *next256;转移表 struct _dState *left; struct _dState *right; int id; 状态id int flags; DState; Dstate是用二叉树的形式组织起来的，以l作为关键字。算法的思想如下： build_dstate For Do If (d, , Null) d = nextstate(d, ) (d, , d) build_dstate(d) End If Endfor nextstate(DState *d, ) For

19、 s d-l Do If s-c = addstate(l, s-out); End If Endfor d= dstate(l) 根据l生成一个Dstate Return d 将s状态上能够通过-转移到达的状态放入l中，实际上就是s的闭包 addstate(List *l, State *s) If(s-c = Split) s状态具有-转移 addstate(l, s-out); addstate(l, s-out1); Return l; EndIf l l s Return l; 下面是正则表达式(AT|GA)(AG|AAA)*)的DFA，加入了初始自环，即.*(AT|GA)(AG|A

20、AA)*). A1AGTG6ATA5GTG9AT0GTG10A2GAG3ATAGTA4G7A8上图中，黑色的箭头表示输入A后状态的转移，黄色的箭头表示输入G，紫色的箭头表示输入T后状态的转移，红色的箭头表示其余的输入表示的状态转移，有两个圈的状态表示终止状态。 使用DFA进行搜索十分简单，从状态0开始，依次读入字符，转移到下一个状态，如果这个状态是终止状态，则发现一个匹配，否则继续读入字符，直到读完为止。 5 Glushkov自动机 Glushkov自动机通过只对字符计数，可以标记出字符表中每个字符在正则表达式RE中的位置。例如，(AT|GA)(AG|AAA)*)标记为(A1T2|G3A4)(

21、A5G6|A7A8A9)*)。我们使用表示对正则表达式RE进行标记的标记表达式，使用L表示它对应的语言，其中每个字符都包含它的位置的索引。于是，上面的例子正则表达式的语言为 A1T2，G3A4，A1T2A5G6，。用Pos(首先，在标记表达式) = 1m表示中位置的集合，用表示标记后的字母表。 上构造自动机，这个自动机识别语言L。然后，通过消除所有字符的位置索引，可以从中抽取Glushkov自动机，从而识别语言L(RE)。 字符位置的集合，加上一个初始状态0，可以当做自动机状态集合的索引。创建m+1个状态，标记为0到m。状态j表示已经从文本中读取了一个字符串，该字符串在NFA中的位置j结束。当

22、再读入一个新的字符时，需要知道从位置j通过可以到达的位置。这个位置可以通过Glushkov自动机计算出来。 为了说明Glushkov算法，下面首先引入四个新的定义。其中，y表示引字符。 中y处的被索集合First表示L的初始状态集合，也就是说，在这些位置可以开始读入字符。上面的例子中，First(A1T2|G3A4)(A5G6|A7A8A9)*)=1，3。 集合Last表示 的终止状态集合，也就是说，在这些位置可以识别出L(RE)中的字符串。上面的例子中，Last(A1T2|G3A4)(A5G6|A7A8A9)*)=2, 4, 6, 9。 集合Follow表示在Pos中从x可以到达的所有位置。

23、上面的例子中，从位置6可以到达的位置集合为Follow(A1T2|G3A4)(A5G6|A7A8A9)*), 6)=7, 5。 函数EmptyRE可以递归的定义如下： 当属于L(RE)时，它的值为；否则它的值为。 确定的Glushkov自动机可以识别语言L，它可以通过下面的方法进行构造： 其中， S = 0, 1, , m是状态集合，它是位置Pos()的集合，初始状态为 I = 0。 F = Last(EmptyRE 0)是终止状态集合。通常，如果状态i属于Pos，则i是一个终止状态。当空字属于L时，初始状态0也是终止状态。这时，EmptyRE = ，则EmptyRE 0= 0；否则Empty

24、RE 0= 是自动机的转移函数，定义为： (5.1) 通常情况下，如果状态y在状态x之后，那么从x到y有一个转移y。从初始状态开始的转移定义为： 图给出了标记正则表达式对应的Glushkov自动机。 (5.2) 为了获得原始的RE的Glushkov，只要简单地去掉标记自动机的位置索引即可。在这个过程中，自动机通常会变成非确定的。新的自动机对应语言L(RE)。例子(A1T2|G3A4)(A5G6|A7A8A9)*)对应的Glushkov自动机如所示。 Glushkov算法基于正则表达式RE对应的树表示TRE。树中的每个节点v都代表RE的子表达式REv。算法中使用了下列与v相关的变量： First

25、(v)：表示集合中所有位置的列表。 Last(v)：表示集合中所有位置的列表。 Emptyv：如果中包含空串，它为True，否则为False。 对于每个节点，这些变量都是后序计算的，也就是说，先计算出v的所有子节点的变量值，然后再计算v的变量值。如果v是”|”或者”.”，则把它的两个子节点分别记做vl和vr；如果v表示”*”，则把它唯一的子节点记做v*。 集合Follow(x)是一个全局变量，对于每一个节点v，Follow(x)的值要根据它在子表达式中位置的变化而不断更新。 Glushkov_variables(vRE, lpos) If v = | (vl,vr) OR v = (vl,vr

26、) Then lpos Glushkov_variables (vl,lpos) lpos Glushkov_variables (vr,lpos) Else If v = * (v*) Then lpos Glushkov_variables (v*,lpos) End of If If v= () Then First(v) ，Last(v) , Emptyv Then If v = ()， Then lpos lpos + 1 First(v) lpos, Last(v) lpos, Emptyv , Follow(lpos) Then If v = | (vl,vr) Then Fir

27、st(v) First(vl) First(vr) Last (v) Last (vl) Last (vr) Emptyv Emptyvl Emptyvr Then If v = (vl,vr) Then First(v) First(vl) (Emptyvl First(vr) Last (v) (Emptyvr Last (vl) Last (vr) Emptyv Emptyvl Emptyvr For x Last(vl) Do Follow(x) Follow (x) First(vr) Then If v = * (v*) Then First(v) First(v*), Last(

28、v) Last(v*), Emptyv For x Last(v*) Do Follow(x) Follow (x) First(v*) End of If Return lpos Glushkov(RE) vRE Parse(RE,1) m Glushkov_variables(vRE, 0) = For i 0m Do create state i For x First(vRE) Do(0, x, x) For i 0m Do For x Follow(i) Do(i, x, x) End of for For x Last(vRE) (Empty vRE 0) Do mark x as

29、 terminal 上面给出了Glushkov_variables(vRE,lpos)的递归算法。对于正则表达式RE的树表示中的每个节点v，该算法提供计算变量First(v)，Last(v)，Follow(x)和Emptyv的方法。为了计算每个节点vRE的值，该算法使用后续遍历树中所有的节点。 整个Glushkov算法包括：将RE转化成树vRE，并且使用Glushkov_variables(vRE,0)计算它对应的变量，然后从树vRE的根对应的变量开始构造Glushkov自动机。 6 Glushkov自动机的位并行算法 存储DFA状态的一种可行方法就是使用O(m)位的位掩码。其中，如果NFA的

30、第i个状态属于DFA，那么位掩码的第i位就为1。 NFA可以表示如下： ，运算）。 使用位掩码的Glushkov_variables算法如下所示： ， Glushkov自动机的NFA是-free的 证明：由公式(5.1)，标记正则表达式的转移函数为，即当前为x状态，输入y，转移到状态y。注意y是正则表达式第y个字符和y的组合，显然不为空。转换后的正则表达式只是去掉位置索引，因此转移函数中y为正则表达式第y个字符，也是不为空的。故自动机的NFA是-free的。 所有指向状态y的箭头都标记着同样的字符 证明：同样，根据转移函数，到达状态y的输入是y，显然是同一个字符。 假设B()为包含字符的位置的

31、集合，则有： (6.1) 证明：设y(x, )。这意味着y能够从x位置输入到达，因此。相反，假设，那么表明可以从x位置转移到y，并且输入也能到达y。根据性质，到达y的所有箭头都标记为，显然也包括离开x的，因此y(x, )。 不会有任何箭头到达Glushkov自动机的NFA中的0状态 证明：所有的箭头都是根据公式(5.1)生成的，并且根据Follow函数的定义，0状态不在任何其他状态的Follow状态集合中。 下面我们使用性质来获得DFA的表示。计算DFA的转移表可以通过两个表来进行，一个是B，给出了每个字符可达到状态的位掩码。第二个是Follow的确定性版本，一个从状态的集合到状态的集合的表T

32、，满足： (6.2) 这个表给出了从一个D中的激活状态，不管通过哪个字符，可到达的状态集合。由性质，下式成立： (6.3) 注意，存储：22，需要(m+1)(2)位，而存储T：2需要(m+1)(2m+1+)位，节省了很多的空间。 下面给出从Follow计算T的算法： m+1m+1m+1m+12m+1和B：2m+1我们现在给出基于位掩码以及上面构建的搜索算法。首先，用First和Last表示整个正则表达式的对应的变量。从技术的便利上看，可以设置Follow(0)=First。其次，我们增加一个自循环在表达式的开始，以便可以搜索到从任意位置开始的正则表达式的语言。下面给出搜索算法： 上面提到，存储

33、T和B需要(m+1)(2m+1+)位。但是在经典的DFA算法中，只需要存储能够达到的状态，这个状态远小于2m+1所有可能的状态。这里也可以使用类似的算法，只计算可以到达的T。下面的算法给出了递归构建T的过程，从D = 01开始，假定T已经初始化为0，B，Follow和m已经计算出来了。 m7 位并行Glushkov算法的实现 7.1 位掩码 我们使用位掩码来表示集合。位掩码实际上是内存中一块连续的内存，内存地址低的是位掩码的低位。程序中提供了一系列对位掩码的操作函数和宏。如下所示： static BITMAP* makebitmap( unsigned numbytes,unsigned nu

34、m )； 生成num个位掩码，每个占用numbytes个字节，返回指向位掩码的指针； void free_bitmap(BITMAP* map) 释放位掩码的空间； SETBIT(c,map,val) 宏，设置位掩码map的第c位的值为val； TESTBIT(c,map) 宏，位掩码map的第c位是否为1？； BITCOPY(size,D,S) 宏，拷贝位掩码，DS，size个字节； TRAVEL_BITMAP_BEGIN(size,map,i) TRAVEL_BITMAP_END 遍历位掩码map中所有为1的位； int compare_bitmap(int numbytes, BITMA

35、P *A, BITMAP* B) 比较位掩码A和B的大小，从最高字节开始，逐个字节比较，每个字节看成无符号数； void bitmap_AND(int numbytes, BITMAP *C, BITMAP* A, BITMAP* B) 位掩码与运算，C=A&B； void bitmap_OR(int numbytes, BITMAP *C, BITMAP* A, BITMAP* B) 位掩码或运算，C=A | B； int is_bitmap_empty(unsigned char* map, unsigned numbytes) 位掩码map是否为0，是，返回1，否则返回0； 7.2 Ha

36、sh表 程序中T表是用位掩码来索引的，如果位数较多的话，直接通过位掩码找到对应的T的表项很麻烦。这里使用Hash函数将位掩码换算成一个无符号整数。对于T表，使用一个hash表来保存。每个位掩码换算成整数后，再hash成Key值，在表中查询。对于两个一样的Key，使用链表将它们穿在一个Key下面。Hash表的结构如下： typedef struct hash_key_node struct hash_key_node* next; unsigned int value; unsigned int key; BITMAP* D; BITMAP* T; hash_key_node; typedef

37、struct hash_node struct hash_key_node* head; unsigned int value; /这个key下面有几个节点 hash_node; typedef struct hashtable unsigned int bucket_num; hash_node* bucket; hashtable; 每个hash_key_node节点中都存储了D和T，保存D目的是在插入一个相同key时，比较是否D相同。由于在生成T表前不知道有效的T的个数，故hash表的大小是动态变化的。为了不会在一个Key下面挂多个节点，在当前T的表项个数大于2/3的hash表的buck

38、et数目时，就重新生成一个更大数目的表。 7.3 Glushkov算法的实现 程序中实现的Glushkov算法和上面的伪代码算法很相似，这里就不在详述了。 8 一个具体的例子 正则表达式为(AT|GA)(AG|AAA)*)，字符串为AAAGATAAGATAGAAAA。 B表如下： BA(0x41):.11 10110011 BG(0x47):.00 01001001 BT(0x54):.00 00000101 T表如下： Hash0 :T.00 00000000 =.00 00000000 Hash6 :T.00 00010011 =.00 10101111 Hash14:T.00 00001

39、001 =.00 00011011 Hash18:T.00 10100011 =.01 01001111 Hash19:T.01 10100011 =.11 01001111 Hash20:T.10 10100011 =.01 11101111 Hash31:T.00 00000001 =.00 00001011 Hash37:T.00 10110011 =.01 11101111 T.00 01001001 =.00 10111011 Hash40:T.00 00000011 =.00 00001111 Hash41:T.01 00000011 =.10 00001111 Hash42:T.

40、10 00000011 =.00 10101111 Hash43:T.11 00000011 =.10 10101111 Hash49:T.00 00000101 =.00 10101011 Final: .10 01010100 从D等于.00 00000001开始： 1. 读入A T.00 00000001 .00 00001011 & BA:.11 10110011 D:.00 00000011 2. 读入A T.00 00000011 .00 00001111 & BA:.11 10110011 D:.00 00000011 3. 读入A T.00 00000011 .00 00001

41、111 & BA:.11 10110011 D:.00 00000011 4. 读入G T.00 00000011 .00 00001111 & BG:.00 01001001 D:.00 00001001 5. 读入A T.00 00001001 .00 00011011 & BA:.11 10110011 D:.00 00010011 Final:.10 01010100 因为D&F 0m+1，所以标记一个成功匹配 6. 读入T T.00 00010011 .00 10101111 & BT:.00 00000101 D:.00 00000101 Final:.10 01010100 因为D&F 0m+1，所以标记一个成功匹配 7. 读入A T.00 00000101 .00 10101011 & BA:.11 10110011 D:.00 10100011 8. 读入A T.00 10100011 .01 01001111 & BA:.11 10110011 D:.01 00000011 9. 读入G T.01 00000011 .10 00001111 & BG:.00 01001001 D:.00 00001001 10. 读入A T.0