《正则表达式匹配》word版.doc

正则表达式匹配正则表达式匹配2010-12-09 21：21正则表达式匹配也可以简单快速(下：实现部分)技术专题2009-10-04 00：29：16阅读706实现Thompson在1968年的论文里对多状态模拟策略进行了介绍。在他的文章里，NFA的状态是使用机器码序列来表示的，可能状态列表仅仅是一系列的函数调用指令。实际上，Thompson将正则表达式编译成了机器码。四十年后，计算机已经变得很快了，所以机器码的这种方法变得不太必要了。下面的章节里介绍一种使用标准c的实现。完整的源代码(少于400行)和测试脚本在这里(。实现：编译成NFA第一步就是把正则表达式编译成等价的NFA。在我们的c程序里，我们使用一个带指针的结构体来表示NFA。struct Stateint c；State*out；State*out1；int lastlist；每个状态可以用来代表下面的三个NFA片段，取决于c的值(lastlist是执行时使用的，下面还会解释)根据Thomspon的论文，编译器从一个正则表达式的前缀形式开始构建NFA，对于连接通过增加一个.来将该运算以运算符的形式显示化。通过一个独立函数re2post将中缀正则表达式比如a(bb)+a转换成后缀表达式abb.+.a.。(一个实际的实现并不需要用.来代替连接字符。一个实际的实现也可能解析的同时构建NFA而不是构建一个显示的后缀表达式。然而，后缀版本更加方便也更接近Thompson的论文)当编译器扫描后缀表达式的时候，它用过一个栈来维护一个已经计算好的NFA片段。Literals push new NFA fragments onto the stack,while operators pop fragments off the stack and then push anew fragment.比如，编译好abb.+.a.中的abb之后，栈里包含a,b和b的NFA片段。然后编译.,这时需要将两个b的NFA片段从栈里pop出来，然后将bb.的NFA片段压入栈。每个NFA片段是由开始状态和输出指针组成的：struct FragState*start；Ptrlist*out；对于片段来说，start是开始节点，out是一系列指向未链接到任何东西的状态指针的列表的指针。NFA片段里存在一些悬空指针。下面这些辅助函数可以帮助控制指针链表：Ptrlist*list1(State*outp)；Ptrlist*append(Ptrlist*l1,Ptrlist*l2)；void patch(Ptrlist*l,State*s)；list1创建一个新指针列表包括outp指针的。append将两个指针列表连接起来，并返回结果。patch将list1中的悬空指针连接使它们指向状态s：对于l里的每个指针outp,它设置*outp=s。给定上面这些基础内容及片段栈，编译过程实际上是一个在后缀表达式串上的简单循环。处理到最后只剩下一个单片段：添加一个匹配状态就完成了NFA的构建。State*post2nfa(char*postfix)char*p；Frag stack1000,*stackp,e1,e2,e；State*s；#define push(s)*stackp+=s#define pop()*-stackp stackp=stack；for(p=postfix；*p；p+)switch(*p)/*compilation cases,described below*/e=pop()；patch(e.out,matchstate)；return e.start；下面这些具体的编译实例，模拟了上面所描述的那些转换步骤。文本字符：default：s=state(*p,NULL,NULL)；push(frag(s,list1(&s-out)；break；连接：case.：e2=pop()；e1=pop()；patch(e1.out,e2.start)；push(frag(e1.start,e2.out)；break；选择：case|：e2=pop()；e1=pop()；s=state(Split,e1.start,e2.start)；push(frag(s,append(e1.out,e2.out)；break；Zero or one：case?：e=pop()；s=state(Split,e.start,NULL)；push(frag(s,append(e.out,list1(&s-out1)；break；Zero or more：case*：e=pop()；s=state(Split,e.start,NULL)；patch(e.out,s)；push(frag(s,list1(&s-out1)；break；One or more：case+：e=pop()；s=state(Split,e.start,NULL)；patch(e.out,s)；push(frag(e.start,list1(&s-out1)；break；实现：模拟NFA现在NFA已经构建好了，下面需要模拟执行。这个模拟执行需要追踪状态集，它们被保存到一个简单的链表里：struct ListState*s；int n；模拟执行使用了两个链表：clist是当前NFA所处在的状态集合，nlist是处理完当前状态NFA下一个将要到达的状态集合。初始时，clist只包含一个开始状态然后每次只在状态机里前进一步。intmatch(State*start,char*s)List*clist,*nlist,*t；/*l1 and l2 are preallocated globals*/clist=startlist(start,&l1)；nlist=&l2；for(；*s；s+)step(clist,*s,nlist)；t=clist；clist=nlist；nlist=t；/*swap clist,nlist*/return ismatch(clist)；为了避免每次循环迭代中分配内存，match用了两个已经预先分配好的链表l1和l2作为clist和nlist,每运行一步就将它们两个交换。如果最终的状态列表中包含匹配状态，那么就说与字符串匹配。intismatch(List*l)int i；for(i=0；i l-n；i+)if(l-si=matchstate)return 1；return 0；addstate增加一个状态到列表中，但是如果它已经在列表中了就不用添加了。如果每次添加都需要扫描整个链表会使效率很低；变量listid作为链表的生成数。当给链表添加一个状态s，它记录一个lastid在s-lastlist里。如果两个相等，那么说明s已经存在于已建立的链表中。addstate也要沿着未标注指针前进：如果s是一个具有两个指向新状态的未标注指针的分离状态，那么addstate增加那两个新状态而不是s到链表中。voidaddstate(List*l,State*s)if(s=NULL|s-lastlist=listid)return；s-lastlist=listid；if(s-c=Split)/*follow unlabeled arrows*/addstate(l,s-out)；addstate(l,s-out1)；return；l-sl-n+=s；开始链表创建一个初始状态列表通过增加开始状态：List*startlist(State*s,List*l)listid+；l-n=0；addstate(l,s)；return l；最后，每次读入一个单字符NFA就前进一步，使用当前列表clist来计算下一个列表nlist。voidstep(List*clist,int c,List*nlist)int i；State*s；listid+；nlist-n=0；for(i=0；i clist-n；i+)s=clist-si；if(s-c=c)addstate(nlist,s-out)；性能刚才描述的c实现并没有将效率考虑在内。即使如此，一个线性算法也能轻易地在效率上打败一个指数级算法。通过各种流行的正则表达式引擎测试那种病态字符串可以很清楚的看到这点。考虑正则表达式(a?)nan。如果a?不匹配任何字符，则它匹配字符串an，整个字符串将通过an匹配。考虑正则表达式的回溯实现如何实现zero-or-one的?,它首先尝试匹配1个然后尝试匹配0个。现在这里有n个这样的选择，这样总共有2n种可能。但是只有最后一种可能-对所有的?选择0才会导致匹配成功。所以这个回溯实现需要O(2n)，这样n最多可以扩展到n=25。与此相比，Thompson算法通过维护大概n个状态列表处理字符串，如果字符串的长度也为n，这样总的时间应该是O(n2)(运行时间是超线性的，因为伴随这输入的增加正则表达式本身并没有再改变。对于一个长为m的正则表达式运行在一个长为n的字符串上，Thompson NFA需要O(mn)时间)。下面的图形画出了(a?)nan匹配an的时间花费：需要注意，为了能够看到在一个图中看到一个宽广的时间跨度，图的y轴不同的位置采用了不同的时间单位。从图中可以明显的看出Perl,PCRE,Python,and Ruby都使用了递归回溯。当n=23时，pcre已经无法得到正确答案了，因为经过过多步骤之后它自动终止了递归回溯。在perl5.6里，perl的正则表达式引擎据说采用了备忘录来进行递归回溯搜索，以内存为代价，防止搜索过程花费指数级的时间，当然如果存到反向引用也还是要花指数级时间。正如图中所展示的，备忘录方法是不完全的：即使不存在前向引用，但perl的运行时间仍然是指数级的。尽管这里没有进行测试，实际上java也使用了回溯实现。实际上，java.util.regex接口也需要一个回溯实现，因为这样大量的java代码可以被替换成匹配路径。php使用了pcre库。图中的粗蓝线正是本文中描述的Thompson的c实现。awk，tcl，gnu grep以及gnu awk构建DFAs，要么预先计算出来要么使用下一节描述的on-the-fly构建方法。有些人可能认为这个测试对于回溯实现不公平，因为它专注于不常见的特例。但是这个观点忽略了一点：给你两个选择，一个实现是可预测，一致对所有的输入都有快速的运行时间，另一个通常很快速但是对于某些输入却需要花上数年的cpu时间，应该选择哪个是很明显的。Also,while examples as dramatic as this one rarely occur in practice,less dramatic ones do occur.Examples include using(.*)(.*)(.*)(.*)(.*)to split five space-separated fields,or using alternations where the common cases are not listed first.结果，程序员找到哪点开销最大然后再避免它，或者他们使用所谓的优化器。使用Thompson NFA模拟不需要这样的改变，因为它不存在开销巨大的正则表达式。缓存NFA构建DFA DFAs比NFAs效率更高，因为DFAs一次只有一个可选状态，任何NFA可以转换为等价的DFA状态机。比如这里有一个关于abab|abbb的NFA，图中具有状态标号。等价的DFA是：DFA里的每个状态对应于NFA里的一系列状态。另一方面，Thompsons NFA模拟执行也可以在等价的DFA上执行：每个列表对于某个DFA状态，函数每计算一步，给定一个列表和下一个字符，下一个DFA状态加入。Thompson算法模拟执行DFA通过需要时重新构建每个DFA状态。不是将这些工作推迟到每一步后面，我们可以将这些lists缓存到内存里，避免重复计算或者必要时计算出等价的DFA形式。这一节提出了这样的一种实现方式。从前面提到的NFA实现，我们只需要添加少于100行代码就可以构造一个DFA实现。为了实现缓存，我们首先引入一种新的数据类型来表示一个DFA状态：struct DStateList l；DState*next256；DState*left；DState*right；Dstate是链表l的缓存版本。数组next包含每个输入字符对应的指向下一个状态的指针：如果当前状态是d，下一个输入字符是c，那么d-nextc就是下一个状态。如果d-nextc=null，那么下一个状态就处于未计算状态。nextsate根据一个给定状态和字符来计算，记录返回下一个状态。正则表达式沿着d-nextc不断匹配，调用nextstate来计算下一个状态intmatch(DState*start,char*s)int c；DState*d,*next；d=start；for(；*s；s+)c=*s&0xFF；if(next=d-nextc)=NULL)next=nextstate(d,c)；d=next；return ismatch(&d-l)；All the DStates that have been computed need to be saved in astructure that lets us look up aDState by its List.To do this,we arrange them in abinary tree using the sorted List as the key.The dstate function returns the DState for agiven List,allocating one if necessary：DState*dstate(List*l)int i；DState*dp,*d；static DState*alldstates；qsort(l-s,l-n,sizeof l-s0,ptrcmp)；/*look in tree for existing DState*/dp=&alldstates；while(d=*dp)！=NULL)i=listcmp(l,&d-l)；if(i 0)dp=&d-left；else if(i 0)dp=&d-right；elsereturn d；/*allocate,initialize new DState*/d=malloc(sizeof*d+l-n*sizeof l-s0)；memset(d,0,sizeof*d)；d-l.s=(State*)(d+1)；memmove(d-l.s,l-s,l-n*sizeof l-s0)；d-l.n=l-n；/*insert in tree*/*dp=d；return d；nextstate运行NFA step，并返回相应的状态Dstate：DState*nextstate(DState*d,int c)step(&d-l,c,&l1)；return d-nextc=dstate(&l1)；最后，DFA的开始状态就是NFA的开始列表对于的DstateDState*startdstate(State*start)return dstate(startlist(start,&l1)；(正如在NFA模拟中一样，l1是预分配好的链表)这个DStates是DFA中的状态，但是DFA只有需要时才会建立：如果一个DFA状态搜索过程中并没有碰到，那么它也不会出现在缓存中。另一个变种可能是预先一次计算出所有的DFA。这样做可能可以通过去掉一些条件分支使匹配速度提高一些，但是以启动时间和内存使用为代价。人们可能会担心on-the-fly DFA构建带来的内存花费太大。因为Dstates仅仅是step函数的一个缓存，dstate实现可能选择丢弃目前为止的整个dfa如果缓存需求太大。实现缓存替换策略仅仅需要一些dstate和nextstate中的额外的代码行，加上进行内存管理的50行代码。一个参考实现可以在这里找到：使用类似的限制大小的缓存策略，使用一个32个缓存状态；这个也可以说明上图中在n=28时出现的性能转折)NFAS可以表现出很好的局部性：它们访问相同的状态集，沿着相同的转换指针不断的运行。这就使缓存变得很有意义：the first time an arrow is followed,the next state must be computed as in the NFA simulation,but future traversals of the arrow are just asingle memory access.实际的基于DFA的实现可以充分使用额外的优化让它运行地更快。还应该有一篇(还未写)文章更加详细的介绍基于DFA的正则表达式匹配实现。现实世界的正则表达式实际程序中的正则表达式使用多少要比我们上面介绍的正则表达式实现要复杂。这一节将简要的介绍下这些普通的实现；当然对于这些的介绍已经超过一篇介绍性的文章所应涉及的内容。字符类。0-9orw or.。字符类可以在编译时扩展到选择运算符，尽管如果为他们增加一个新的DFA节点类来表示可能更有效。posix还定义了一些新的字符类比如：upper：，根据不同的本地化方案具体含义可能有所不同，but the hard part of accommodating these is determining their meaning,not encoding that meaning into an NFA.转义序列。实际的正则表达式符号需要处理转义序列，一方面是为了匹配元字符，另一方面也是为了表示难以输入的字符比如n。重复计数。很多正则表达式实现提供了一个重复计数操作符n用来精确匹配n长度字符串；n,m用来匹配至少n但是至多m个字符；n,用来匹配n个或者更多个字符。递归回溯实现可以通过循环实现重复计数；NFA或者基于DFA的实现必须通过扩展来实现这个重复：e3扩展为eee；e3,5扩展为eeee?e?,e3,扩展成eee+。匹配子表达式提取。正则表达式是用来分离和解析字符串的，如果能够找到输入字符串中匹配子表达式的那部分，这样会是十分有用的。像这样的正则表达式(0-9+-0-9+-0-9+)(0-9+：0-9+)匹配字符串(可能是日期或者时间)，很多正则表达式引擎可以利用括号来进行文本匹配。比如，用perl写的一个匹配：if(/(0-9+-0-9+-0-9+)(0-9+：0-9+)/)printdate：,time：n；子匹配的边界提取这个问题并没有被计算机科学理论研究者所重视，同时这个问题也是使用递归回溯的最强烈的原因。然而，Thompson类型的算法可以被改进以记录子匹配的边界同时也不需要放弃性能。第八版的unix regexp库已经早在1985年实现了这个算法，正如下面所解释的，这个特性并没有被广泛的使用或者被人注意到。无锚点匹配。这个文章假设正则表达式与整个字符串匹配。实际中，人们只是希望能够找到输入的一个子字符串与正则表达式匹配。传统的unix工具总是返回输入中的最左最长匹配。对于e的无锚点匹配实际上可以看成匹配子表达式提取的特殊情况：就等价于搜索.*(e).*同时要求第一个.*的匹配要尽可能的短。非贪婪操作符。在传统的unix正则表达式里，重复操作符?,*,and+定义成匹配尽可能长的字符串。比如用(.+)(.+)匹配abcd，第一个(.+)匹配abc，第二个匹配d。这些操作符被称为贪婪的。perl引入了?,*?,and+?作为它们对应的非贪婪版本，可以匹配尽可能少的字符：比如(.+?)(.+?)匹配abcd，第一个(.+?)匹配a，第二个匹配bcd。通过定义，操作符是否是贪婪的并不影响正则表达式与字符串是否匹配，它仅仅影响到匹配的边界。回溯算法可以产生非贪婪操作符的一个简单实现：总是首先尝试较短的那个匹配。比如在一个标准回溯实现里，e?首先尝试使用e然后尝试不使用它；e?采用另一个顺序。Thompson算法的子匹配变种可以简单的应用到非贪婪操作符。断言。传统的正则表达式元字符和$可以看做是它们旁边的文本的断言：表示前一个字符是换行(或者是字符串的开始)，$表示下一个字符是换行(或者是字符串的末尾)。perl增加了更多的断言，比如字边界b，表示前一个字符是字母或者数字，但是下一个不是。perl也将这个想法继续扩展，叫做前向断言：(?=re)表明当前输入位置后面的文本匹配re，但是实际上并不将输入位置前移；(?！re)与之类似，但是它是用来说明文本不匹配re的。前向断言(?=re)and(?！re)类似，但是它们是用来表示与当前输入位置之前的文本的匹配关系的。简单断言，比如,$,andb，很容易在NFA里表示，对于前向匹配只需要延续一个字节即可。一般化的断言虽然很难表示，但是通过一定的方法也可以编码在NFA里。前向引用。正如前面提到的，没有人知道怎么有效的实现带有前向引用的正则表达式，也没有人可以证明它是不可能的(特别的，这个问题是NP完全的，意味着如果有人发现了一个有效的实现，那么这将是计算机科学的一个大新，并可以获得百万奖励)。对于前向引用来说，最简单也是最有效的策略就是awk和egrep采用的，就是不实现它们。但是这个策略也不再实用了，在某些应用中用户已经开始依赖于前向引用，而且前向引用也是posix标准正则表达式的一部分。即使如此，我们也可以对大部分正则表达式使用Thompson的NFA模拟，只在需要时再使用回溯。一个特殊的聪明的实现可以将它们结合，只有使用前向引用时再使用回溯。记忆化回溯。perl的策略使用了记忆化来避免指数级的回溯。至少理论上，应该让perl的正则表达式表现地更像NFA，而不是回溯。记忆化并没有完全解决这个问题，记忆化本身需要等价于文本串长度(可能是正则串的数倍)的内存空间。记忆化也不能减少递归回溯需要的栈空间，这个大小与文本串大小是线性的。匹配一个长字符串就可能导致回溯实现栈空间溢出。$perl-e(ax 100000)=/(ab?)*$/；Segmentation fault(core dumped)字符集。现代正则表达式实现比较处理大量的非ansii字符集，比如unicode。Plan 9的正则表达式库包含了nicode，每次运行NFA通过一个unicode字符作为输入字符。库将NFA的运行与输入的解码分离，这样相同的正则表达式匹配码即可以用于utf-8也可以用于宽字符输入。历史及引用Michael Rabin and Dana Scott在1959年的论文里7介绍了非确定性有限自动机和非确定性的概念，指出NFAs可以使用DFAs模拟，每个DFA状态应一系列的NFA状态集。(由于他们论文中提出的非确定性的概念，获得了1976年的图灵奖)。R.McNaughton and H.Yamada4and Ken Thompson9给出了正则表达式向NFAs转换的第一个实现，即使那篇文章中并没有提到NFA的概念。McNaughton and Yamada的实现创建了DFA，Thompson的实现使用了IBM 7094机器码。正则表达式向NFA转换的区别仅仅在如何进行编码。上面使用的方法，在编码时使用了显示的节点和未标注指针。一个改进方法，也是最常用的是由McNaughton and Yamada发明的，可以避免未标号指针，不允许NFA具有多个具有相同标注的输出指针。McIlroy在Haskell里给出了这种方法的部分实现。Thompson的正则表达式为运行在IBM7094的CTSS操作系统上的QED编辑器实现的。这个编辑器的还可以在CTSS的源代码里找到。L.Peter Deutsch and Butler Lampson开发了第一个QED，但是Thompson的重新实现是第一个采用正则表达式的版本。Dennis Ritchie，已经将QED的历史进行了文档化。Thompson的论文标志这正则表达式实现的一个新的开始。他并没有使用它的算法实现文本编辑器ed(出现在1971UNIX第一版上),或者是它的后续grep。相反，这些unix工具使用了递归回溯！使用回溯是合理的，因为正则表达式的符号那个时候还十分有限：它忽略了分组括号以及|,?,+运算符。Al Aho的egrep是第一个提供了完整的正则表达式符号的unix工具，采用了预先计算好的DFA。在1985年的第8版里，egrep开始即时计算DFA，就像上面给出的那个实现一样。在编写文本编辑器sam的时候，Rob Pike写了一个新的正则表达式的实现。Pike的实现将子匹配加入到了一个有效的NFA模拟中，但是并没有被广泛应用。Pike本身也没有意识到他的技术有什么新颖的地方。Henry Spencer使用回溯重新实现了这个功能，并把它发布到公众面前。于是它很快变得流行起来，并且被Perl pcre python这些采用。(Spencer知道这个过程可能变得很慢，但是他并不知道还有一个效率更高的算法存在，他甚至在文档中提出警告Many users have found the speed perfectly adequate,although replacing the insides of egrep with this code would be amistake.)Pike的正则表达式实现，被扩展到可以支持unicode，并且可以与sam一起免费获得，但是那些效率特别高的正则匹配搜索算法却逐渐被忘记。Ville Laurikari在1999年独立发现了Pike的算法，并发展出了一个理论基础。最后，任何关于正则表达式的讨论如果不提及Jeffrey Friedl的精通正则表达式都将是不完整的，或许这本书是今天的程序员最流行的参考书。Friedl的书主要是用来教程序员如何更好地使用今天的正则表达式实现，而不是如何更好的实现它们。里面只有一小部分文本用来介绍实现，并且使得人们产生了这样一种观点，好像正则表达式只有递归回溯一种实现。很明显，Friedl也不理解或者重视底层实现。摘要通过已经出现数十年的基于有限自动机的技术，正则表达式匹配可以很简单，很快速。与此相比，Perl,PCRE,Python,Ruby,Java,以及其他很多语言的正则表达式实现却基于递归回溯，虽然很简单，但也会很低效。不考虑前向引用的话，那些由慢的回溯实现提供的特点完全可以由基于自动机的实现更快更一致的提供。致谢Lee Feigenbaum,James Grimmelmann,Alex Healy,William Josephson,and Arnold Robbins阅读了这篇文章的手稿，并提出了很多建议。Rob Pike提供了一些关于他的正则表达式实现的历史。在这里一并表示感谢。参考文献：1L.Peter Deu