正则表达式可以用来匹配嵌套模式吗?

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

例如:

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


// More { }
} // End

应该匹配:

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


// More { }
}
138172 次浏览
小开

不，你在这一点上进入了上下文无关语法的领域。

小开
最佳答案

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

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

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

小开

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

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


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

HTH

编辑:检查:

Torsten Marek还有一件事(他已经正确地指出，它不再是一个正则表达式):

小开

常规语言的抽运引理是你不能这样做的原因。

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

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

小开

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

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

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

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

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

小开

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

小开

是的，如果它是。net RegEx-engine. net引擎支持有限状态机提供一个外部堆栈。看到细节

小开

/(\{(?:\{.*\}|[^\{])*\})/m

小开

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

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

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

http://php.net/manual/en/regexp.reference.recursive.php < a href = " http://php.net/manual/en/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;
}
小开

是的

.．.假设有一个最大数量的巢，你会高兴地停止。

让我解释一下。

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

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


提交答案