regex - valida - Construyendo un motor de expresiones regulares: ¿recursos en línea?
valida regex online (9)
Creo que el artículo How Regexes Work de Mark-Jason Dominus es excelente. Está dirigido a personas que no son programadores, pero está escrito de una manera muy algorítmica y, por lo tanto, se puede utilizar para implementar dicho motor, especialmente si tiene alguna experiencia con la compilación. Lo he hecho yo mismo.
El artículo también menciona consejos y trucos más avanzados, y tiene cierta información sobre las limitaciones del motor.
Estoy interesado en crear un motor de expresiones regulares, como un proyecto paralelo, solo para fines de aprendizaje.
Conozco la teoría detrás de la evaluación de expresiones regulares, y tengo una comprensión suficiente de las máquinas de estados finitos, etc.
Lo que me interesa es cómo se implementa un motor de expresiones regulares en el software. Así que me preguntaba si había algún tipo de tutorial o recurso en línea que explicara la implementación de un motor de expresiones regulares, la traducción de la expresión regular a un FSM y demás. No quiero ningún sitio que simplemente explique la teoría detrás de esto.
Gracias.
El quinto capítulo de Algorithms de Robert Sedgewick es una muy buena introducción al tema. Explica qué es una NFA y cómo se puede construir una NFA a partir de una expresión regular. Los ejemplos tienen visuales y son muy claros. Incluso tiene un código para un reproductor de expresiones regulares simple. Y hay algunos ejercicios para implementar más características de expresiones regulares.
En el primer capítulo de Beautiful Code ( Amazon , borrador en línea ), Brian Kernighan habla sobre el elegante y muy pequeño regex matcher de Rob Pike. Es realmente simple, pero Kernighan le da siete ejercicios para extenderlo, lo cual podría ser una buena introducción para usted.
Llego tarde a la fiesta, pero esta asignación de curso de WSU me pareció la más útil al presentar una implementación de motor regex a un alto nivel. No sé C, así que fue bueno que el material se presentara en un formato independiente del idioma. Es importante destacar que hace un gran trabajo al explicar:
- Por qué usar la notación postfix
- Qué es la pila de fragmentos de NFA
- El algoritmo postfix-a-NFA en pseudocódigo
- La estructura de datos NFA
Además, encontré el artículo del profesor Pace útil en la implementación del método re2post mencionado por WSU y Cox.
Yo recomendaría leer el artículo de WSU primero y luego el artículo de Russ Cox para más profundidad.
Para los lectores alemanes, el capítulo tres "Pattern-Matching-Algorithmen für einfache Strings" de " Algorithmen auf Sequenzen " podría ser interesante. El autor es el Prof. Dr. Sven Rahmann, Lehrstuhl XI, Fakultät für Informatik, TU Dortmund. Todos los algoritmos tienen ejemplos de Python.
Si te sientes cómodo con C, probablemente te beneficie mirar el código fuente de las expresiones regulares compatibles con Perl .
Tengo 2 enlaces interesantes para los mecanismos de expresiones regulares,
otra implementación simple y clara (C, menos 500 líneas) RecursiveRegexpRaptor
Russ Cox tiene una buena colección de artículos sobre Implementación de Expresiones Regulares , especialmente su artículo Regular Expression Matching Puede Ser Simple y Rápido, vale la pena leerlo.