Pode expressões regulares ser usado para corresponder a padrões aninhadas? [duplicado]

StackOverflow https://stackoverflow.com/questions/133601

  •  02-07-2019
  •  | 
  •  

Pergunta

Esta questão já tem uma resposta aqui:

É possível escrever uma expressão regular que corresponde a um padrão aninhado que ocorre um número desconhecido de vezes? Por exemplo, pode uma expressão regular corresponde a uma abertura e chave de fechamento quando há um número desconhecido de chaves de abertura / fecho aninhados dentro das chaves exteriores?

Por exemplo: 

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

  // More { }
} // End

Caso jogo: 

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

  // More { }
}
Foi útil?

Solução

No. É tão fácil. Um autômato finito (que é a estrutura de dados subjacente uma expressão regular) não tem memória para além do estado em que está, e se você tiver arbitrariamente profunda aninhamento, você precisa de um arbitrariamente grande autômato, que colide com a noção de um finito autômato.

Você pode combinar aninhados / elementos emparelhados até uma profundidade fixa, onde a profundidade é limitado apenas pela sua memória, porque o autômato fica muito grande. Na prática, no entanto, você deve usar um para baixo impulso autômato, analisador ou seja um para uma gramática livre de contexto, por exemplo LL (top-down) ou LR (bottom-up). Tem de tomar o tempo de execução do comportamento pior em conta:. O (n ^ 3) vs S (n), com n = comprimento (entrada)

Existem muitos geradores de analisador avialable, por exemplo ANTLR para Java. Encontrar uma gramática existente para Java (ou C) também não é difícil.
Para mais fundo: Automata Teoria na Wikipedia

Outras dicas

Usando expressões regulares para verificar se há padrões aninhadas é muito fácil. 

'/(\((?>[^()]+|(?1))*\))/'

solução Perl Provavelmente trabalhando, se a cadeia está em uma linha: 

my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;

if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
    print "Found: $1\n" ;
  }

HTH

EDIT: de verificação:

E mais uma coisa por Torsten Marek (que tinha apontado corretamente, que não é um regex mais) :

Sim, se for .NET RegEx-motor. Net motor suporta máquina de estado finito fornecido com uma pilha externo. Consulte

O lema do bombeamento para linguagens regulares é a razão pela qual você não pode fazer isso.

O autômato gerado terá um número finito de estados, dizem k, então uma seqüência de k + 1 chaves de abertura é obrigado a ter um lugar estado repetido (como o autômato processa os caracteres). A parte da cadeia de caracteres entre o mesmo estado pode ser repetido infinitamente muitas vezes e o autômato não vai saber a diferença.

Em particular, se ele aceita k + cintas uma abertura seguido de + 1 chaves de fechamento k (que deveria) que também irá aceitar o número de cintas bombeado abertura seguido por Brases k + 1 fechamento inalterados (o que não deveria ).

As expressões regulares adequada não seria capaz de fazê-lo como você iria deixar o reino das Linguagens Regulares à terra no contexto linguagens livres territórios.

Contudo os "expressão regular" pacotes que muitas línguas oferta são estritamente mais poderoso.

Por exemplo, Lua expressões regulares têm o reconhecedor "%b()" que irá corresponder parêntese equilibrada. No seu caso, você usaria "%b{}"

Outra ferramenta sofisticada semelhante ao sed é gema , onde irá partida equilibrada chaves muito facilmente com {#}.

Assim, dependendo das ferramentas que você tem à sua disposição a sua "expressão regular" (em sentido amplo) pode ser capaz de corresponder parênteses aninhados.

Usando a correspondência recursiva no motor de regex PHP é maciçamente mais rápido do que a correspondência processual de suportes. especialmente com cadeias mais longas.

http://php.net/manual/en/regexp.reference.recursive.php

por exemplo. 

$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;
}

YES

... assumindo que existe algum número máximo de assentamentos que ficaria feliz de parar em.

Deixe-me explicar.

@ torsten-marek é certo que uma expressão regular não pode buscar por padrões aninhadas como este, MAS é possível definir um padrão regex aninhada que lhe permitirá capturar estruturas aninhadas como esta até uma profundidade máxima . Eu criei um para capturar EBNF-style comentários ( experimentá-lo aqui ), como: 

(* This is a comment (* this is nested inside (* another level! *) hey *) yo *)

O regex (para comentários única de profundidade) é o seguinte: 

m{1} = \(+\*+(?:[^*(]|(?:\*+[^)*])|(?:\(+[^*(]))*\*+\)+

Isto poderia facilmente ser adaptado para os seus fins, substituindo o \(+\*+ e \*+\)+ com { e } e substituindo tudo mais com um [^{}] simples: 

p{1} = \{(?:[^{}])*\}

( Aqui está o link para tentar isso.)

Para ninho, apenas permitir que este padrão dentro do próprio bloco: 

p{2} = \{(?:(?:p{1})|(?:[^{}]))*\}
  ...or...
p{2} = \{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\}

Para encontrar blocos triple-aninhadas, use: 

p{3} = \{(?:(?:p{2})|(?:[^{}]))*\}
  ...or...
p{3} = \{(?:(?:\{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\})|(?:[^{}]))*\}

Um claro padrão emergiu. Para encontrar aninhadas até uma profundidade de N, basta usar o regex: 

p{N} = \{(?:(?:p{N-1})|(?:[^{}]))*\}

  where N > 1 and
  p{1} = \{(?:[^{}])*\}

Um script poderia ser escrito para gerar recursivamente estas expressões regulares, mas isso está além do escopo do que eu preciso disso para. (Este é deixado como um exercício para o leitor. ??)

como zsolt mencionado, alguns motores de regex apoiar recursão - é claro, estes são normalmente os que utilizam um algoritmo de recuo por isso não vai ser particularmente eficiente. exemplo: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

Não, você está entrando no reino da Contexto gramáticas livres nesse ponto .

Isso parece funcionar: /(\{(?:\{.*\}|[^\{])*\})/m

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top