在Ruby中使用递归正则表达式（如perl）匹配平衡括号

Question

我一直在寻找一种在正则表达式中匹配平衡括号的方法，发现了Perl中使用递归正则表达式的方法：

my $re;
$re = qr{
           \(
              (?:
                 (?> [^()]+ )       # Non-parens without backtracking
                 |
                 (??{ $re })        # Group with matching parens
              )*
           \)
         }x;

从Perl正则表达式网站获得。

是否有一种方法可以在Ruby或类似语言中执行此操作？

更新:

对于那些感兴趣的人，这里是一些有趣的链接：

Oniguruma手册 - 来自Sawa的回答。

Pragmatic Programmers' Ruby 1.9 正则表达式示例章节

- Yet Another Geek

---

Oniguruma文档链接已不再提供。更好的来源可能是：https://github.com/kkos/oniguruma/blob/master/doc/RE - Gabriel Mazetto

我经常惊讶于语言设计者未能从 Perl 中学到东西 - 这是一种具有有点奇怪语法的惊人语言。 - John Deighan

Answer 1

是的。在 Ruby 1.9 中内置了 oniguruma 正则表达式引擎，并可在 Ruby 1.8 上安装。您可以使用 (?<name>...) 或 (?'name'...) 命名子正则表达式。然后在同一正则表达式中使用 \g<name> 或 \g'name' 调用子正则表达式。因此，您的正则表达式翻译为 oniguruma 正则表达式将是：

re = %r{
  (?<re>
    \(
      (?:
        (?> [^()]+ )
        |
        \g<re>
      )*
    \)
  )
}x

还要注意，在PHP>=5中，多字节字符串模块使用oniguruma正则表达式引擎，因此您将能够执行相同的操作。

oniguruma的手册在这里。

- sawa

---

那么有人最好更新维基百科页面。不过，我更喜欢使用\((?:[^()]*+|(?0))*\)的这个更简单的答案。 - tchrist

@sawa：做得好！但最好将Uɴɪᴄᴏᴅᴇ属性支持改为Some：Oniguruma仅支持Gᴇɴᴇʀᴀʟ_Cᴀᴛᴇɢᴏʀʏ和一些Sᴄʀɪᴘᴛ。Uɴɪᴄᴏᴅᴇ属性支持有4个以上的级别：⑴RL1.2所需的所有11个属性；⑵兼容属性，如\w 和 ᶜ根据RL1.2A；⑶命名字符，如\N{POUND SIGN} 根据RL2.5；和⑷所有属性的全面支持 根据RL2.7。Perl＆ICU符合所有④; Ruby符合 ⓪。 - tchrist

很高兴为您服务。Oniguruma具有许多有趣的功能，但它也有一些严重的缺陷，比如在正则表达式层面处理物理串行化（编码）而不是始终在虚拟代码点中处理。这是一个很大的头痛和一个严重的违规：Level 1: Basic Unicode Support. 在这个级别上，正则表达式引擎提供对Unicode字符的基本逻辑单元支持。(这与Unicode的实际序列化形式如UTF-8、UTF-16BE、UTF-16LE、UTF-32BE或UTF-32LE无关。) 这是有用的Unicode支持的最低级别。 看到了吗？ - tchrist

@sawa 虽然你的回答非常有帮助，但你可能应该进行这个小修正：将 (??\g<re>) 更改为 (\g<re>)，因为 (?? {}) 是Perl动态递归运算符（或类似的东西）。 - Yet Another Geek

@sawa - 你太棒了 :-) - Arup Rakshit

Answer 2

我喜欢上述解决方案，但经常希望忽略转义字符。假设 \ 转义以下字符，则以下正则表达式也处理转义字符。

ESC= /(?<![\\])(?>[\\](?:[\\][\\])*)/
UNESC= /(?:\A|(?<=[^\\]))(?:[\\][\\])*/
BALANCED_PARENS = /#{UNESC}(
                   (?<bal>\(
                    (?>
                      (?>  (?:#{ESC}\(|#{ESC}\)|[^()])+     )
                      |\g<bal>
                    )*
                    \))    ) /xm

考虑到负回顾限制的局限性，由匹配括号分隔的部分将是第一个捕获而不是整个匹配（整个匹配可能包含前导转义反斜杠）。

ESC和UNESC的复杂性原因在于\\被认为是一个转义的反斜杠。我们仅在初始括号匹配之前使用UNESC序列，因为任何其他转义的括号都将在原子组内匹配并且永远不会回溯。确实，如果我们尝试使用UNESC前缀来匹配内部或最终括号匹配中的任何一个，当原子组中的[^()]匹配前导\'s并拒绝回溯时，它将失败。

此正则表达式将扫描第一个定界平衡括号的左括号。因此，对于字符串" ( ( stuff )"，它将匹配"( stuff )"。通常，期望的行为是定位第一个（未转义）括号并匹配内部（如果平衡）或无法匹配。不幸的是，原子分组不能阻止整个正则表达式被回退并在稍后的某个点尝试匹配，因此我们必须锚定在字符串的开头并仅查看第一个捕获。以下正则表达式进行了更改：

BALANCED_PARENS = /\A(?:#{ESC}\(|#{ESC}\)|[^()])*+
                  (?<match>\(
                   (?<bal>
                    (?>
                      (?>  (?:#{ESC}\(|#{ESC}\)|[^()])+     )
                      |\(\g<bal>
                    )*
                    \))    ) /xm

- Peter Gerdes