Comportamento de Correspondência
O mecanismo de expressões regulares do .NET Framework faz correspondências de referência passada de expressões regulares que incorpora um mecanismo Nondeterministic Finite Automaton (NFA) tradicional, como os usado em Perl, Python, Emacs e TCL.Isso o distingue de mecanismos mais rápidos, porém mais limitados, de pura expressão regular de Deterministic Finite Automaton (DFA), como os encontrados em awk, egrep ou lex.Isso também o distingue NFAs POSIX padronizados, porém mais lentos.
Três tipos de mecanismos de expressões regulares
Esta seção fornece uma visão geral dos benefícios e desvantagens dos três tipos de mecanismos e explica por que o mecanismo do .NET Framework implementa um correspondente NFA tradicional.
Mecanismos DFA executam em tempo linear porque eles não exigem retrocesso (e, portanto, eles nunca testam o mesmo caractere duas vezes).Eles também podem garantir correspondências às sequências mais longas possíveis.No entanto, como um mecanismo DFA contém somente estado finito, ele não pode coinciir com um padrão com referências passadas, e porque ele não construir uma expansão explícita, ele não pode capturar subexpressões.
Mecanismos tradicionais NFA executam os chamados algoritmos de referência pssada de correspondência de "ganância", que testa todas as possíveis expansões de uma expressão regular em uma ordem específica e aceita a primeira correspondência.Devido a um NFA tradicional construir uma expansão específica da expressão regular para uma correspondência com êxito, ele pode capturar correspondências de subexpressões e referências passadas correspondentes.No entanto, devido a um NFA tradicional retroceder, ele pode visitar exatamente o mesmo estado várias vezes se o estado chegou sobre caminhos diferentes.Como resultado, ele pode executar de forma exponencialmente mais lenta no caso mais grave.Devido a um NFA tradicional aceitar a primeira correspondência que ele encontra, ele também pode deixar outras correspondências (possivelmente mais longas) não descobertas.
Mecanismos POSIX NFA são como mecanismos NFA tradicionais, exceto pelo fato de que eles continuam o retrocesso até que eles possam garantir que eles descobriram o correspondente mais longo possível.Como resultado, um mecanismo POSIX NFA é mais lento do que um mecanismo NFA tradicional, e ao usar um POSIX NFA você não pode preferir uma correspondência menor ao invés de uma maior alterando a ordem da pesquisa de retrocesso.
Mecanismos NFA tradicionais são favorecidos por programadores porque eles são mais expressivos que mecanismos DFA ou NFA POSIX.Embora no caso mais grave eles podem executar mais lentamente, você pode comandá-los para localizar correspondências em tempo linear ou polinomial usando os padrões que reduzem ambiguidades e limitam retrocesso.
Recursos do Mecanismo .NET Framework
Levando em conta os benefícios de um mecanismo NFA tradicional, o mecanismo de expressões regulares .NET Framework inclui um conjunto completo de construtores que permitem que os programadores comandem o mecanismo de retrocesso.Esses construtores podem ser usados para localizar correspondências mais rápido ou favorecer expansões específicas sobre outras expansões.
Outros recursos incluem as seguintes capacidades:
Quantificadores "Lentas": ??, *?, +?, {n,m}?.Estes informam o mecanismo de retrocesso para procurar o número mínimo de repetições primeiro.Por outro lado, quantificadores comuns de ganância tentam coincidir com o número máximo de repetições pela primeira vez.
Positiva visão antecipada.Isso permite que o mecanismo de retrocesso retorne ao mesmo ponto no texto após uma subexpressão correspondente.Ele é útil para pesquisar em todo o texto, verificando vários padrões a partir a mesma posição.
Negativa visão antecipada.Isso adiciona a capacidade para coincidir com uma expressão somente se uma subexpressão não corresponde.Isso é particularmente poderoso para refinar uma pesquisa, porque geralmente uma expressão para casos em que deve ser eliminada é muito mais simples do que uma expressão para casos em que deve ser incluído.(Por exemplo, é difícil escrever uma expressão para palavras que não comecem com "Não".)
Avaliação condicional.Isso permite que o mecanismo pesquise usando mais de um padrão alternativo, de acordo com os resultados das correspondências de subexpressão anteriores.Isso permite que um formulário mais poderoso de referência passada permita, por exemplo, corresponder um parêntese direito quando um parêntese esquerdo foi capturado anteriormente em uma subexpressão.
Subexpressão que não realizam recuo (também conhecida com subexpressão gulosa.)Isso permite que o mecanismo de retrocesso garanta que uma subexpressão corresponda apenas a primeira correspondência encontrada para aquela subexpressão, como se a expressão estivesse sendo executada independente da expressão que a contém.Sem est construtor, pesquisas de retrocesso a partir de expressões maiores podem alterar o comportamento de uma subexpressão.
Correspondência da direita para a esquerda.Isso é útil quando a pesquisa é feita da direita para a esquerda em vez de a partir da esquerda para direita ou nos casos em que ele é mais eficiente para iniciar uma correspondência na parte direita do padrão em vez de à esquerda.
Lookbehind positivos e negativos.Semelhante à visão antecipada.Devido ao mecanismo de expressões regulares permitir correspondência completa da direita para esquerda, expressões regulares permitem irrestrios lookbehinds.