递归模式

考虑匹配圆括号内字符串的问题,允许无限嵌套括号。如果不使用递归, 最好的方式是使用一个模式匹配固定深度的嵌套。它不能处理任意深度的嵌套。 perl 5.6 提供了一个实验性的功能允许正则表达式递归。 特殊项 (?R) 提供了递归的这种特殊用法。 这个PCRE模式解决了圆括号问题(假设 PCRE_EXTENDED 选项被设置了, 因此空白字符被忽略): \( ( (?>[^()]+) | (?R) )* \)

首先,它匹配一个左括号。 然后它匹配任意数量的非括号字符序列或一个模式自身的递归匹配(比如, 一个正确的括号子串),最终,匹配一个右括号。

这个例子模式包含无限重复的嵌套,因此使用了一次性子组匹配非括号字符, 这在模式应用到模式不匹配的字符串时非常重要。比如, 当它应用到 (aaaaaaaaaaaaaaaaaaaaaaaaaaaaa() 时就会很快的产生”不匹配”结果。 然而,如果不使用一次性子组,这个匹配将会运行很长时间, 因为有很多途径让 + 和 * 重复限定分隔目标字符串, 并且在报告失败之前需要测试所有路径。

所有捕获子组最终被设置的捕获值都是从递归最外层子模式捕获的值。 如果上面的模式匹配 (ab(cd)ef),捕获子组最终被设置的值为 ”ef”, 即顶级得到的最后一个值。如果增加了额外的括号,\( ( ( (?>[^()]+) | (?R) )* ) \),捕获到的字符串就是顶层括号的匹配内容 ”ab(cd)ef”。 如果在模式中有超过 15 个捕获括号, PCRE 在递归期间就会使用 pcre_malloc 分配额外的内存来存储数据, 随后通过 pcre_free 释放他们。如果没有内存可被分配,它就仅保存前 15 个捕获括号, 在递归内部无法给出内存不够用的错误。

从 PHP 4.3.3 开始, (?1)(?2) 等可以用于递归子组。这同样可以用于命名子组: (?P>name)(?P&name)

如果递归子组语法在它提到的子组括号外部使用(无论是子组数字序号还是子组名称), 这个操作就相当于程序设计语言中的子程序。 前面一些有一个例子指出模式 (sens|respons)e and \1ibility 匹配 ”sense and responsibility” 和 ”response and responsibility”,但是不匹配 ”sense and responsibility”。如果用模式 (sens|respons)e and (?1)ibility 替代, 它会像匹配那两个字符串一样匹配 ”sense and responsibility”。 这种引用方式意义是紧接着匹配引用的子模式。(译注: 后向引用只匹配引用的子组之前匹配的结果, 这里的递归语法引用是拿引用的子模式重新匹配。)

目标字符串的最大长度是 int 型变量可以存储的最大正整数。然而, PCRE 使用递归处理子组和无限重复。 这就是说对于某些模式可用的栈空间可能会受目标字符串限制。

关注编程学问公众号