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

StackOverflow https://stackoverflow.com/questions/133601

  •  02-07-2019
  •  | 
  •  

题

这个问题在这里已经有答案了：

是否可以编写一个正则表达式来匹配出现次数未知的嵌套模式？例如，当外大括号内嵌套未知数量的左大括号时，正则表达式是否可以匹配左大括号和右大括号？

例如：

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

  // More { }
} // End

应匹配：

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

  // More { }
}
有帮助吗？

解决方案

不。就是这么简单。有限自动机（正则表达式底层的数据结构）除了其所处状态之外没有内存，如果您有任意深度的嵌套，则需要一个任意大的自动机，这与 有限 自动机。

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

有许多可用的解析器生成器，例如 ANTLR 对于Java。找到 Java（或 C）的现有语法也不难。
了解更多背景： 自动机理论 在维基百科

其他提示

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

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

如果字符串在一行上，则可能是可行的 Perl 解决方案：

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

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

华泰

编辑： 查看：

还有一件事 托斯顿·马雷克 （谁正确地指出，它不再是正则表达式了）：

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

这 常规语言的泵送引理 这就是你不能这样做的原因。

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

特别是，如果它接受 k+1 个左大括号，后跟 k+1 个右大括号（它应该），它也将接受泵送数量的左大括号，后跟未更改的 k+1 个右大括号（它不应该）。

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

尽管如此，许多语言提供的“正则表达式”包实际上更强大。

例如， 卢阿 正则表达式有“%b()" 将匹配平衡括号的识别器。在你的情况下，你会使用“%b{}"

另一个类似于 sed 的复杂工具是 杰马, ，您可以轻松地将平衡花括号与 {#}.

因此，根据您可以使用的工具，您的“正则表达式”（广义上）可能能够匹配嵌套括号。

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

是的

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

让我解释。

@托斯顿·马雷克 正则表达式无法检查像这样的嵌套模式，这是正确的， 但 有可能 定义 嵌套的正则表达式模式将允许您捕获像这样的嵌套结构 达到某个最大深度. 。我创建了一个来捕获 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} = \{(?:[^{}])*\}

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

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

不，你正在进入的领域 上下文无关语法 在那时候。

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top