是否有可能编写一个正则表达式来匹配出现未知次数的嵌套模式?例如,当在外花括号内嵌套了未知数量的开/闭花括号时,正则表达式是否可以匹配开/闭花括号?

例如:

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

  // More { }
} // End

应该匹配:

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

  // More { }
}

当前回答

不,你在这一点上进入了上下文自由语法的领域。

其他回答

使用正则表达式检查嵌套模式非常简单。

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

常规语言的泵浦引理是您不能这样做的原因。

生成的自动机将有有限数量的状态,比如k,所以一个由k+1个开括号组成的字符串必然在某个地方有一个重复的状态(当自动机处理字符时)。相同状态之间的字符串部分可以复制无限次,自动机不会知道其中的区别。

特别是,如果它接受k+1个开大括号,后面跟着k+1个闭大括号(它应该),它也会接受泵送的开大括号数量,后面跟着不变的k+1个闭大括号(它不应该)。

在PHP regex引擎中使用递归匹配要比括号的过程匹配快得多。尤其是长弦的时候。

http://php.net/manual/en/regexp.reference.recursive.php

e.g.

$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;
}

不,你在这一点上进入了上下文自由语法的领域。

正确的正则表达式将无法做到这一点,因为您将离开常规语言领域,进入上下文自由语言领域。

然而,严格来说,许多语言提供的“正则表达式”包更强大。

例如,Lua正则表达式有“%b()”识别器,它将匹配平衡圆括号。在你的例子中,你可以使用"%b{}"

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

因此,根据您拥有的工具,您的“正则表达式”(在更广泛的意义上)可能能够匹配嵌套括号。