详解平衡组

在之前回顾正则表达式30分钟入门这篇文章的时候，发现最后一节的平衡组理解起来有些困难。于是，查找了一些资料，记录一下。

NFA引擎匹配原理

正则表达式引擎

正则表达式引擎大体可分为不同的两类：DEA和NFA，而NFA又基本上可以分为传统型NFA和POSIX NFA。

DFA: Deterministic finite automaton 确定型有穷自动机

NFA: Non-deterministic finite automaton 非确定型有穷自动机

DFA引擎因为不需要回溯，所以匹配快，但不支持捕获组，所以也就不支持反向引用和$number匹配，目前使用DFA引擎的语言和工具主要有awk、egrep和lex。

POSIX NFA主要指符合POSIX标准的引擎，它的特点主要是提供longest-leftmost匹配，也就是在找到最左侧最长匹配之前，它将继续回溯。同DFA一样，非贪婪模式或者说忽略优先量词对于POSIX NFA同样是没有意义的。

大多数语言和工具使用的是传统型的NFA引擎，它有一些DFA不支持的属性：

捕获组、反向引用和$number引用方式
环视(Lookaround，(?<=exp)、(?<!exp)、(?=exp)、(?!exp))，或者有的有文章叫做预搜索
忽略优化量词（??、*?、+?、{m,n}?、{m,}?），或者有的文章叫做非贪婪模式，固化分组(?<exp)

预备知识

字符串组成

对于”abc”而言，包括3个字符和4个位置。

占有字符和零宽度

正则表达式匹配过程中，如果子表达式匹配到的是字符内容，而非位置，并被保存到最终的匹配结果中，那么就认为这个子表达式是占有字符的；如果子表达式匹配的仅仅是位置，或者匹配的内容并不保存到最终的匹配结果中，那么就认为这个子表达式是零宽度的。

占有字符是互斥的，零宽度是非互斥的。也就是一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配。

控制权和传动

正则的匹配过程，通常情况下都是由一个子表达式(可能是一个普通的字符、元字符或元字符序列组成)取得控制权，从字符的某一位置开始尝试匹配，一个子表达式开始尝试匹配的位置，是从前一个子表达式匹配成功的结束位置开始的。如正则表达式：

(子表达式1)(子表达式2)

假设(子表达式1)为零宽度表达式，由于它匹配开始和结束的位置是同一个，如位置0，那么(子表达式2)是从位置0开始尝试匹配的。

假设(子表达式1)为占有字符的表达式，由于它匹配开始和结束的位置不是同一个，如匹配成功开始于位置0，结束于位子2，那么(子表达式2)是从位置2开始尝试匹配的。

而对于整个表达式来说，通常是由字符串位置0开始尝试匹配的。如果在位置0开始的尝试，匹配到字符长某一位置时整个表达式匹配失败，那么引擎会使正则想前传动，整个表达式从位置1开始重新尝试匹配，依此类推，直到报告匹配成功或尝试到最后一个位置报告匹配失败。

回溯和备选状态

由上文可以知道，NFA引擎是用表达式去匹配文本，而表达式又有若干分支和范围，一个分支或者范围匹配失败并不意味着最终匹配失败，正则引擎会去尝试下一个分支或者范围。

正是因为这样的机制，引申出了NFA引擎的核心特点——回溯。

首先，我们要区分备选状态和回溯。

什么是备选状态？就是说这一个分支不行，我就换一个分支，这个范围不行，那我就换一个范围。正则表达式中可以商榷的部分就叫做备选状态。

备选状态可以实现模糊匹配，是正则表达式能力的一方面。

回溯可不是个好东西。想象一下，面前有两条路，你选择了一条，走到尽头发现是条死路，你只好原路返回尝试另一条路。这个原路返回的过程就叫回溯，它在正则中的含义是吐出已经匹配过的文本。

我们来看两个例子：

