可以使用正则表达式来匹配嵌套模式吗？ [重复]

是否可以编写与嵌套模式（发生次数未知）匹配的正则表达式？例如，当外部括号内嵌套的打开/关闭括号的数量未知时，正则表达式可以匹配打开和关闭括号吗？

例如：

public MyMethod()
{
  if (test)
  {
    // More { }
  }

  // More { }
} // End

应匹配：

{
  if (test)
  {
    // More { }
  }

  // More { }
}

为了明确回答这个问题，首先需要定义术语：“正则表达式”。

从书本上，正则表达式不能做到这一点，但是无上下文的表达式可以做到。通过这些工具，现代的表达式解析器将使用外部堆栈将正则表达式称为某种东西，这意味着能够回溯，意味着能够递归：实际上，这些都是与上下文无关的表达式，因此，您可以将其与simili-PCRE2（PHP，Java，.NET，Perl，...）或ICU兼容（Obj-C / Swift）工具，通常使用（？> ...）语法，或者使用诸如（？R ）或（？0）语法。

#1 楼

不，就这么简单。有限自动机（即正则表达式基础的数据结构）除了处于其所在的状态外没有其他内存，如果您具有任意深度的嵌套，则需要一个任意大的自动机，该自动机会与有限自动机的概念相冲突。

您可以将嵌套/配对的元素匹配到固定深度，该深度仅受内存限制，因为自动机非常大。但是，实际上，您应该使用下推式自动机，即用于上下文无关文法的解析器，例如LL（自上而下）或LR（自下而上）。您必须考虑更糟糕的运行时行为：O（n ^ 3）vs. O（n），其中n = length（input）。

有很多解析器生成器可用，例如ANTLR对于Java。查找Java（或C）的现有语法也不难。
有关更多背景知识，请参见Wikipedia的自动机理论

就理论而言，托尔斯滕是正确的。在实践中，许多实现都有一些技巧，以便允许您执行递归“正则表达式”。例如。请参阅php.net/manual/en/regexp.reference.php中的“递归模式”一章

– daremon
08-09-25 at 15:26

我对自然语言处理和其中包含的自动机理论的培养非常满意。

–斯托恩·马雷克
08-09-25在15:31

一个清晰的答案。我见过的最好的“为什么不”。

–本末日
08-09-25在16:35

语言理论中的正则表达式和实践中的正则表达式是不同的野兽……因为正则表达式不能具有反向引用，正向引用等优点。

–诺维科夫
10-10-4在16:54

@TorstenMarek-您能确认这还是真的吗？其他来源指出，如果正则表达式引擎支持诸如反向引用之类的功能，它将成为2类语法（无上下文），而不是3类语法（常规语法）。因此，例如PCRE-能够处理嵌套结构。混淆来自这样一个事实，即现实世界中的“正则表达式”在技术上已不再规则。如果这是正确的，那么更新此答案将是很好的。

–安迪·贝克（Andy Baker）
16年8月13日在13:25

#2 楼

使用正则表达式检查嵌套模式非常容易。

'/(\((?>[^()]+|(?1))*\))/'

