Можно ли использовать регулярные выражения для сопоставления с вложенными шаблонами?
Можно ли написать регулярное выражение, которое соответствует вложенному шаблону, который встречается неизвестное количество раз? Например, может ли регулярное выражение соответствовать открывающей и закрывающей фигурной скобке, когда во внешних фигурных скобках есть неизвестное число открытых / закрытых фигурных скобок?
Например:
public MyMethod()
{
if (test)
{
// More { }
}
// More { }
} // End
Должно совпадать:
{
if (test)
{
// More { }
}
// More { }
}
11 ответов
Нет, это так просто Конечный автомат (который является структурой данных, лежащей в основе регулярного выражения) не имеет памяти, кроме состояния, в котором он находится, и если у вас сколь угодно глубокая вложенность, вам нужен сколь угодно большой автомат, который вступает в противоречие с понятием конечного автомата.
Вы можете сопоставлять вложенные / парные элементы до фиксированной глубины, где глубина ограничена только вашей памятью, потому что автомат становится очень большим. На практике, однако, вы должны использовать автомат "нажми-вниз", то есть парсер для грамматики без контекста, например, LL (сверху вниз) или LR (снизу вверх). Вы должны принять во внимание худшее поведение во время выполнения: 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" ;
}
НТН
РЕДАКТИРОВАТЬ: проверить:
- http://dev.perl.org/perl6/rfc/145.html
- Рубиновая информация: 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 (который правильно указал, что это больше не регулярное выражение):
Лемма Pumping для обычных языков является причиной, почему вы не можете сделать это.
Сгенерированный автомат будет иметь конечное число состояний, скажем, k, поэтому строка из k+1 открывающих скобок обязательно должна где-то повторяться (поскольку автомат обрабатывает символы). Часть строки между одним и тем же состоянием может дублироваться бесконечно много раз, и автомат не будет знать разницу.
В частности, если он принимает k+1 открывающие скобки, за которыми следуют k+1 закрывающие скобки (что и должно быть), он также принимает накачанное количество открывающих скобок, за которым следуют неизмененные k+1 закрывающие скобки (что не следует).
Да, если это.NET RegEx-движок. .Net engine поддерживает конечный автомат, снабженный внешним стеком. смотреть детали
Правильные регулярные выражения не смогут сделать это, так как вы оставите царство регулярных языков, чтобы попасть на территории Context Free Languages.
Тем не менее пакеты "регулярных выражений", предлагаемые многими языками, являются строго более мощными.
Например, регулярные выражения Lua имеют "%b()"распознаватель, который будет соответствовать сбалансированным скобкам. В вашем случае вы бы использовали"%b{}"
Еще один сложный инструмент, похожий на sed, - это gema, в котором вы очень легко сопоставите сбалансированные фигурные скобки {#},
Таким образом, в зависимости от инструментов, которыми вы располагаете, ваше "регулярное выражение" (в более широком смысле) может соответствовать вложенным скобкам.
ДА
... при условии, что есть максимальное количество вложений, на которое вы бы с удовольствием остановились.
Позволь мне объяснить.
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} = \{(?:[^{}])*\}
Можно написать сценарий для рекурсивного генерирования этих регулярных выражений, но это выходит за рамки того, для чего мне это нужно. (Это оставлено как упражнение для читателя.)
Использование рекурсивного сопоставления в движке PHP regex значительно быстрее, чем процедурное сопоставление скобок. особенно с более длинными строками.
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;
}
Как упомянул zsolt, некоторые движки регулярных выражений поддерживают рекурсию - конечно, они обычно используют алгоритм обратного отслеживания, поэтому он не будет особенно эффективным. пример: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm
Нет, в этот момент вы попадаете в область контекстно-свободных грамматик.
Мой вопрос + ответ связан, и я делаю выражение и мета-выражение, которые могут соответствовать произвольным (конечным) уровням вложенности. Это довольно странно, но что еще можно ожидать? Используйте обратные ссылки в матче, если ваш движок это поддерживает.