Можно ли написать регулярное выражение, которое соответствует вложенному шаблону, который встречается неизвестным числом раз? Например, может ли регулярное выражение соответствовать открывающей и закрывающейся скобке, если в внешних фигурных скобках имеется неизвестное количество открытых/закрывающих скобок?
Например:
public MyMethod()
{
if (test)
{
// More { }
}
// More { }
} // End
Должно соответствовать:
{
if (test)
{
// More { }
}
// More { }
}
Нет. Это так просто. Конечный автомат (который является структурой данных, лежащей в основе регулярного выражения) не имеет памяти, кроме состояния, в котором он находится, и если у вас есть произвольно глубокое вложение, вам нужен произвольно большой автомат, который сталкивается с понятием конечного автомата.
Вы можете сопоставить вложенные/парные элементы с фиксированной глубиной, где глубина ограничена только вашей памятью, потому что автомат становится очень большим. На практике, однако, вы должны использовать push-down automaton, т.е. Синтаксический анализатор для контекстно-свободной грамматики, например LL (сверху вниз) или LR (снизу вверх). Вы должны учитывать худшее поведение во время выполнения: O (n ^ 3) по сравнению с O (n), с n = длина (ввод).
Существует много генераторов синтаксического анализатора, например ANTLR для Java. Найти существующую грамматику для Java (или C) также не сложно.
Для получения дополнительной информации: Теория автоматов в Википедии
Возможно, работающее решение Perl, если строка находится в одной строке:
my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;
if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
print "Found: $1\n" ;
}
НТН
РЕДАКТИРОВАТЬ: проверить:
И еще одна вещь Torsten Marek (кто правильно указал, что это не регулярное выражение):
Использование регулярных выражений для проверки вложенных шаблонов очень просто.
'/(\((?>[^()]+|(?1))*\))/'
Да, если это .NET RegEx-движок..Net поддерживает конечный конечный автомат, поставляемый с внешним стеклом. см. подробности
Лекция о перекачке для правильных языков - причина, по которой вы не можете этого сделать.
Сгенерированный автомат будет иметь конечное число состояний, скажем k, поэтому строка из k + 1 открывающих фигурных скобок связана с тем, что состояние повторяется где-то (поскольку автомат обрабатывает символы). Часть строки между одним и тем же состоянием может быть продублирована бесконечно много раз, и автомат не узнает разницу.
В частности, если он принимает k + 1 открывающих скобок, за которыми следуют k + 1 закрывающие скобки (что он должен), он также примет количество накачиваемых открывающих фигурных скобок, за которым следуют неизменные k + 1 замыкающие браки (что не должно).
Правильные регулярные выражения не смогут сделать это, так как вы покинете область обычных языков для приземления на территориях контекстного свободного языка.
Тем не менее, пакеты "регулярного выражения", предлагаемые многими языками, являются более мощными.
Например, Lua в регулярных выражениях есть распознаватель <%b(), который будет соответствовать сбалансированным скобкам. В вашем случае вы будете использовать "%b{}"
Другим сложным инструментом, похожим на sed, является gema, где вы легко сопоставляете сбалансированные фигурные фигурные скобки с помощью {#}.
Итак, в зависимости от инструментов, которые у вас есть, ваше "регулярное выражение" (в более широком смысле) может соответствовать вложенным скобкам.
Использование рекурсивного соответствия в 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 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;
}
Как упоминалось в zsolt, некоторые двигатели регулярных выражений поддерживают рекурсию - конечно, обычно это те, которые используют алгоритм обратного отслеживания, поэтому он не будет особенно эффективен. Пример: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm
Нет, вы попадаете в область Контекстные бесплатные грамматики в этой точке.
... предполагая, что есть некоторое максимальное количество гнезд, с которыми вы были бы счастливы остановиться.
Позволь мне объяснить.
@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} = \{(?:[^{}])*\}
Сценарий можно записать для рекурсивного генерации этих регулярных выражений, но это выходит за рамки того, что мне нужно для этого. (Это остается как упражнение для читателя. 😉)
Это работает: /(\{(?:\{.*\}|[^\{])*\})/m
Мой вопрос + ответ связан, и я делаю выражение и мета-выражение, которое может соответствовать произвольным (конечным) уровням вложенности. Это довольно изящно, но что еще вы можете ожидать? Используйте обратные ссылки в матче, если ваш движок поддерживает его.
Нет. Вам нужен полноразмерный парсер для этого типа проблем.