提问人:Richard Dorman 提问时间:9/25/2008 最后编辑:codeforesterRichard Dorman 更新时间:3/29/2018 访问量:146727
正则表达式可以用来匹配嵌套模式吗?[复制]
Can regular expressions be used to match nested patterns? [duplicate]
问:
是否可以编写一个正则表达式来匹配出现未知次数的嵌套模式?例如,当外大括号内嵌套了未知数量的左/右大括号时,正则表达式能否匹配左大括号和右大括号?
例如:
public MyMethod()
{
if (test)
{
// More { }
}
// More { }
} // End
应匹配:
{
if (test)
{
// More { }
}
// More { }
}
答:
不,那时您正在进入上下文自由语法的领域。
不。就这么简单。有限自动机(它是正则表达式的基础数据结构)除了它所处的状态之外没有内存,如果你有任意深度的嵌套,你需要一个任意大的自动机,它与有限自动机的概念相冲突。
您可以将嵌套/成对的元素匹配到固定深度,其中深度仅受内存限制,因为自动机变得非常大。然而,在实践中,你应该使用一个下推自动机,即一个上下文无关语法的解析器,例如LL(自上而下)或LR(自下而上)。您必须考虑较差的运行时行为:O(n^3) 与 O(n),其中 n = length(input)。
有许多可用的解析器生成器,例如用于 Java 的 ANTLR。找到 Java(或 C)的现有语法也不难。
更多背景信息:维基百科的自动机理论
评论
如果字符串在一行上,则可能有效的 Perl 解决方案:
my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;
if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
print "Found: $1\n" ;
}
IT)
编辑:检查:
- http://dev.perl.org/perl6/rfc/145.html
- Ruby 信息:http://www.ruby-forum.com/topic/112084
- 更多 perl:http://www.perlmonks.org/?node_id=660316
- 更多 Perl:https://metacpan.org/pod/Text::Balanced
- perl, perl, perl: http://perl.plover.com/yak/regex/samples/slide083.html
Torsten Marek 还有一件事(他正确地指出,它不再是正则表达式):
评论
常规语言的抽水引理是你不能这样做的原因。
生成的自动机将具有有限数量的状态,例如 k,因此一串 k+1 左大括号必然会在某处重复一个状态(当自动机处理字符时)。同一状态之间的字符串部分可以无限多次复制,自动机不会知道其中的区别。
特别是,如果它接受 k+1 个左大括号,然后是 k+1 个右大括号(它应该接受),它也将接受泵送数量的左大括号,然后是不变的 k+1 右大括号(它不应该)。
正确的正则表达式将无法做到这一点,因为您将离开常规语言领域进入上下文自由语言领域。
然而,许多语言提供的“正则表达式”包严格来说更强大。
例如,Lua 正则表达式具有与平衡括号匹配的 “” 识别器。在你的情况下,你会使用”%b()
%b{}
"
另一个类似于 sed 的复杂工具是 gema,您可以在其中非常轻松地匹配平衡的大括号。{#}
因此,根据您可以使用的工具,您的“正则表达式”(从更广泛的意义上讲)可能能够匹配嵌套括号。
正如 Zsolt 所提到的,一些正则表达式引擎支持递归——当然,这些引擎通常使用回溯算法,所以它不会特别有效。例:/(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm
是的,如果它是 .NET 正则表达式引擎。.Net 引擎支持外部堆栈提供的有限状态机。查看详情
评论
这似乎有效:/(\{(?:\{.*\}|[^\{])*\})/m
评论
{{}
使用正则表达式检查嵌套模式非常容易。
'/(\((?>[^()]+|(?1))*\))/'
评论
(?>...)
?>
/\((?:[^()]++|(?R))*+\)/
/\(([^()]|(?R))*\)/
(?1)
(?>
'(a (b c)) (d e)'
'/\([^()]*\)/'
/^(\((?>[^()]+|(?1))*\))+$/
/^\([^()]*\)+$/
(a (b c))(d e)
在 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;
}
是的
...假设有一些最大数量的嵌套,你会很乐意停下来。
让我解释一下。
@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} = \{(?:[^{}])*\}
可以编写一个脚本来递归生成这些正则表达式,但这超出了我需要它的范围。(这是留给读者的练习。 😉
评论
String getNestedBraceRegex(int n) {if(n == 1) return "\\{(?:[^{}])*\\}"; else return "\\{(?:(?:" + getNestedBraceRegex(n-1) + ")|(?:[^{}]))*\\}";}
(\{((?>[^{}]+|(?1))*)\})
评论
regular expression
context-free expressions
(?>...)
(?R)
(?0)