Можно ли использовать регулярные выражения для сопоставления с вложенными шаблонами?[дубликат]

https://stackoverflow.com/questions/133601

02-07-2019
|

Вопрос

На этот вопрос уже есть ответ здесь:

Регулярное выражение для соответствия сбалансированным скобкам 16 ответов

Можно ли написать регулярное выражение, соответствующее вложенному шаблону, который встречается неизвестное количество раз?Например, может ли регулярное выражение соответствовать открывающей и закрывающей фигурным скобкам, когда существует неизвестное количество открывающих / закрывающих фигурных скобок, вложенных во внешние фигурные скобки?

Например:

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

  // More { }
} // End

Должно совпадать:

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

  // More { }
}

Решение

Нет.Это так просто.Конечный автомат (который является структурой данных, лежащей в основе регулярного выражения) не обладает памятью, отличной от состояния, в котором он находится, и если у вас сколь угодно глубокая вложенность, вам нужен сколь угодно большой автомат, который противоречит понятию конечный автомат.

Вы можете сопоставлять вложенные / парные элементы до фиксированной глубины, где глубина ограничена только вашей памятью, потому что автомат становится очень большим.На практике, однако, вам следует использовать нажимной автомат, то есть анализатор для контекстно-свободной грамматики, например 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" ;
  }

HTH

Редактировать: проверить:

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 (который правильно указал, что это больше не регулярное выражение):

http://coding.derkeiler.com/Archive/Perl/comp.lang.perl.misc/2008-03/msg01047.html

Да, если это движок регулярных выражений .NET.Движок .Net engine поддерживает конечный автомат, поставляемый с внешним стеком.видишь Подробные сведения

Тот Самый Лемма о прокачке для обычных языков вот причина, по которой вы не можете этого сделать.

Сгенерированный автомат будет иметь конечное число состояний, скажем k, поэтому строка из k + 1 открывающих фигурных скобок обязательно будет иметь состояние, повторяющееся где-то (по мере того, как автомат обрабатывает символы).Часть строки между одним и тем же состоянием может дублироваться бесконечно много раз, и автомат не заметит разницы.

В частности, если он принимает k + 1 открывающие фигурные скобки, за которыми следуют k + 1 закрывающие фигурные скобки (что и должно быть), он также примет закачанное количество открывающих фигурных скобок, за которыми следуют неизмененные k + 1 закрывающие фигурные скобки (чего не должно быть).

Правильные регулярные выражения не смогли бы этого сделать, поскольку вы покинули бы область обычных языков, чтобы попасть на территории контекстно-свободных языков.

Тем не менее пакеты "регулярных выражений", предлагаемые многими языками, строго говоря, более мощные.

Например, Lua регулярные выражения имеют "%b()" распознаватель, который будет соответствовать сбалансированным скобкам.В вашем случае вы бы использовали "%b{}"

Другим сложным инструментом, похожим на sed, является гема, где вы очень легко сопоставите сбалансированные фигурные скобки с {#}.

Таким образом, в зависимости от имеющихся в вашем распоряжении инструментов ваше "регулярное выражение" (в более широком смысле) может соответствовать вложенной круглой скобке.

Использование рекурсивного сопоставления в движке регулярных выражений 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} = \{(?:[^{}])*\}

Можно было бы написать скрипт для рекурсивной генерации этих регулярных выражений, но это выходит за рамки того, для чего мне это нужно.(Это оставлено в качестве упражнения для читателя.😉)

как упоминал жолт, некоторые движки регулярных выражений поддерживают рекурсию - конечно, обычно это те, которые используют алгоритм обратного отслеживания, поэтому он не будет особенно эффективным.пример: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

Нет, вы вступаете в царство Контекстно - свободные Грамматики в этот момент.

Кажется, это работает: /(\{(?:\{.*\}|[^\{])*\})/m

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow