现在的位置: 首页 > 综合 > 正文

正则匹配原理之——逆序环视深入

2012年10月18日 ⁄ 综合 ⁄ 共 2986字 ⁄ 字号 评论关闭

:部分内容有待进一步研究和修正,因为最近工作太忙,暂时抽不出时间来,未研究过的可以跳过这一篇,想研究的不要被我的思路所左右了,有研究清楚的还请指正

1        问题引出

前几天在CSDN论坛遇到这样一个问题:

var str="8912341253789";

需要将这个字符串中的重复的数字给去掉,也就是结果89123457

首先需要说明的是,这种需求并不适合用正则来实现,至少,正则不是最好的实现方式。

这个问题本身不是本文讨论的重点,本文所要讨论的,主要是由这一问题的解决方案而引出的另一个正则匹配原理问题。

先看一下针对这一问题本身给出的解决方案。

string str = "8912341253789";

Regex reg = new Regex(@"((\d)\d*?)\2");

while (str != (str = reg.Replace(str, "$1"))) { }

richTextBox2.Text = str;

/*--------输出--------

89123457

*/

基于此有朋友提出另一个疑问,为什么使用下面的正则没有效果

(?<=(?<value>\d).*?)\k<value>

由此也引出本文所要讨论的逆序环视更深入的一些细节,涉及到逆序环视的匹配原理和匹配过程。前面的两篇博客中虽然也有介绍,但还不够深入,参考 正则基础之——环视 正则应用之——逆序环视探索 。本文将以逆序环视和反向引用结合这种复杂应用场景,对逆序环视进行深入探讨。

先把问题简化和抽象一下,上面的正则中用到了命名捕获组和命名捕捉组的反向引用,这在一定程度上增加了问题的复杂度,写成普通捕获组,并且用“\d”代替范围过大的“.”,如下

(?<=(\d)\d*?)\1

需要匹配的字符串,抽象一下,取两种典型字符串如下。

源字符串一:878

源字符串二:9878

与上面正则表达式类似,正则表达式相应的也有四种形式

正则表达式一:(?<=(\d)\d*)\1

正则表达式二:(?<=(\d)\d*?)\1

正则表达式三:(?<=(\d))\d*\1

正则表达式四:(?<=(\d))\d*?\1

先看一下匹配结果:

string[] source = new string[] {"878", "9878" };

List<Regex> regs = new List<Regex>();

regs.Add(new Regex(@"(?<=(\d)\d*)\1"));

regs.Add(new Regex(@"(?<=(\d)\d*?)\1"));

regs.Add(new Regex(@"(?<=(\d))\d*\1"));

regs.Add(new Regex(@"(?<=(\d))\d*?\1"));

foreach (string s in source)

{

     foreach (Regex r in regs)

     {

          richTextBox2.Text += "源字符串: " + s.PadRight(8, ' ');

          richTextBox2.Text += "正则表达式: " + r.ToString().PadRight(18, ' ');

          richTextBox2.Text += "匹配结果: " + r.Match(s).Value + "\n------------------------\n";

     }

     richTextBox2.Text += "------------------------\n";

}

/*--------输出--------

源字符串: 878     正则表达式: (?<=(\d)\d*)\1    匹配结果: 8

------------------------

源字符串: 878     正则表达式: (?<=(\d)\d*?)\1   匹配结果:

------------------------

源字符串: 878     正则表达式: (?<=(\d))\d*\1    匹配结果: 78

------------------------

源字符串: 878     正则表达式: (?<=(\d))\d*?\1   匹配结果: 78

------------------------

------------------------

源字符串: 9878    正则表达式: (?<=(\d)\d*)\1    匹配结果:

------------------------

源字符串: 9878    正则表达式: (?<=(\d)\d*?)\1   匹配结果:

------------------------

源字符串: 9878    正则表达式: (?<=(\d))\d*\1    匹配结果: 78

------------------------

源字符串: 9878    正则表达式: (?<=(\d))\d*?\1   匹配结果: 78

------------------------

------------------------

*/

这个结果也许会出乎很多人的意料之外,刚开始接触这个问题时,我也一样感到迷惑,放了两天后,才灵机一触,想通了问题的关键所在,下面将展开讨论。

在此之前,可能还需要做两点说明:

1、  下面讨论的话题已经与本文开始提到的问题没有多大关联了,最初的问题主要是为了引出本文的话题,问题本身不在讨论范围之内,而本文也主要是纯理论的探讨。

2、  本文适合有一定正则基础的读者。如果您对上面几个正则的匹配结果和匹配过程感到费解,没关系,下面就将为您解惑;但是如果您对上面几个正则中元字符和语法代表的意义都不清楚的话,还是先从基础看起吧。

2       逆序环视匹配原理深入

正则表达式一:(?<=(\d)\d*)\1

正则表达式二:(?<=(\d)\d*?)\1

正则表达式三:(?<=(\d))\d*\1

正则表达式四:(?<=(\d))\d*?\1

上面的几个正则表达式,可以最终抽象为“(?<=SubExp1)SubExp2”这样的表达式,在做逆序环视原理分析时,根据“SubExp1”的特点,可以归纳为三类:

1、  逆序环视中的子表达式“SubExp1”长度固定,正则表达式三和四属于这一类,当然,这一类里是包括“?”这一量词的,但也仅限于这一个量词。

2、  逆序环视中的子表达式“SubExp1”长度不固定,其中包含忽略优先量词,如“*?”、“+?”、“{m,}?”等,也就是通常所说的非贪婪模式,正则表达式二属于这一类。

3、  逆序环视中的子表达式“SubExp1”长度不固定,其中包含匹配优先量词,“*”、“+”、“{m,}”等,也就是通常所说的贪婪模式,正则表达式一属于这一类。

下面针对这三类正则表达式进行匹配过程的分析。

2.1     固定长度子表达式匹配过程分析

2.1.1  源字符串一 + 正则表达式三匹配过程

源字符串一:878

正则表达式三:(?<=(\d))\d*\1

首先在位置0处开始尝试匹配,由“(?<=(\d))”取得控制权,长度固定,只有一位,由位置0处向左查找一位,失败,“(?<=(\d))”匹配失败,导致第一轮匹配尝试失败。

正则引擎传动装置向前传动,由位置1处尝试匹配,控制权交给“(?<=(\d))”,向左查找一位,接着将控制权交给“(\d)”,更进一步的将控制权交给“\d”。“\d”取得控制权后,向右尝试匹配,匹配“8”成功,此时“(?<=(\d))

抱歉!评论已关闭.