2

假设我有一个带有任意数量的捕获组的正则表达式：

pattern = /(some)| ..a lot of masks combined.... |(other)/

有没有办法确定这些组的数量？

4

1 回答 1

2

如果你总能找到一个与你给定的正则表达式匹配的字符串，那么将它与正则表达式匹配就足够了，并查看匹配数据长度。但是，确定正则表达式是否具有匹配的字符串是 np-hard [1]。这只有在您事先知道您将获得什么样的正则表达式时才可行。

类中下一个最好的方法Regexp是Regexp#sourceor Regexp#to_s。但是，如果我们这样做，我们需要解析正则表达式。

我不能说未来，但从Ruby 2.0 开始Regexp，核心类中没有更好的方法。

如果前面有未转义的反斜杠，则左括号表示文字左括号。除非前面有未转义的反斜杠，否则反斜杠是未转义的。因此，如果前面有奇数个反斜杠，则字符会被转义。

未转义的左括号表示捕获组当且仅当后面没有问号。带有问号，它可以表示各种含义：(?'name')并(?<name>)表示一个命名的捕获组。然而，命名和未命名的捕获组不能在同一个正则表达式中共存[2]。(?:)表示非捕获组。这是 的一个特例(?flags-flags:)。(?>)表示原子团。(?=), (?!),(?<=)和(?<!)表示环视。(?#)表示评论。

Ruby 正则表达式引擎支持正则表达式中的注释。在主正则表达式中考虑它们将非常困难。如果我们真的想支持这些，我们可以尝试剥离它们，但是完全支持它们会变得混乱，因为内联标志可能会以正则表达式无法捕获的方式打开和关闭扩展模式（以及因此行注释）。我将继续并且不支持正则表达式注释中的未转义括号[3]。

我们要计算：

  • 左括号的数量\(
  • 没有被反斜杠转义(?<!(?<!\\)(?:\\\\)*\\)（阅读：前面没有奇数个反斜杠，前面没有另一个反斜杠）和
  • 后面没有问号的(?!\?)

ruby 不支持无界的lookbehind，但是如果我们先反转源码，我们可以稍微重写第一个断言：(?!(?:\\\\)*(?!\\)). 第二个断言变成了一个lookbehind (?<!\?)：.

整体解决方案

def count_groups(regexp)
  # named capture support:
  # named_count = regexp.named_captures.count 
  # return named_count if named_count > 0

  # main: 
  test = /(?!<\?)\((?!(?:\\\\)*(?!\\))/
  regexp.source.scan(test).count
end

[1]：我们可以通过将可满足性问题转换为它来显示 NP 硬度：

  • AND：（xy必须x是断言）
  • 或者：x|y
  • 不是：(?!x)
  • 原子：(?=1), (?=.1), (?=..1), ..., (?!1), (?!.1)...

示例（异或）：/^(?:(?=1)(?!.1)|(?!1)(?=.1))..$/

这扩展到可以在多项式时间内测试的任何类型的正则表达式的 NP 完整性。这包括任何没有嵌套重复（或重复反向引用重复或递归）和可选匹配的有界嵌套深度的正则表达式。

[2]：/((?<name>..)..)../.match('abcdef').to_a返回['abcdef', 'ab']，表示存在命名捕获组时忽略未命名捕获组。在 Ruby 1.9.3 中测试

[3]：内联注释以 . 开头(?#和结尾)。它们不能包含未转义的右括号，但可以包含未转义的左括号。这些可以很容易地剥离（即使我们必须在任何地方都撒上“未转义”的正则表达式），它们的危害较小，但它们也不太可能包含未转义的左括号。

行注释以换行符开始#和结束。这些仅在扩展模式中被视为注释。在扩展模式之外，它们匹配文字#和换行符。这仍然很容易，即使我们不得不考虑再次逃跑。确定正则表达式是否设置了扩展标志并不太困难，但标志修饰符组完全不同。

即使使用 Ruby 令人敬畏的递归正则表达式，仅确定修改扩展模式的先前打开的组是否已经关闭会产生非常讨厌的正则表达式（即使您一个一个替换并且不必跳过注释，您也必须考虑逃逸）。它不会很漂亮（即使有插值），也不会很快。

于 2013-07-06T06:26:51.317 回答