'abbbc'.match(/ab{1,3}c/);
// ["abbbc", index: 0, input: "abbbc", groups: undefined]
'abc'.match(/ab{1,3}c/);
// ["abc", index: 0, input: "abc", groups: undefined]

第一个例子，第一次a匹配a成功，接着碰到贪婪匹配，不巧正好是三个b贪婪得逞，最后用c匹配c成功。

正则	文本
/a/	a
/ab{1,3}/	ab
/ab{1,3}/	abb
/ab{1,3}/	abbb
/ab{1,3}c/	abbbc

第二个例子的区别在于文本只有一个b。所以表达式在匹配第一个b成功后继续尝试匹配b，然而它见到的只有c。不得已将c吐出来，委屈一下，毕竟贪婪匹配也只是尽量匹配更多嘛，还是要臣服于匹配成功这个目标。最后不负众望用c匹配c成功。在成功匹配第一个b之后，继续尝试匹配b，用b匹配c失败，会发生一次控制权的转让，用c去匹配c。

正则	文本
/a/	a
/ab{1,3}/	ab
/ab{1,3}/	abc
/ab{1,3}/	ab
/ab{1,3}c/	abc

这个例子没有发生回溯。

这是作者在文中提出的观点。在网上也有人认为这是发生了回溯的。就我个人而言，我是赞同作者的观点的。其实，是否发生回溯，可以通过是否是由于整体匹配失败而发生位置传动进行重新匹配来判断。如果是在某一次匹配过程中分支或范围匹配失败，需要转让控制权，这个过程是不叫回溯的。相反，由于整体匹配失败（分支和范围切换后依然失败）需要进行位置传动进行重新匹配，这个叫回溯。（个人理解）

下面看一个真正发生回溯的例子：

1 2	'ababc'.match(/ab{1,3}c/); // ["abc", index: 2, input: "ababc", groups: undefined]

匹配过程：

从位置0开始匹配，a匹配a成功
控制权转让给b{1,3},b{1,3}尝试匹配b，匹配成功
接着继续匹配b，遇到的是a，匹配失败
此时会回到备选状态，不再匹配b，将控制权转让给c，c匹配a，匹配失败，这个时候无备选状态，报告第一次匹配失败
进行回溯，发生位置传动，尝试在位置1重新开始匹配，用a匹配b，匹配失败
再次发生位置传动，从位置2开始匹配，a匹配a，匹配成功
转让控制权给b{1,3}，b{1,3}尝试匹配b，匹配成功
接着继续匹配b，遇到的是c，匹配失败
此时会回到备选状态，不再匹配b，将控制权转让给c，c匹配c，匹配成功

正则	文本
/a/	a
/ab{1,3}/	ab
/ab{1,3}/	aba
/ab{1,3}/	ab
/ab{1,3}c/	aba
/a/	ab(位置传动，尝试在位置1重新开始匹配)
/a/	aba(位置传动，尝试在位置2重新开始匹配)
/ab{1,3}/	abab
/ab{1,3}/	ababc
/ab{1,3}/	abab
/ab{1,3}c/	ababc

结合匹配过程看这个表格会更加清晰。

正则表达式匹配文本过程

基础匹配过程

源字符串：abc
正则表达式： abc
匹配过程：首先由正则表达式字符串’a’取得控制权，从位置0开始匹配，由’a’来匹配’a’，匹配成功；控制权交给正则表达式字符串’b’，由于’a’已经被正则表达式字符串’a’匹配，所以’b’从位置1开始尝试匹配，由’b’来匹配’b’，匹配成功；控制权交给正则表达式字符串’c’，由’c’来匹配’c’，匹配成功。

此时正则表达式匹配完成，报告匹配成功。匹配结果为’abc’，开始于位置0，结束于位置3。

含有匹配优先量词的匹配过程——匹配成功（一）

源字符串：abc
正则表达式：ab?c

