欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

正则表达式——详细讲解平衡组

程序员文章站 2022-06-23 11:32:28
这篇文章适合你吗? 要读懂这篇文章的精髓,你最好要有一点正则匹配原理的基础。比如".*?"匹配文本内容"asp163",稍懂正则表达式的人都知道可以匹配,但是你知...

这篇文章适合你吗?

要读懂这篇文章的精髓,你最好要有一点正则匹配原理的基础。比如".*?"匹配文本内容"asp163",稍懂正则表达式的人都知道可以匹配,但是你知道他的匹配过程吗?如果你不太清楚,那么下面的内容,对你来说可能不太适合,或许,看的太吃力且无法领悟平衡组的用法。因此,我建议你先了解正则表达式nfa引擎的匹配原理。想要整理一份易懂易描述的话,的确要费些时间,但不知道这篇内容会不会达到我预期的效果。慢慢完善吧~(注:这是我2010年写的,现在拿过来,有时间将自己做为读者来看本篇文章,修改有问题的地方,并增加些实例,尽量做到通俗易懂。)

一般正则教程中对平衡组的介绍

如果想要匹配可嵌套的层次性结构的话,就得使用平衡组了。举个例子吧,如何把“xx <aa <bbb> <bbb> aa> yy”这样的字符串里,最长的尖括号内的内容捕获出来?

这里需要用到以下的语法构造:
(?<group>) 把捕获的内容命名为group,并压入堆栈
(?<-group>) 从堆栈上弹出最后压入堆栈的名为group的捕获内容,如果堆栈本来为空,则本分组的匹配失败
(?(group)yes|no) 如果堆栈上存在以名为group的捕获内容的话,继续匹配yes部分的表达式,否则继续匹配no部分
(?!) 顺序否定环视,由于没有后缀表达式,试图匹配总是失败

如果你不是一个程序员(或者你是一个对堆栈的概念不熟的程序员),你就这样理解上面的三种语法吧:第一个就是在黑板上写一个(或再写一个)"group",第二个就是从黑板上擦掉一个"group",第三个就是看黑板上写的还有没有"group",如果有就继续匹配yes部分,否则就匹配no部分。
我们需要做的是每碰到了左括号,就在黑板上写一个"group",每碰到一个右括号,就擦掉一个,到了最后就看看黑板上还有没有-如果有那就证明左括号比右括号多,那匹配就应该失败(为了能看得更清楚一点,我用了(?'group')的语法):

<         #最外层的左括号
 [^<>]*     #最外层的左括号后面的不是括号的内容
 (
  (
   (?'open'<) #碰到了左括号,在黑板上写一个"open"
   [^<>>]*   #匹配左括号后面的不是括号的内容
  )+
  (
   (?'-open'>) #碰到了右括号,擦掉一个"open"
   [^<>]*   #匹配右括号后面不是括号的内容
  )+
 )*
 (?(open)(?!))  #在遇到最外层的右括号前面,判断黑板上还有没有没擦掉的"open";如果有,则匹配失败
>         #最外层的右括号

我为什么写这篇文章

看了上面的介绍,你明白了吗?在我未理解正则表达式匹配原理之前,看上面对于平衡组的介绍,似懂非懂,且只能当做模板记住,而不能灵活运用。因此查阅大量有关正则方面的资料,这里尤其感谢lxcnn的技术文档及《精通正则表达式》这本书,让我对正则表达式有了更深入、更系统的理解,因此,在它们的基础之上,我就结合自己的学习经历做个小结,一来做为学习笔记存档,另外,如果能解决你的疑惑,也是件让人高兴的事。
我先暂不分析上面的代码,先讲解一下关于平衡组相关的概念及知识。
下面表达式匹配测试工具为:expresso,本站也提供它的完美破解版下载。

平衡组的概念及作用

平衡组,故名思义,平衡即对称,主要是结合几种正则语法规则,提供对配对出现的嵌套结构的匹配。平衡组有狭义与广义两种定义,狭义平衡组指(?expression) 语法,而广义平衡组并不是固定的语法规则,而是几种语法规则的综合运用,我们平时所说的平衡组通常指的是广义平衡组。本文中如无特殊说明,平衡组这种简写指的是广义平衡组。
平衡组的匹配原理
平衡组的匹配原理可以用堆栈来解释,先举个例子,再根据例子进行解释。

源字符串:a+(b*(c+d))/e+f-(g/(h-i))*j
正则表达式:((?<open>\()|(?<−open>)|[^()])*(?(open)(?!))\)
需求说明:匹配成对出现的()中的内容
输出:(b*(c+d)) 和 (g/(h-i))
我将上面正则表达式代码分行写,并加上注释,这样看起来有层次,而且方便

 \(        #普通字符“(”
  (       #分组构造,用来限定量词“*”修饰范围
   (?<open>\() #命名捕获组,遇到开括弧“open”计数加1
   |      #分支结构
   (?<-open>\)) #狭义平衡组,遇到闭括弧“open”计数减1
   |      #分支结构
   [^()]+    #非括弧的其它任意字符
  )*       #以上子串出现0次或任意多次
  (?(open)(?!)) #判断是否还有“open”,有则说明不配对,什么都不匹配
 \)       #普通闭括弧

