您好,欢迎访问三七文档
当前位置:首页 > 办公文档 > 统计图表 > 正则表达式的DFA算法
正则表达式1正则表达式的定义正则表达式(RegularExpression)是一种强大的,便捷的,高效的文本处理工具,它可以表示比单字符、字符串集合等更加复杂的搜索模式。下面首先给出正则表达式和它所表达语言的形式化定义。一个正则表达式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)*)的解析树可以表示如下:·TA·AG·|GA·A··|*AA。程序中使用这个二叉树的后序遍历序列来存储这个解析树,那么上面那个正则表达式的存储序列如下:AT·GA·|AG·AA·A·|*·。函数re2post就是将输入的正则表达式字符串转换成解析树的后序遍历序列。解析过程中有两个重要的变量,natom和nalt,natom表示解析到这个字符为止,已经有多少个原子结构,而nalt表示解析到这个字符为止,已经有多少个分支结构。正则表达式中的括号表示一个子表达式,这个子表达式对于括号外面的表达式来说是一个原子结构,它内部的natom和nalt的值和外部的表达式的这些值没有关系。为了正确的处理这种括号及其嵌套,程序中使用堆栈来辅助解析,每当碰见“(“,将当前的natom和nalt压入栈中,新的natom和nalt从零开始;而解析到”)“时,则根据当前的natom和nalt值进行后续处理,然后从栈中弹出上一层的natom和nalt。具体的处理算法如下:Parse(p=p1p2…pm,last)v=0;Whileplast≠$DoIfplast∈ΣThenIf(natom1)Then--natom;v←v+'.';EndIfv←v+plast;natom++;ElseIf='|'v←v+(natom-1)×'.'nalt++;ElseIf='*'or'+'or'?'v←v+plast;ElseIf='('If(natom1)Then--natom;v←v+'.';EndIfpush(natom,nalt);nalt←0;natom←0;ElseIf=')'v←v+(natom-1)×'.'v←v+nalt×'|'pop(natom,nalt);natom++;EndIfEndwhilev←v+(natom-1)×'.'v←v+nalt×'|'Returnv;3构造NFA有多种方式用来从正则表达式构造NFA,最常见的两种,也是实践中经常使用的是Thompson构造法和Glushkov构造法。Thompson方法简单,并且构造的NFA中状态数量(最多2m个)和转移数量(最多4m个)都是线性的。这种自动机存在ε-转移,即空转移。Thompson自动机Thompson自动机构造的核心思想是先形成正则表达式RE对应的树表示Tre,然后自底向上地对树的每个节点v,构造一个自动机Th(v)来识别以v为根的子树所表达的语言。根据不同类型的中间节点和叶节点,有不同的自动机构造方法,具体情况如下。空字的构造方法。自动机由连接两个节点而组成IFε单字符α的构造方法,与空字类似,只不过转移是使用字符来标识,而不是使用空字符串。IFα相连节点的构造法。将两个子节点vl和vr对应的Thompson自动机合并,即第一个自动机的终止状态成为第二个自动机的初始状态。vlvrIF联合节点的构造法。对于联合节点,则必须通过子节点对应的自动机Th(vl)和Th(vr)中的一个。这时需要ε-转移。构造过程中,必须添加两个新的状态:一个是初始状态I,从它有两个ε-转移分别到自动机Th(vl)和Th(vr)的初始状态;另一个是终止状态F,从自动机Th(vl)和Th(vr)的终止状态分别由ε-转移到达终止状态F。它表达的语言是REvl|REvr。vlvrIFεεεε星节点的构造方法,它使用了同联合节点构造方法相同的思想。首先,因为对于语言REv*,节点v的唯一子节点v*可以被重复任意多次,所以需要创建一个从自动机Th(v*)的终止状态指向其初始状态的ε-转移。但是星符号也意味着自动机Th(v*)可以被忽略。因此需要创建初始节点I和终止节点F,并用一个ε-转移把它们连接起来。另外,再创建两条ε-转移分别用来从节点I指向Th(v*)的初始状态以及从Th(v*)的终止状态指向F。最终,自动机识别的语言是(REv*)*。v*IFεεεε整个Thompson算法包含自底向上的树的遍历,同时保证根节点开始构造的自动机即为能够表示整个正则表达式的Thompson自动机。在构造树表示中的每一个节点时,自动机中相应地最多增加2个状态和4个转移。因此,构造完成后,状态与转移的数量最多为2m和4m个。下面图表示了正则表达式(AT|GA)((AG|AAA)*)的构造过程。IFATIFGAIFεεεεATGAIFAGIFAAAIFεεεεAGAAAIεεεεAGAAAFεεεε1234560εεεεATGA910111213157εεεεAGAA14A81716εεεThompson算法由函数post2nfa实现。post2nfa函数输入一个数组表示的解析树,返回Thompson自动机,它使用了下面两种数据结构。typedefstruct_state{intc;表示状态的特性,小于256时,表示此状态输入c将转移到out指向的状态struct_state*out;下一个状态struct_state*out1;c是Split时,指向下一个分支状态intlastlist;intstateid;状态编号}State;typedefunion_ptrlist{union_ptrlist*next;State*s;}Ptrlist;typedefstruct_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();/*生成一个新的Split状态s,指向e1和e2的start状态*/s=state(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(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:加号节点的构造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状态。01234εεεεATGA115678εεAGAA9A10124DFA构造DFA算法的核心思想是,当使用NFA遍历文本时,会经过很多转移,因此会激活一个状态集合。然而,DFA在一个时刻只有一个确定的活动状态,因此可以在NFA的状态集合上定义相对应的DFA。该思想的关键在于,确定性自动机的当前唯一状态就是NFA的当前活动状态集合。在NFA中,E(s)表示状态s对应的ε闭包,它是在NFA中状态s能够通过ε-转移到达的所有状态的集合。假设NFA为(Q,Σ,I,F,Δ),那么DFA定义
本文标题:正则表达式的DFA算法
链接地址:https://www.777doc.com/doc-3383215 .html