量词“?”属于匹配优先量词，在可匹配可不匹配时，会先选择尝试匹配，只有这种选择会使整个表达式无法匹配成功时，才会尝试让出匹配到的内容。这里的量词“?”是用来修饰字符“b”的，所以“b?”是一个整体。
匹配过程：首先由正则表达式字符’a’取得控制权，从位置0开始匹配，由’a’来匹配’a’，匹配成功；控制权交给正则表达式字符’b?’，由于’?’是匹配优先量词，所以会尝试进行匹配，由’b?’来匹配’b’，同时记录一个备选状态，匹配成功；控制权交给’c’，由’c’来匹配’c’，匹配成功。记录的备选状态丢弃。

此时正则表达式匹配完成，报告匹配成功。匹配结果为‘abc’，开始位置为0，结束位置为3。

含有匹配优先量词的匹配过程——匹配成功（二）

源字符串：abc
正则表达式：ab?c
匹配过程：首先由正则表达式字符’a’取得控制权，从位置0开始匹配，由’a’来匹配’a’，匹配成功；控制权交给正则表达式字符’b?’，由于’?’是匹配优先量词，所以会尝试进行匹配，由’b?’来匹配’c’，同时记录一个备选状态，匹配失败；此时进行回溯，找到备选状态，’b?’忽略匹配，让出控制权；把控制权交给’c’，由’c’来匹配’c’，匹配成功。

此时正则表达式匹配完成，报告匹配成功。匹配结果为“ac”，开始位置为0，结束位置为2。其中“b?”不匹配任何内容。

含有匹配优先量词的匹配过程——匹配失败

源字符串：abd
正则表达式：ab?c
匹配过程：首先由正则表达式字符’a’取得控制权，从位置0开始匹配，由’a’来匹配’a’，匹配成功；控制权交给正则表达式字符’b?’，由于’?’是匹配优先量词，所以会尝试进行匹配，由’b?’来匹配’b’，同时记录一个备选状态，匹配成功；控制权交给’c’，由’c’来匹配’d’，匹配失败；此时找到记录的备选状态，’b?’忽略匹配，即’b?’不匹配’b’，让出控制权，把控制权交给’c’，由’c’来匹配’b’，匹配失败。此时第一轮匹配尝试失败。
正则引擎使正则向前传动，由位置1开始尝试匹配，由’a’来匹配’b’，匹配失败，没有备选状态，第二轮匹配失败。
继续向前传动，直到在位置3尝试匹配失败，匹配结束。此时报告整个表达式匹配失败。

含有忽略优先量词的匹配过程——匹配成功

源字符串：abc
正则表达式：ab??c
匹配过程：首先由字符’a’取得控制权，从位置0开始匹配，由’a’来匹配’a’，匹配成功；控制权交给字符’b??’，先尝试忽略匹配，即’b??’不进行匹配，同时记录一个备选状态，控制权交给’c’；由’c’来匹配’b’，匹配失败，此时进行回溯，找到记录的备选状态，’b??’尝试匹配，即’b??’来匹配’b’，匹配成功；把控制权交给’c’，由’c’来匹配’c’，匹配成功。

此时正则表达式匹配完成，报告匹配成功。匹配结果为“abc”，开始位置为0，结束位置为3。其中“b??”匹配字符“b”。

零宽度匹配过程

源字符串：a12
正则表达式：^(?=[a-z])[a-z0-9]+$
匹配过程：首先由元字符^取得控制权，从位置0开始匹配，^匹配的就是开始位置‘位置0’，匹配成功，控制权交给零宽断言(?=[a-z]);(?=[a-z])要求它所在位置的右侧必须是字母才能匹配成功，零宽度的子表达式之间是不互斥的，即同一个位置可以同时由多个零宽度子表达式匹配，所以它也是从位置0尝试进行匹配，位置0的右侧是字符“a”，符合要求，匹配成功，控制权交给[a-z0-9]+。因为(?=[a-z])只进行匹配，并不将匹配到的内容保存到最后结果，并且(?=[a-z])匹配成功的位置是位置0，所以[a-z0-9]+也是从位置0开始尝试匹配的，[a-z0-9]+首先尝试匹配“a”，匹配成功，继续尝试匹配，可以成功匹配接下来的“1”和“2”，此时已经匹配到位置3，位置3的右侧已没有字符，这时会把控制权交给“$”；元字符“$”从位置3开始尝试匹配，它匹配的是结束位置，也就是“位置3”，匹配成功。

