《正则表达式匹配》word版

《《正则表达式匹配》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、正则表达式匹配正则表达式匹配2010-12-0921：21正则表达式匹配也可以简单快速(下：实现部分)技术专题2009-10-0400：29：16阅读706实现Thompson在1968年的论文里对多状态模拟策略进行了介绍。在他的文章里，NFA的状态是使用机器码序列来表示的，可能状态列表仅仅是一系列的函数调用指令。实际上，Thompson将正则表达式编译成了机器码。四十年后，计算机已经变得很快了，所以机器码的这种方法变得不太必要了。下面的章节里介绍一种使用标准c的实现。完整的源代码(少于400行)和测试脚本在这里(。实现：编译成NFA第一步

2、就是把正则表达式编译成等价的NFA。在我们的c程序里，我们使用一个带指针的结构体来表示NFA。structStateintc；State*out；State*out1；intlastlist；}；每个状态可以用来代表下面的三个NFA片段，取决于c的值(lastlist是执行时使用的，下面还会解释)根据Thomspon的论文，编译器从一个正则表达式的前缀形式开始构建NFA，对于连接通过增加一个"."来将该运算以运算符的形式显示化。通过一个独立函数re2post将中缀正则表达式比如"a(bb)+a"转换成后缀表达式"abb.+.a."。(一个实

3、际的实现并不需要用"."来代替连接字符。一个实际的实现也可能解析的同时构建NFA而不是构建一个显示的后缀表达式。然而，后缀版本更加方便也更接近Thompson的论文)当编译器扫描后缀表达式的时候，它用过一个栈来维护一个已经计算好的NFA片段。LiteralspushnewNFAfragmentsontothestack,whileoperatorspopfragmentsoffthestackandthenpushanewfragment.比如，编译好abb.+.a.中的abb之后，栈里包含a,b和b的NFA片段。然后编译".",这时需要将

4、两个b的NFA片段从栈里pop出来，然后将bb.的NFA片段压入栈。每个NFA片段是由开始状态和输出指针组成的：structFragState*start；Ptrlist*out；}；对于片段来说，start是开始节点，out是一系列指向未链接到任何东西的状态指针的列表的指针。NFA片段里存在一些悬空指针。下面这些辅助函数可以帮助控制指针链表：Ptrlist*list1(State*outp)；Ptrlist*append(Ptrlist*l1,Ptrlist*l2)；voidpatch(Ptrlist*l,State*s)；list1创建

5、一个新指针列表包括outp指针的。append将两个指针列表连接起来，并返回结果。patch将list1中的悬空指针连接使它们指向状态s：对于l里的每个指针outp,它设置*outp=s。给定上面这些基础内容及片段栈，编译过程实际上是一个在后缀表达式串上的简单循环。处理到最后只剩下一个单片段：添加一个匹配状态就完成了NFA的构建。State*post2nfa(char*postfix)char*p；Fragstack[1000],*stackp,e1,e2,e；State*s；#definepush(s)*stackp++=s#define

6、pop()*--stackpstackp=stack；for(p=postfix；*p；p++){switch(*p){/*compilationcases,describedbelow*/e=pop()；patch(e.out,matchstate)；returne.start；下面这些具体的编译实例，模拟了上面所描述的那些转换步骤。文本字符：default：s=state(*p,NULL,NULL)；push(frag(s,list1(&s-out))；break；连接：case'.'：e2=pop()；e1=pop()；patch(e

7、1.out,e2.start)；push(frag(e1.start,e2.out))；break；选择：case'

8、'：e2=pop()；e1=pop()；s=state(Split,e1.start,e2.start)；push(frag(s,append(e1.out,e2.out)))；break；Zeroorone：case'?'：e=pop()；s=state(Split,e.start,NULL)；push(frag(s,append(e.out,list1(&s-out1))))；break；Zeroormore：case'

9、*'：e=pop()；s=state(Split,e.start,NULL)；patch(e.out,s)；push(frag(s,list1(&s-out1)))；break；