Implementação de Regex que pode manipular regex gerados por máquina: * non-backtracking *, O (n)?
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:
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.