237

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

例如:

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

  // More { }
} // End

应该匹配:

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

  // More { }
}
4

11 回答 11

274

不,就这么简单。一个有限自动机(它是正则表达式的基础数据结构)除了它所处的状态之外没有内存,如果你有任意深度的嵌套,你需要一个任意大的自动机,这与有限自动机的概念相冲突。

您可以将嵌套/配对元素匹配到固定深度,其中深度仅受您的记忆限制,因为自动机变得非常大。然而,在实践中,您应该使用下推自动机,即用于上下文无关文法的解析器,例如 LL(自上而下)或 LR(自下而上)。您必须考虑更糟糕的运行时行为:O(n^3) 与 O(n),其中 n = 长度(输入)。

有许多可用的解析器生成器,例如Java 的ANTLR。为 Java(或 C)找到现有的语法也不难。
更多背景信息:维基百科的自动机理论

于 2008-09-25T14:27:12.643 回答
36

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

'/(\((?>[^()]+|(?1))*\))/'
于 2010-10-03T18:49:51.500 回答
33

如果字符串在一行上,则可能是有效的 Perl 解决方案:

my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;

if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
    print "Found: $1\n" ;
  }

高温高压

编辑:检查:

Torsten Marek的另一件事(他正确地指出,它不再是正则表达式):

于 2008-09-25T14:40:25.420 回答
19

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

于 2008-12-05T06:35:28.943 回答
17

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

生成的自动机将具有有限数量的状态,例如 k,因此一串 k+1 个左大括号必然会在某处重复一个状态(当自动机处理字符时)。同一状态之间的字符串部分可以无限复制多次,自动机不会知道其中的区别。

特别是,如果它接受 k+1 个左大括号,然后是 k+1 个右大括号(它应该接受),它还将接受泵送的左大括号数量,然后是不变的 k+1 个右大括号(它不应该)。

于 2008-09-25T14:47:07.887 回答
13

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

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

例如,Lua正则表达式具有%b()匹配平衡括号的“”识别器。在您的情况下,您将使用“ %b{}

另一个类似于 sed 的复杂工具是gema,您可以在其中非常轻松地匹配平衡的花括号{#}

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

于 2008-09-25T15:09:20.360 回答
8

是的

...假设有一些最大数量的嵌套你很乐意停下来。

让我解释。


@torsten-marek是正确的,正则表达式无法检查这样的嵌套模式,但是可以定义一个嵌套的正则表达式模式,这将允许您捕获这样的嵌套结构,直到某个最大深度。我创建了一个来捕获EBNF 风格的评论(在这里试试),比如:

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

正则表达式(用于单深度注释)如下:

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

\(+\*+通过将and\*+\)+替换为{and}并将其间的所有内容替换为简单的 ,这可以很容易地适应您的目的[^{}]

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} = \{(?:[^{}])*\}

可以编写一个脚本来递归地生成这些正则表达式,但这超出了我需要的范围。(这留给读者作为练习。)

于 2018-03-28T11:20:37.837 回答
5

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

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

例如

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

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

对比

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;
}
于 2012-09-17T08:43:24.110 回答
3

正如 zsolt 提到的,一些正则表达式引擎支持递归——当然,这些引擎通常使用回溯算法,因此它不会特别有效。例子:/(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

于 2008-09-25T15:25:10.523 回答
2

不,此时您正在进入上下文无关语法领域。

于 2008-09-25T14:19:02.553 回答
0

这似乎有效:/(\{(?:\{.*\}|[^\{])*\})/m

于 2010-04-01T20:39:10.703 回答