El motor de expresiones regulares por dentro, como biblioteca

• Existe un autor del regex crate de Rust que ha mejorado y optimizado la biblioteca de expresiones regulares de Rust.
• Se creó un nuevo crate llamado regex-automata que expone el interior del regex crate como una API separada.
• Esta es la primera biblioteca de expresiones regulares que expone tanto su interior como una biblioteca versionada aparte.
• Este artículo ofrece una guía sobre el proceso de reescritura para mejorarla, cómo se resolvieron los problemas y la API de regex-automata.
• El público objetivo son programadores de Rust y cualquier persona interesada en cómo se implementan los motores de expresiones regulares con autómatas finitos.
• El artículo ofrece una breve historia de regex crate y su desarrollo.
• Entre los problemas que enfrentaba regex crate estaban la configuración, las pruebas, ciertas solicitudes de API y la necesidad de un DFA completamente compilado.
• La reescritura resuelve estos problemas y ofrece una solución más flexible y optimizada.
• Al publicar regex-automata como un crate separado, se hace posible experimentar y desarrollar APIs adicionales sin volver confuso el crate principal regex.
• El artículo destaca las ventajas de usar regex-automata y su potencial de mejora en el campo de los motores de expresiones regulares.
• El artículo describe el programa regex-cli, que proporciona acceso por línea de comandos a la API de regex crate.
• Este programa incluye utilidades como serializar un DFA compilado a un archivo y generar código Rust.
• El artículo muestra ejemplos del impacto de Unicode en los patrones de expresiones regulares.
• El programa regex-cli puede depurar e imprimir varios tipos de datos del ecosistema de regex crate.
• Existe un comando regex-cli find que puede ejecutar búsquedas de múltiples patrones usando grupos de captura.
• El artículo explica el flujo de datos a través del motor de expresiones regulares, desde el análisis del patrón hasta la construcción del NFA.
• La extracción de literales es una técnica de optimización importante usada en regex crate.
• La extracción de literales consiste en extraer literales de un patrón de expresión regular para identificar rápidamente coincidencias candidatas en el haystack.
• Elegir qué literales buscar es importante para minimizar falsos positivos y reducir la latencia.
• La extracción de literales es un proceso heurístico para minimizar los falsos positivos y el impacto en la latencia.
• Una guía para la extracción de literales es priorizar literales más largos y evitar los extremadamente cortos o comunes.
• El artículo explica la optimización de secuencias literales en expresiones regulares.
• Una secuencia literal es una sucesión de cadenas tratadas como cadenas de coincidencia exacta.
• Durante la optimización, se identifican secuencias que pueden hacerse infinitas para mejorar el rendimiento.
• El artículo explica cómo distintas expresiones regulares pueden generar distintas secuencias literales.
• El artículo también analiza el proceso de buscar literales en el haystack.
• Se usan algoritmos diferentes para la búsqueda de una sola subcadena y de múltiples subcadenas.
• El artículo introduce el concepto de los NFA (autómatas finitos no deterministas) y su papel en los motores de expresiones regulares.
• Los NFA pueden transformarse en otros tipos, por ejemplo para implementar DFA (autómatas finitos deterministas).
• El artículo proporciona y explica ejemplos detallados de los componentes de un NFA.
• El artículo menciona optimizaciones en el nuevo compilador de NFA para reducir el uso de transiciones epsilon.
• El nuevo compilador de NFA optimiza la representación del NFA usando estados dispersos que incluyen múltiples rangos de bytes.
• Esta optimización reduce la sobrecarga y elimina la necesidad de transiciones epsilon.
• El NFA orientado a bytes usado en el compilador anterior era lento y requería compilaciones separadas para Unicode y para NFA orientado a bytes.
• El nuevo compilador de NFA integra autómatas UTF-8 en el NFA orientado a bytes para manejar clases Unicode.
• El nuevo compilador usa el algoritmo de Daciuk para calcular DFA mínimos a partir de secuencias ordenadas de elementos no anidados.
• Las transiciones inversas se manejan usando una estructura de datos especial llamada range trie.
• El nuevo compilador de NFA genera NFA con menos estados y sin transiciones epsilon en comparación con el compilador anterior.
• Se puede usar una optimización de reducción inversa para disminuir aún más el tamaño del NFA, aunque aumenta el tiempo de construcción.
• En general, el nuevo compilador de NFA mejora el rendimiento y simplifica el manejo de clases Unicode en expresiones regulares.
• El artículo analiza problemas técnicos relacionados con la codificación de caracteres.
• El problema está relacionado con caracteres dispersos y su representación en distintos formatos de codificación.
• El artículo menciona caracteres específicos y su frecuencia en sus respectivas codificaciones.
• El artículo resalta la complejidad de la codificación de caracteres y los posibles desafíos que plantea.
• El artículo puede ser interesante para ingenieros de software y desarrolladores que trabajan con codificación de caracteres.
• El artículo analiza técnicas de optimización de NFA en motores de expresiones regulares.
• Se sabe que el NFA de Thompson escala mal debido a las transiciones epsilon.
• El artículo presenta una optimización de NFA que reduce las transiciones epsilon al limitar la alternancia de literales.
• El nuevo compilador de NFA crea un trie de literales y lo convierte en un NFA con transiciones epsilon minimizadas.
• Esta optimización mantiene la prioridad de la coincidencia más a la izquierda y mejora el rendimiento de búsqueda.
• El artículo también menciona trabajo futuro sobre el NFA de Glushkov y sobre almacenar los NFA en una sola asignación contigua.
• El regex crate de Rust usa varios motores de expresiones regulares para equilibrar funcionalidad y rendimiento de búsqueda.
• PikeVM es el motor de expresiones regulares más potente del crate y admite todas las funciones de regex.
• PikeVM simula el NFA

[GN⁺]

Comentarios en Hacker News

• El crate regex de Rust es legendario y una herramienta valiosa para la comunidad.
• Este artículo profundizó en los cambios y mejoras del crate regex.
• Las expresiones regulares son una herramienta poderosa que puede realizar tareas complejas con rapidez.
• En este artículo se recomendó un libro para dominar las expresiones regulares.
• En 2001, el editor Komodo tenía un depurador de expresiones regulares de vanguardia.
• Ripgrep es una herramienta que le da vida a la búsqueda en código y archivos de texto.
• Un comentarista propuso ampliar la funcionalidad de las expresiones regulares para que pueda usarse con listas en lugar de solo cadenas.
• El crate regex-automata es compatible con todas las estructuras de datos de texto.
• Un comentarista elogió el trabajo de BurntSushi y expresó su agradecimiento.
• Automa.jl es un motor de expresiones regulares puro de Julia que permite insertar código arbitrario de Julia.