Implementación de expresiones regulares que puede manejar expresiones regulares generadas por máquina: * sin retroceso *, O (n)?
Edición 2: Para una demostración práctica de por qué esto sigue siendo importante, no busque más.propia interrupción causada por expresiones regulares de stackoverflow hoy (2016-07-20)!
Editar: Esta pregunta ha evolucionado considerablemente desde la primera vez que la hice. Vea a continuación dos implementaciones rápidas compatibles, pero no completamente completas. Si conoce más o mejores implementaciones, mencionelas, ¡todavía no hay una implementación ideal aquí todavía!
Dónde puedo encontrarseguramente Rápida implementación de Regex?¿Alguien sabe de un normal?sin retroceso (System.Text.RegularExpressions
Backtracks) ¿Implementación de expresiones regulares de tiempo lineal para .NET o nativo y razonablemente utilizable desde .NET? Para ser útil, necesitaría:
Tales algoritmos existen (esto es teoría básica de autómatas ...), pero ¿hay alguna que sea prácticamente utilizable?implementaciones accesible desde .NET?
Fondo: (puedes saltarte esto)Me gusta usar Regex para realizar limpiezas de texto rápidas y sucias, pero me he topado repetidamente con problemas en los que la implementación de NFA en retroceso común utilizada por perl / java / python / .NET muestra un comportamiento exponencial. Desafortunadamente, estos casos son bastante fáciles de desencadenar tan pronto como comienzas a generar automáticamente tus expresiones regulares. Incluso el rendimiento no exponencial puede volverse extremadamente pobre cuando alternas entre expresiones regulares que coinciden con el mismo prefijo; por ejemplo, en un ejemplo realmente básico, si tomas un diccionario y lo conviertes en una expresión regular, esperas un rendimiento terrible.
Para obtener una descripción general rápida de por qué existen mejores implementaciones y se tienen desde los años 60, consulteLa coincidencia de expresiones regulares puede ser simple y rápida.
Opciones no bastante prácticas:Casi ideal: Kit de herramientas FSA. Puede compilar expresiones regulares para implementaciones C rápidas de DFA + NFA, también permite transductores (!), Tiene expresiones regulares de primera clase (encapsulación yay!) Que incluyen sintaxis para intersección y parametrización.Pero está en prólogo.... (¿Por qué algo con este tipo de funciones prácticas no está disponible en un lenguaje general?)Rápido pero poco práctico: un analizador completo, como el excelenteANTLR En general, admite expresiones regulares de forma rápida y fiable. Sin embargo, la sintaxis de antlr es mucho más detallada y, por supuesto, permite construcciones que pueden no generar analizadores válidos, por lo que debería encontrar algún subconjunto seguro.Buenas implementaciones:RE2 - una biblioteca de código abierto de Google que apunta a una compatibilidad razonable con PCRE menos referencias inversas. Creo que este es el sucesor del puerto unix de la expresión regular de plan9, dado el autor.TRE - También es mayormente compatible con PCRE e incluso hace referencias inversas, aunque usar las garantías de pérdida de velocidad. ¡Y tiene un modo de emparejamiento aproximado mega-ingenioso!Desafortunadamente, ambas implementaciones son C ++ y requerirían interoperabilidad para usar desde .NET.