对于一个嵌套结构而言,开始和结束标记都是确定的,对于本例开始为“(”,结束为“)”,那么接下来就是考察中间的结构,中间的字符可以划分为三类,一类是“(”,一类是“)”,其余的就是除这两个字符以外的任意字符。

那么平衡组的匹配原理就是这样的

1、先找到第一个“(”,作为匹配的开始。即上面的第1行,匹配了:a+(b*(c+d))/e+f-(g/(h-i))*j (红色显示部分)

2、在第1步以后,每匹配到一个“(”,就入栈一个open捕获组,计数加1

3、在第1步以后,每匹配到一个“)”,就出栈最近入栈的open捕获组,计数减1

也就是讲,上面的第一行正则“\(”匹配了:a+(b*(c+d))/e+f-(g/(h-i))*j (红色显示部分)
然后,匹配到c前面的“(”,此时,计数加1;继续匹配,匹配到d后面的“)”,计算减1;——注意喽:此时堆栈中的计数是0,正则还是会向前继续匹配的,但是,如果匹配到“)”的话,比如,这个例子中d))(红色显示的括号)——引擎此时将控制权交给(?(open)(?!)),判断堆栈中是否为0,如果为0,则执行匹配“no”分支,由于这个条件判断结构中没有“no”分支,所以什么都不做,把控制权交给接下来的“\)”
这个正则表达式“\)”可匹配接下来的),即b))(红色显示的括号)

4、后面的 (?(open)(?!))用来保证堆栈中open捕获组计数是否为0,也就是“(”和“)”是配对出现的

5、最后的“)”,作为匹配的结束

匹配过程

首先匹配第一个“(”,然后一直匹配,直到出现以下两种情况之一时,把控制权交给(?(open)(?!)):
a)堆栈中open计数已为0,此时再遇到“)”
b)匹配到字符串结束符
这时控制权交给(?(open)(?!)),判断open是否有匹配,由于此时计数为0,没有匹配,那么就匹配“no”分支,由于这个条件判断结构中没有“no”分支,所以什么都不做,把控制权交给接下来的“\)”
如果上面遇到的是情况a),那么此时“\)”可以匹配接下来的“)”,匹配成功;
如果上面遇到的是情况b),那么此时会进行回溯,直到“\)”匹配成功为止,否则报告整个表达式匹配失败。
由于.net中的狭义平衡组“(?<close-open>expression)”结构,可以动态的对堆栈中捕获组进行计数,匹配到一个开始标记,入栈,计数加1,匹配到一个结束标记,出栈,计数减1,最后再判断堆栈中是否还有open,有则说明开始和结束标记不配对出现,不匹配,进行回溯或报告匹配失败;如果没有,则说明开始和结束标记配对出现,继续进行后面子表达式的匹配。
需要对“(?!)”进行一下说明,它属于顺序否定环视,完整的语法是“(?!expression)”。由于这里的“expression”不存在,表示这里不是一个位置,所以试图尝试匹配总是失败的,作用就是在open不配对出现时,报告匹配失败。

下面在看个例子:

<table>
<tr>
<td id="td1"> </td>
<td id="td2">
<table>
<tr>
<td>snhame</td>
<td>f</td>
</tr>
</table>
</td>
<td></td>
</tr> </table>

以上为部分的html代码.现在我们的问题是要提取出其<td id="td2">的<td>标签并将其删除掉,以往我们惯用的方法都是直接去取,像<td\s*id="td2">[\s\s]+?\</td>,不过问题出来了,我们提取到的不是我们想要的内容,而是

<td id="td2">
<table>
<tr>
<td>snhame</td>

原因也很简单,它和离他最近的</td>标签匹配上了,不过它不知道这个标签不是它的-_-,是不是就是?符号的原因呢,我们去掉让他无限制贪婪,可这下问题更大了,什么乱七八糟的东东它都匹配到了

<td id="td2">
<table>
<tr>
<td>snhame</td>
<td>f</td>
</tr>
</td>
<td></td>

这个结果也不是我们想要的。那么我就用“平衡组”来解决吧。

<td\s*id="td2"[^>]*>((?<mm><td[^>]*>)+|(?<-mm></td>)|[\s\s])*?(?(mm)(?!))</td>

匹配的结果是

<td id="td2">
<table>
<tr>
<td>snhame</td>
<td>f</td>
</tr>
</table>
</td>
<td></td>

这正是我们想要的
注意,我开始写成这样的方式

<td\s*id="td2"[^>]*>((?<mm><td[^>]*>)+|(?<-mm></td>)|[\s\s])*(?(mm)(?!))</td> 

匹配的结果是

<td id="td2">
<table>
<tr>
<td>snhame</td>
<td>f</td>
</tr>
</table>
</td>
<td></td>

一个问题
以下代码只是做为一个问题探讨
文本内容:e+f(-(g/(h-i))*j

正则表达式:

\(
 (
  (?<mm>\()
  |
  (?<-mm>\))
  |
  .
 )*?
 (?(mm)(?!))
\)

匹配的结果是:(-(g/(h-i))