Escribir un analizador para expresiones regulares

Question

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.

Por lo tanto, para enseñarme a mí mismo y comprender las expresiones regulares propiamente, he decidido hacer lo que siempre hago cuando trato de aprender algo; es decir, intente escribir algo ambicioso que probablemente abandonaré tan pronto como sienta que ya aprendí 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.

EDIT:. Debo aclarar que, si bien voy a poner en práctica el analizador de expresiones regulares en Python, no estoy demasiado exigente en cuanto a qué lenguaje de programación los ejemplos o artículos están escritos en la medida que no es en Brainfuck, probablemente entenderé lo suficiente como para que valga la pena.

Answer 1

Escribir una implementación de un motor de expresión regular es de hecho una tarea bastante compleja.

Pero si usted está interesado en la forma de hacerlo, incluso si usted no puede entender lo suficiente de los detalles a implementarlo en realidad, yo recomiendo que al menos vistazo a este artículo:

Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)

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 algún 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.

Answer 2

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 .^$*.

Answer 3

This paper tiene un enfoque interesante. La implementación se da en Haskell, pero ha sido reimplemented in Python al menos una vez.

Answer 4

Ya le he dado un +1 a Mark Byers, pero, por lo que recuerdo, el papel realmente no dice mucho sobre cómo funciona la expresión regular, además 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 describo (muy rápidamente) es el enfoque adoptado en Modern Compiler Design.

Imagine que tiene la siguiente expresión regular ...

a (b c)* d 

Las letras representan los caracteres literales a juego. 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 en el que nada se ha visto acompañado, sin embargo, por lo que el punto va en la parte delantera ...

0 : .a (b c)* d 

La única combinación posible es 'a', por lo que el siguiente estado es derivamos. ..

1 : a.(b c)* d 

ahora tenemos dos posibilidades - coincide con la 'b' (si hay al menos una repetición de 'b c') o coincide con la 'd' de otra manera. Nota: básicamente estamos haciendo una búsqueda de dígrafo 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. (B c) * 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 un operador, con el fin de simplificar el manejo del punto. Estado 1 se transforma en ...

1 : a.b c (b c)* d 
    a.d 

Es decir, su siguiente opción es o bien para que coincida con la primera repetición o para saltar 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).

EDIT 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 de 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 está cerrado en relación con nuestro conjunto de operadores de transición: el conjunto mínimo de estados alcanzables.

Mínimo aquí 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 obtener un tercero que representa la unión" (o intersección, o establecer 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 comunes 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.

Lo anterior probablemente sea un poco descuidado con las definiciones de WRT, 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.

BTW - eche un vistazo al resto de Dick Grunes site - 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.

Answer 5

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 Grammar examples y ejecutar a través de la AST y el analizador que genera. Genera un código realmente complicado pero tendrá una buena comprensión de cómo funciona un analizador.