我同意。但是，（？> ...）原子组语法（在PHP 5.2下）的一个问题是？>部分被解释为：“脚本结束”！这是我的写法：/ \（（？：[^（）] ++ |（？R））* + \）/。这对于匹配和不匹配都更加有效。 / \（（[[（（^（）] |（？R））* \）/的最小形式，确实是一件美丽的事情！

– Ridgerunner
2011-3-12在6:35

双+？我使用（？1）允许注释包含在其他文本中（我将其删除并从我的电子邮件地址正则表达式中简化了）。和（？>之所以被使用，是因为我相信它会使失败更快（如果需要）。这不正确吗？

– MichaelRushton
2011-3-19在12:27

您可以为正则表达式的每个部分添加解释吗？

– EricP
15年1月15日在18:01

对于字符串'（a（b c））（d e）'，使用简单表达式'/ \（[^（）] * \）/'可以得到相同的结果。您的长表达有好处吗？

–Cœur
15年10月13日在7:38

尝试使用/ ^（\（（？> [^（）] + |（？1））* \））+ $ /和/ ^ \（[^（）] * \）+ $ /来匹配（a（ bc））（de）。前者匹配，而后者不匹配。

– MichaelRushton
2015年10月13日9:16

#3 楼

对。 Perl的“正则表达式”不是（并且已经存在很长时间了）。应该注意的是递归正则表达式是Perl 5.10的新功能，即使您可以做到这一点，在大多数情况下（例如解析HTML），您也可能不应该这样做。

–迈克尔·卡曼（Michael Carman）
08-09-25 at 15:09

perldoc.perl.org/perlretut.html

–布拉德·吉尔伯特（Brad Gilbert）
08-10-16在16:30

#4 楼

是的，如果它是.NET RegEx引擎。 .Net引擎支持外部堆栈提供的有限状态机。查看详情

正如其他人提到的那样，.NET并不是唯一能够执行此操作的正则表达式引擎。

– Ben S
10 Mar 15 '10 at 0:18

#5 楼

常规语言的Pumping引理是您不能这样做的原因。
生成的自动机将具有有限数量的状态，例如k，因此绑定了k + 1个开括号的字符串具有在某处重复的状态（因为自动机处理字符）。相同状态之间的字符串部分可以无限次重复，并且自动机不会知道它们之间的区别。

特别是，如果它接受k + 1个开括号，然后接受k + 1个闭括号（应该），它还将接受抽出数量的开括号，然后是不变的k + 1个闭括号（不应该）。

#6 楼

正确的正则表达式将无法做到，因为您将把正则语言的领域留在上下文无关语言领域。

然而，许多语言提供的“正则表达式”软件包严格来说要严格得多例如，Lua正则表达式具有与平衡括号匹配的“ %b()”识别器。在您的情况下，您可以使用“ %b{}”

另一个类似于sed的复杂工具是gema，您可以使用{#}很容易地将平衡的花括号匹配。

因此，取决于您可以使用的“正则表达式”（从广义上来说）工具可以匹配嵌套的括号。

#7 楼

是的

...假设有一些最大的嵌套数量，您很乐意停止。

让我解释一下。

@ torsten-marek是对的，正则表达式无法检查这样的嵌套模式，但是可以定义一个嵌套的正则表达式模式，这将允许您捕获这样的嵌套结构，直到某个最大深度。我创建了一个捕获EBNF样式的注释（在此处尝试），例如：

(* This is a comment (* this is nested inside (* another level! *) hey *) yo *)

正则表达式（用于单深度注释）如下： />

m{1} = \(+\*+(?:[^*(]|(?:\*+[^)*])|(?:\(+[^*(]))*\*+\)+

通过用$+\*+和\*+$+替换{和}并用简单的[^{}]替换介于两者之间的所有内容，可以很容易地适应您的目的：

p{1} = \{(?:[^{}])*\}

（这里是尝试的链接。）

要嵌套，只需在块本身中允许以下模式即可：

p{2} = \{(?:(?:p{1})|(?:[^{}]))*\}
  ...or...
p{2} = \{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\}

要查找三层嵌套的块，请使用：

p{3} = \{(?:(?:p{2})|(?:[^{}]))*\}
  ...or...
p{3} = \{(?:(?:\{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\})|(?:[^{}]))*\}

已经出现了清晰的图案。要查找嵌套在N深度处的注释，只需使用正则表达式即可：

p{N} = \{(?:(?:p{N-1})|(?:[^{}]))*\}

  where N > 1 and
  p{1} = \{(?:[^{}])*\}

可以编写脚本来递归生成这些正则表达式，但这超出了范围我需要这个（这留给读者练习。😉）

#8 楼

在PHP正则表达式引擎中使用递归匹配比括号中的过程匹配要快得多。尤其是较长的字符串。

http://php.net/manual/zh-CN/regexp.reference.recursive.php

例如

$patt = '!\( (?: (?: (?>[^()]+) | (?R) )* ) \)!x';

preg_match_all( $patt, $str, $m );

vs.

matchBrackets( $str );

function matchBrackets ( $str, $offset = 0 ) {

    $matches = array();

    list( $opener, $closer ) = array( '(', ')' );

    // Return early if there's no match
    if ( false === ( $first_offset = strpos( $str, $opener, $offset ) ) ) {
        return $matches;
    }

    // Step through the string one character at a time storing offsets
    $paren_score = -1;
    $inside_paren = false;
    $match_start = 0;
    $offsets = array();

    for ( $index = $first_offset; $index < strlen( $str ); $index++ ) {
        $char = $str[ $index ];

        if ( $opener === $char ) {
            if ( ! $inside_paren ) {
                $paren_score = 1;
                $match_start = $index;
            }
            else {
                $paren_score++;
            }
            $inside_paren = true;
        }
        elseif ( $closer === $char ) {
            $paren_score--;
        }

        if ( 0 === $paren_score ) {
            $inside_paren = false;
            $paren_score = -1;
            $offsets[] = array( $match_start, $index + 1 );
        }
    }

    while ( $offset = array_shift( $offsets ) ) {

        list( $start, $finish ) = $offset;

        $match = substr( $str, $start, $finish - $start );
        $matches[] = $match;
    }

    return $matches;
}

#9 楼

正如zsolt所提到的，某些正则表达式引擎支持递归-当然，这些引擎通常是使用回溯算法的引擎，因此它并不是特别有效。例如：/(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

#10 楼

不，那时候您将进入上下文无关文法领域。

#11 楼

这似乎可行：/(\{(?:\{.*\}|[^\{])*\})/m

它似乎也与{{}不匹配

– Stijn Sanders
2014年1月2日，下午6:52

编程黑洞网