Editar 2: Para uma demonstração prática de por que isso continua importante, não procure maisprópria paralisação causada por regex do stackoverflow hoje (2016-07-20)!

Editar: Essa questão evoluiu consideravelmente desde a primeira vez que a perguntei. Veja abaixo duas implementações rápidas + compatíveis, mas não totalmente completas. Se você souber de mais ou melhores implementações, mencione-as, ainda não há uma implementação ideal aqui ainda!

Onde posso encontrarde forma confiável implementação rápida de Regex?

Alguém sabe de um normalnão retrocedendo (System.Text.RegularExpressions backtracks) implementação de regex de tempo linear para .NET ou nativo e razoavelmente utilizável a partir do .NET? Para ser útil, seria necessário:

tenha umpior caso complexidade do tempo de avaliação regex deO (m * n) onde m é o comprimento da regex e n o comprimento da entrada.tenha umcomplexidade de tempo normal de O (n), uma vez que quase nenhuma expressão regular realmente aciona o espaço de estados exponencial, ou, se puderem, somente o fazem em um subconjunto de minutos da entrada.tenha umvelocidade de construção razoável (ou seja, nenhum DFA potencialmente exponencial)ser destinado ao uso por seres humanos, não matemáticos - por exemplo, Eu não quero reimplementar classes de caracteres unicode:As classes de caracteres de estilo .NET ou PCRE são um ponto positivo.Pontos bônus:Pontos bônus para praticidade, se implementa recursos baseados em pilha quedeixe lidar com aninhamento às custas de consumir memória O (n + m) em vez de memória O (m).pontos de bônus paraou capturando subexpressõesou substitutos (se houver um número exponencial de possíveis correspondências de subexpressão, enumerandotodos deles é inerentemente exponencial - mas enumerar os primeiros não deve ser, e da mesma forma para substituições). Você pode solucionar o recurso ausente usando o outro, portanto, ter um deles é suficiente.lotsa pontos de bônus paratratando regexes como valores de primeira classe (então você pode pegar a união, intersecção, concatenação, negação - em particular, a negação e a intersecção, já que são muito difíceis de fazer por manipulação de string da definição de regex)correspondência preguiçosa Ou seja, a correspondência em fluxos ilimitados sem colocar tudo na memória é uma vantagem. Se os fluxos não suportarem a busca, a captura de subexpressões e / ou substituições não é (em geral) possível em uma única passagem.Backreferences estão fora, eles são fundamentalmente não confiáveis; isto é, pode sempre exibir um comportamento exponencial em casos de entrada patológica.

Tais algoritmos existem (Isto é teoria básica de autômatos ...) - mas existe algum praticamente utilizável?implementações acessível a partir do .net?

Fundo: (você pode pular isso)

Eu gosto de usar o Regex para limpezas de texto rápidas e sujas, mas eu repetidamente me deparo com problemas em que a implementação comum do backfacing do NFA usada pelo perl / java / python / .NET mostra um comportamento exponencial. Infelizmente, esses casos são fáceis de serem acionados assim que você começa a gerar automaticamente suas expressões regulares. Mesmo o desempenho não exponencial pode se tornar extremamente ruim quando você alterna entre expressões regulares que correspondem ao mesmo prefixo - por exemplo, em um exemplo muito básico, se você pegar um dicionário e transformá-lo em uma expressão regular, espere um desempenho terrível.

Para uma rápida visão geral de por que implementações melhores existem e têm desde os anos 60, vejaCorrespondência de expressões regulares pode ser simples e rápida.

Opções não muito práticas:Quase ideal: Toolkit da FSA. Pode compilar regexes para implementações rápidas de C do DFA + NFA, permite que os transdutores (!) Também tenham expressões de primeira classe (encapsulamento yay!) Incluindo sintaxe para interseção e parametrização.Mas está no prólogo... (por que algo com este tipo de características práticas não está disponível em uma linguagem mainstream ???)Rápido mas impraticável: um parser completo, como o excelenteANTLR geralmente suporta regexes rápidos e confiáveis. No entanto, a sintaxe da antlr é muito mais detalhada e, claro, permite construções que podem não gerar analisadores válidos, então você precisa encontrar algum subconjunto seguro.Boas implementações:RE2 - uma biblioteca de código aberto do google visando a compatibilidade PCRE razoável menos referências anteriores. Acho que este é o sucessor da porta unix da regex lib do plan9, dado o autor.TRE - também principalmente compatível com PCRE e até faz backreferences, embora usando aqueles que você perder garantias de velocidade. E tem um modo de correspondência aproximada mega-bacana!

Infelizmente, ambas as implementações são C ++ e exigiriam interoperabilidade para uso do .NET.