是否有可能编写一个正则表达式来匹配出现未知次数的嵌套模式?例如,当在外花括号内嵌套了未知数量的开/闭花括号时,正则表达式是否可以匹配开/闭花括号?
例如:
public MyMethod()
{
if (test)
{
// More { }
}
// More { }
} // End
应该匹配:
{
if (test)
{
// More { }
}
// More { }
}
是否有可能编写一个正则表达式来匹配出现未知次数的嵌套模式?例如,当在外花括号内嵌套了未知数量的开/闭花括号时,正则表达式是否可以匹配开/闭花括号?
例如:
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,您可以很容易地用{#}匹配平衡的花括号。
因此,根据您拥有的工具,您的“正则表达式”(在更广泛的意义上)可能能够匹配嵌套括号。