此时正则表达式匹配完成，报告匹配成功。匹配结果为“a12”，开始位置为0，结束位置为3。

其中^匹配位置0，(?=[a-z])匹配位置0，[a-z0-9]+匹配字符串“a12”，$匹配位置3。

平衡组的概念及作用

JavaScript不支持平衡组……，因此关于平衡组的测试主要在Expresso 3.1中完成。多说一句，这个Expresso 3.1真好用，香。

平衡组的语法构造可参考之前的文章正则表达式30分钟入门

平衡组，顾名思义，平衡即对称，主要是结合几种正则语法规则，提供对配对出现的嵌套结构的匹配。平衡组有狭义和广义两种定义，狭义平衡组指(?exp)语法，而广义平衡组并不是固定的语法规则，而是几种语法规则的综合应用，我们平时所说的平衡组通常指的是广义平衡组。

下文无特殊说明，平衡组这种简写指的就是广义平衡组。

平衡组的匹配原理

平衡组的匹配原理可以用堆栈来解释，先举个例子，再根据例子进行解释。

源字符串：a+(b*(c+d))/e+f-(g/(h-i))*j
正则表达式：$((?'open'\()|(?'-open'$)|[^()]+)*(?(open)(?!))\)

下面的注释翻译自Expresso

\(                      # 字符‘(’
    (                   # 数字编号的捕获组((?'open'\()|(?'-open'\))|[^()]+)*，重复任意次
        (?'open'\()     # 3个分支，第一个是命名捕获组匹配‘(’，命名为open
        |
        (?'-open'\))    # 第二个是(狭义)平衡组，当匹配到‘)’时,在堆栈中移除最近压入的open捕获
        |
        [^()]+          # 第三个时非括号的任意其他字符，重复一次或多次
    )*
    (?(open)(?!))       # 仅带“Yes”子句的条件表达式，判断堆栈中是否存在名为open捕获组；
                        # 如果有，则尝试匹配(?!),这是一个零宽负向先行断言，由于没有后缀表达式，试图匹配总是失败。
                        # 也就是说如果堆栈中还存在open捕获组，那匹配就应该失败。正则表达式引擎会进行回溯(放弃最前面或最后面的一些字符)，尽量使整个表达式得到匹配。
\)                      # 字符‘)’

下图为Expresso截图：

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

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

先找到”(“作为匹配的开始。即上面的第一行，匹配了a+(b*(c+d))/e+f-(g/(h-i))*j中的第一个括号(蓝色部分)
在第一步之后，每匹配到一个”(“，就入栈一个open捕获组，计数加一
在第一步之后，每匹配到一个”)”，就出栈最近入栈的open捕获组，计数减一

也就是说，上面的第一行”\(“匹配了a+(b*(c+d))/e+f-(g/(h-i))*j中的第一个括号(蓝色部分)

然后，匹配到c前面的“(”，此时，计数加1；继续匹配，匹配到d后面的“)”，计算减1；——注意：此时堆栈中的计数是0，正则还是会向前继续匹配的，但是，如果匹配到“)”的话，比如，这个例子中d))（蓝色显示的括号）——引擎此时将控制权交给(?(Open)(?!))，判断堆栈中open捕获组是否为0，如果为0，则执行匹配“no”分支，由于这个条件判断结构中没有“no”分支，所以什么都不做，把控制权交给接下来的”\)”。这个正则表达式”\)”可匹配接下来的”)”