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:

tener unpeor de los casos complejidad de tiempo de la evaluación de expresiones regulares deO (m * n) donde m es la longitud de la expresión regular y n la longitud de la entrada.tener untiempo normal-complejidad de O (n), ya que casi ninguna expresión regular en realidad dispara el espacio de estado exponencial, o, si es posible, solo lo hace en un subconjunto de minutos de la entrada.tener unvelocidad de construcción razonable (es decir, no hay DFA potencialmente exponenciales)debe estar diseñado para ser utilizado por seres humanos, no por matemáticos, por ejemplo, No quiero volver a implementar las clases de caracteres Unicode:Clases de caracteres estilo .NET o PCRE son una ventaja.Puntos extra:puntos extra por practicidad si implementa características basadas en pila quedéjalo manejar la anidación a costa de consumir memoria O (n + m) en lugar de memoria O (m).puntos de bonificación paraya sea captura de subexpresioneso reemplazos (si hay un número exponencial de posibles subexpresiones, enumerartodos de ellos es inherentemente exponencial, pero enumerar los primeros no debería serlo, y de manera similar para los reemplazos). Puede solucionar una u otra característica usando la otra, por lo que tener cualquiera de las dos es suficiente.muchísimos puntos de bonificación paratratar las expresiones regulares como valores de primera clase (para que pueda tomar la unión, la intersección, la concatenación, la negación, en particular la negación y la intersección, ya que son muy difíciles de realizar mediante la manipulación de cadenas de la definición de expresiones regulares)coincidencia perezosa es decir, la coincidencia en flujos ilimitados sin poner todo en la memoria es una ventaja. Si las secuencias no admiten la búsqueda, la captura de subexpresiones y / o reemplazos no es posible (en general) en una sola pasada.Backreferences están fuera, son fundamentalmente poco fiables; es decir, siempre puede exhibir un comportamiento exponencial dado los casos de entrada patológica.

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.