在做LazyKey的时候，遇见了一个场景，光标在括号右边，需要获取改括号前面的函数名。虽然用堆栈写个语法分析器很方便，但是我就想着用正则表达式是不是更简单？

坑啊， JS 不支持平衡组……

平衡组介绍

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

这里需要用到以下的语法构造：

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

每碰到一个左括号，就添加一个 group，每碰到一个右括号，就去掉一个，到了最后看还有没有 group，如果有则证明左括号比右括号多，那么 匹配就失败了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<                 #最外层的左括号
  [^<>]*          #最外层的左括号后面的不是括号的内容
  (
    (
      (?'Open'<)  #碰到了左括号，添加一个"Open"
      [^<>]*      #匹配左括号后面的不是括号的内容
    )+
    (
      (?'-Open'>) #碰到了右括号，去掉一个"Open"
      [^<>]*      #匹配右括号后面不是括号的内容
    )+
  )*
  (?(Open)(?!))   #在遇到最外层的右括号前面，判断还有没有没去掉的"Open"；如果有，则匹配失败
>                 #最外层的右括号

平衡组的概念

平衡组，故名思义，平衡即对称，主要是结合几种正则语法规则，提供对配对出现的嵌套结构的匹配。平衡组有狭义与广义两种定义，狭义平衡组指(?Expression) 语法，而广义平衡组并不是固定的语法规则，而是几种语法规则的综合运用，我们平时所说的平衡组通常指的是广义平衡组。本文中如无特殊说明，平衡组这种简写指的是广义平衡组。

平衡组的匹配原理

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

源字符串：a+(b*(c+d))/e+f-(g/(h-i))*j

正则表达式：((?<Open>\()|(?<−Open>((?<Open>\()|(?<−Open>)|[^()])*(?(Open)(?!))\)

需求说明：匹配成对出现的()中的内容

输出：(b*(c+d)) 和 (g/(h-i))

我将上面正则表达式代码分行写，并加上注释，这样看起来有层次，而且方便 

1
2
3
4
5
6
7
8
9
10
\(                #普通字符“(”
   (              #分组构造，用来限定量词“*”修饰范围
     (?<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不配对出现时，报告匹配失败。

参考：https://blog.csdn.net/zm2714/article/details/7946437