python3 - python string expresiones regulares
Escribir un analizador para expresiones regulares (5)
Incluso después de años de programación, me da vergüenza decir que nunca he captado completamente las expresiones regulares. En general, cuando un problema requiere una expresión regular, normalmente puedo (después de un montón de referencias a la sintaxis) encontrar una adecuada, pero es una técnica que cada vez me recurro más a menudo.
Entonces, para enseñarme y comprender las expresiones regulares correctamente , he decidido hacer lo que siempre hago cuando trato de aprender algo; es decir, trate de escribir algo ambicioso que probablemente abandonaré tan pronto como sienta que he aprendido lo suficiente.
Para este fin, quiero escribir un analizador de expresiones regulares en Python. En este caso, "aprender lo suficiente" significa que quiero implementar un analizador sintáctico que pueda comprender la sintaxis de expresiones regulares extendida de Perl por completo. Sin embargo, no tiene que ser el analizador más eficiente o incluso necesariamente utilizable en el mundo real. Simplemente tiene que coincidir correctamente o no coincidir con un patrón en una cadena.
La pregunta es, ¿por dónde empiezo? No sé casi nada sobre cómo las expresiones regulares se analizan e interpretan aparte del hecho de que involucra de alguna manera un autómata de estado finito. Cualquier sugerencia sobre cómo abordar este problema bastante desalentador sería muy apreciada.
EDITAR: Debo aclarar que mientras voy a implementar el analizador de expresiones regulares en Python, no me preocupo demasiado por el lenguaje de programación en el que están escritos los ejemplos o los artículos. Mientras no esté en Brainfuck, probablemente entenderé lo suficiente. de eso para que valga la pena mi tiempo.
Escribir una implementación de un motor de expresión regular es de hecho una tarea bastante compleja.
Pero si está interesado en cómo hacerlo, incluso si no puede entender lo suficiente de los detalles para implementarlo realmente, le recomendaría que al menos observe este artículo:
Explica cuántos de los lenguajes de programación populares implementan expresiones regulares de una manera que puede ser muy lenta para algunas expresiones regulares, y explica un método ligeramente diferente que es más rápido. El artículo incluye algunos detalles de cómo funciona la implementación propuesta, incluido un código fuente en C. Puede ser un poco pesado leer si estás empezando a aprender expresiones regulares, pero creo que vale la pena saber acerca de la diferencia entre los dos enfoques.
Estoy de acuerdo en que escribir un motor de expresiones regulares mejorará la comprensión, pero ¿has echado un vistazo a ANTLR? Genera los analizadores automáticamente para cualquier tipo de lenguaje. Así que tal vez puedas probar tu mano tomando una de las gramáticas de lenguaje enumeradas en ejemplos de gramática y ejecutar a través de la AST y el analizador sintáctico que genera. Genera un código realmente complicado pero tendrá una buena comprensión de cómo funciona un analizador.
Hay un capítulo interesante (aunque ligeramente corto) en Beautiful Code por Brian Kernighan, apropiadamente llamado "A Regular Expression Matcher". En él, analiza un marcador simple que puede hacer coincidir caracteres literales, y los símbolos. .^$* .
Ya le he dado un +1 a Mark Byers, pero hasta donde recuerdo, el documento en realidad no dice mucho sobre cómo funciona el emparejamiento de expresión regular más allá de explicar por qué un algoritmo es malo y otro mucho mejor. Tal vez algo en los enlaces?
Me centraré en el buen enfoque: crear autómatas finitos. Si se limita a autómatas deterministas sin minimización, esto no es realmente demasiado difícil.
Lo que describiré (muy rápidamente) es el enfoque adoptado en Modern Compiler Design .
Imagina que tienes la siguiente expresión regular ...
a (b c)* d
Las letras representan caracteres literales para unir. El * es el partido normal de repeticiones cero o más. La idea básica es derivar estados basados en reglas de puntos. Estado cero, tomaremos como el estado donde no se ha hecho coincidir nada, por lo que el punto va al frente ...
0 : .a (b c)* d
La única coincidencia posible es ''a'', por lo que el siguiente estado que derivamos es ...
1 : a.(b c)* d
Ahora tenemos dos posibilidades: hacer coincidir la ''b'' (si hay al menos una repetición de ''b c'') o unir la ''d'' de lo contrario. Nota: básicamente estamos haciendo una búsqueda de dígrafos aquí (ya sea en profundidad primero o ancho primero o lo que sea) pero estamos descubriendo el dígrafo mientras lo buscamos. Suponiendo una estrategia de amplitud, tendremos que poner en cola uno de nuestros casos para su posterior consideración, pero a partir de ahora voy a ignorar ese problema. De todos modos, hemos descubierto dos nuevos estados ...
2 : a (b.c)* d
3 : a (b c)* d.
El estado 3 es un estado final (puede haber más de uno). Para el estado 2, solo podemos hacer coincidir la ''c'', pero debemos tener cuidado con la posición del punto después. Obtenemos "a. (Bc) * d", que es lo mismo que el estado 1, por lo que no necesitamos un nuevo estado.
IIRC, el enfoque en Modern Compiler Design es traducir una regla cuando se golpea a un operador, con el fin de simplificar el manejo del punto. El estado 1 se transformaría en ...
1 : a.b c (b c)* d
a.d
Es decir, su próxima opción es hacer coincidir la primera repetición u omitir la repetición. Los siguientes estados a partir de esto son equivalentes a los estados 2 y 3. Una ventaja de este enfoque es que puedes descartar todas tus partidas pasadas (todo antes del ''.'') Ya que solo te importan las futuras parejas. Esto generalmente da un modelo de estado más pequeño (pero no necesariamente uno mínimo).
EDITAR Si descarta detalles coincidentes, la descripción de su estado es una representación del conjunto de cadenas que pueden ocurrir a partir de este momento.
En términos de álgebra abstracta, este es un tipo de cierre conjunto. Un álgebra es básicamente un conjunto con uno (o más) operadores. Nuestro conjunto es de descripciones de estado, y nuestros operadores son nuestras transiciones (coincidencias de personajes). Un conjunto cerrado es aquel en el que aplicar cualquier operador a cualquier miembro del conjunto siempre produce otro miembro que está en el conjunto. El cierre de un conjunto es el conjunto más pequeño que está cerrado. Entonces, básicamente, comenzando con el estado de inicio obvio, estamos construyendo el conjunto mínimo de estados que se cierra en relación con nuestro conjunto de operadores de transición: el conjunto mínimo de estados alcanzables.
Aquí, el mínimo se refiere al proceso de cierre: puede haber un autómata equivalente más pequeño que normalmente se conoce como mínimo.
Con esta idea básica en mente, no es demasiado difícil decir "si tengo dos máquinas de estados que representan dos conjuntos de cadenas, cómo derivaré una tercera que representa la unión" (o intersección, o establece la diferencia ...). En lugar de reglas de puntos, las representaciones de su estado mostrarán un estado actual (o conjunto de estados actuales) de cada autómata de entrada y tal vez detalles adicionales.
Si tus gramáticas regulares se vuelven complejas, puedes minimizarlas. La idea básica aquí es relativamente simple. Agrupe todos sus estados en una clase de equivalencia o "bloque". Luego, prueba repetidamente si necesita dividir bloques (los estados no son realmente equivalentes) con respecto a un tipo de transición en particular. Si todos los estados en un bloque en particular pueden aceptar una coincidencia del mismo carácter y, al hacerlo, llegar al mismo bloque siguiente, son equivalentes.
El algoritmo Hopcrofts es una forma eficiente de manejar esta idea básica.
Una cosa particularmente interesante acerca de la minimización es que cada autómata finito determinista tiene precisamente una forma mínima. Además, el algoritmo de Hopcrofts producirá la misma representación de esa forma mínima, sin importar qué representación de qué caso más grande haya comenzado. Es decir, esta es una representación "canónica" que se puede usar para derivar un hash o para ordenamientos arbitrarios pero consistentes. Lo que esto significa es que puede usar autómatas mínimos como claves en contenedores.
Probablemente, las anteriores definiciones de WRT son un poco descuidadas, así que asegúrese de buscar los términos usted mismo antes de usarlos usted mismo, pero con un poco de suerte, esto le dará una rápida introducción a las ideas básicas.
Por cierto, eche un vistazo al resto del sitio de Dick Grunes , tiene un libro en PDF gratuito sobre técnicas de análisis sintáctico. La primera edición de Modern Compiler Design es bastante buena IMO, pero como verá, hay una segunda edición inminente.
Este documento tiene un enfoque interesante. La implementación se da en Haskell, pero se ha vuelto a implementar en Python al menos una vez.