深入正则表达式原理(二)

前两天一直心里不好，没有把这个主题写完，现在接着来补上：

       一、上篇中说到NFA正则引擎的表达式主导：

                  (1).  为什么说NFA是表达式主导，请看下面的例子：

                           用 to(nite | knight | night) 来匹配 " I am going to seeing film tonight,could you go with me? "这段文本。

                           NFA引擎会从文本中的第一个字母I开始匹配，它会把匹配表达式全部走一遍，然后发现没有成功，则正则表达式引擎会驱动向下走，到达第二个字符-空格，发现整个匹配表达式也没有匹配成功，则继续，然后到a，依次类推，直到“tonight"这个to，成功匹配后，转向文本中tonight中的n，发现（nite）符合，这它不会再向下匹配，返回成功，然后转向tonight中的i，发现也能成功，则它也不会继续向下匹配，然后转向文本tonight中的g，到正则表达式中的（nite）发现t不匹配，则此时正则引擎会回退从knight单词的k字母进行匹配，发现也不符合，则回退，再从night单词中的n开始匹配，发现符合，则继续匹配，然后到i，发现匹配再到g，依次类推直到匹配成功。最后返回匹配成功。

                             你明白没？其实表达式的控制权在不同的元素字母之间转换，所以我们称之为“表达式主导”                 

                  (2).     DFA引擎的文本主导：

                             继续我们的这个例子。

                             但我们进行I字母的匹配时不成功，就不说了，一直到tonight单词是，前面的to比配成功后，当进行to(nite | knight | night)中的n进行匹配时，DFA会同时向三个选项发出匹配请求，有（nite和night）两个符合，（发现没是同时发出请求）则就会抛弃knight选项，以后就不会再进行匹配，然后是i字母的匹配，发现nite和night都符合，则继续，到tonight中的g，在DFA中同时再向nite和night发出匹配请求，发现只有night符合，就会抛弃nite这个选项，然后继续向下匹配。知道成功。发现没，这种方法少了NFA中的很多的回退，所以效率高。。。。



     二、有现在主流的语言都是用的是NFA正则引擎，那我们就来重点介绍它的实现机制：

              要想了解其中的原理，我们先了解几个概念：回溯、备用状态

             专业术语是回溯其实在我的理解就是回退。NFA引擎最很重要的性质是：她会一次处理各个表达式，或组成元素，遇到需要在两个可能成功中进行选择的时候，她会选择其一，同时记住另一个，以备稍后的可能的需要。

             并且重要的是：不论选择那一种途径，如果它能匹配成功，而且正则表达式的余下部分也能匹配成功，此时才宣告最终匹配成功，或许你觉得我这个说的是废话。但你请看下面的，如果正则表达式中余下的部分最终匹配失败，引擎会知道需要回溯到之前作出选择的地方，选择其他的备用分支继续尝试。这样最终表达式所有的可能途径知道最终的成功或失败。回溯常和备用状态联系起来分析，那就来说一下，什么叫备用状态。

              按我的理解是：大家应该都知道迷宫，走迷宫最常用的方法就是做记号，此刻我们假如用石头做记号，每当我们遇到十字路口是，我们就丢下一块石头，来标记我们所选择的路口，但我们发现不此路不通时，我们就进行回溯，回退到离我们最近的哪一个十字路口，然后重新选择我们的方向，这种方法是我们最常用的。我要说的是，正则表达式中的备用状态就是那个我们在每个十字路口的石头。其实我觉得这就算递归中的回溯，要是你理解了递归，这个应该不难理解。NFA中的LIFO(后进先出)的原则我觉就是那个迷宫此路不通的记号石头就是我们最好的LIFO例子。

               整个NFA中的优化其实就是这个回溯原则和greedy原则(上一篇中讲到的)，进行合理的优化和匹配。

      三、忽略优先量词（*?、+?、??、{min、max}?、）

              针对NFA的greedy原则，正则表达式有了忽略优先量词，这很大程度上解决了，很多由于greedy原则带来的麻烦和效率的问题。她只会匹配符合要求的最小的选择。如：

                  若用 <B>.*</B> 来匹配<B>I</B>and<B>you</B>are chinese,we are very happy to be chinese.

                                     结果会是：<B>I</B>and<B>you</B>

                   但用<B>.*?</B>匹配 则结果是：<B>I</B>

      四：固化分组：(?>)

                  使用固化分组，这会让引擎不记住备用状态，这又是能很好的提高正则表达式的效率。这也是优化正则表达式的常用方式。如下面的例子：

                  用 i.*! 来匹配 iHello!   在没有用固化分组时，是可以匹配成功的。

                 若用固化分组，i(?>.*)! 来匹配 iHello! 则匹配不成功，由于*是贪婪的她会一直匹配到最后，又由于固化分组了.*,她不会再吐出字符让后面的!来匹配。所以匹配失败。

评论

1 楼 xiaoqing20 2010-09-13