detalles de implementación de expresiones regulares

A question that I answered me hizo pensar:detalles de implementación de expresiones regulares

Cómo son expresiones regulares implementados en Python? ¿Qué tipo de garantías de eficiencia hay? ¿La implementación es "estándar" o está sujeta a cambios?

Pensé que las expresiones regulares se implementarían como DFA, y por lo tanto eran muy eficientes (requiriendo como máximo un escaneo de la cadena de entrada). Laurence Gonsalves planteó un punto interesante de que no todas las expresiones regulares de Python son regulares. (Su ejemplo es r "(a +) b \ 1", que coincide con cierta cantidad de a's, a b, y luego con el mismo número de a's que antes). Esto claramente no se puede implementar con un DFA.

Entonces, para reiterar: ¿cuáles son los detalles de implementación y las garantías de las expresiones regulares de Python?

También sería bueno si alguien pudiera dar algún tipo de explicación (a la luz de la implementación) sobre por qué las expresiones regulares "cat | catdog" y "catdog | cat" llevan a diferentes resultados de búsqueda en la cadena " catdog ", como se menciona en el question that I referenced before.

Fuente

2009-05-09 Tom

Las implementaciones de expresiones regulares actuales tienen muchas más características que las que describe la definición clásica de expresiones regulares. – Gumbo

@Gumbo: De hecho lo hacen ... esta es una de las razones de mi pregunta. Tengo curiosidad sobre una implementación específica porque realmente no es seguro asumir que se usa un DFA (debido a estas características adicionales). – Tom

Usa la fuente, Luke (http://svn.python.org/view/python/trunk/Lib/re.py?view=markup). En realidad parece bastante bien documentado. –

El módulo re de Python se basó en PCRE, pero ha pasado a su propia implementación.

Aquí está el enlace al C code.

Parece que la biblioteca se basa en un retroceso recursivo cuando se ha tomado una ruta incorrecta.

alt text

expresión y de texto de tamaño normal n
una? ⁿ un ⁿ búsqueda de un ⁿ

Tenga en cuenta que este gráfico no es representativo de las búsquedas normales de expresiones regulares.

http://swtch.com/~rsc/regexp/regexp1.html

Fuente

2009-05-09 23:03:17 Unknown

(me doy cuenta de que este comentario es tardío) Me gusta su explicación, excepto que no creo que la última parte sea correcta sobre la coincidencia de "cat | catdog". El uso de "cat | catdog" produce "cat" como resultado y "catdog | cat" produce "catdog" como resultado. Básicamente, el orden importa. Hay dos cosas pasando. En primer lugar, 'findall' solo encuentra todas las coincidencias que no se superponen. Entonces no deberías esperar "cat" Y "catdog". En segundo lugar, si estuviera implementando esto, creo que es fácil decir que el NFA se puede convertir a un DFA y entonces tendría "c -> a -> * t * -> d -> o -> * g *" donde los asteriscos denotan un estado final. – Tom

(continúa ...): Básicamente, la "t" es un estado final, y siento que la búsqueda siempre debe devolver "gato" porque es todo lo que necesita para encontrar una coincidencia. Sin embargo, tu respuesta fue útil, y voy a aceptarla (meses después :-). – Tom

Sin embargo, los DFA no son un enfoque perfecto. Coincidencia '[ab] * b [ab]^n' requiere' O (2^n) 'memoria usando un DFA, pero se puede hacer en tiempo lineal y memoria usando un NFA. –

no hay "garantías de eficiencia" en Python ER más que en cualquier otra parte del lenguaje (biblioteca estándar de C++ 's es el único lenguaje estándar generalizado Sé que intenta establecer esas normas - pero no hay estándares, incluso en C++, que especifiquen que, por ejemplo, multiplicar dos entradas debe tomar tiempo constante, o algo así); tampoco hay ninguna garantía de que las grandes optimizaciones no se apliquen en ningún momento.

Hoy, F. Lundh (originalmente responsable de implementar el actual módulo de RE de Python, etc.), presentando Unladen Swallow en Pycon Italia, mencionó que uno de los caminos que explorarán es compilar expresiones regulares directamente al código intermedio LLVM (en lugar de su propio código de bytes para ser interpretado por un tiempo de ejecución ad-hoc), dado que el código ordinario de Python también se está compilando para LLVM (en una versión próximamente inminente de Unladen Swallow), una RE y su código Python circundante podrían optimizarse juntos, incluso de formas bastante agresivas a veces. Sin embargo, dudo que algo así vaya a estar cerca de "listo para la producción" ;-).

Fuente

2009-05-10 21:01:56

Matching regular expressions with backreferences is NP-hard, que es al menos tan difícil como NP-Complete. Eso básicamente significa que es tan difícil como cualquier otro problema que puedas encontrar, y la mayoría de los informáticos piensan que podría requerir un tiempo exponencial en el peor de los casos.Si pudiera hacer coincidir esas expresiones "regulares" (que realmente no lo son, en el sentido técnico) en tiempo polinomial, podría ganar a million bucks.

Fuente

2009-10-28 04:24:21

detalles de implementación de expresiones regulares

Respuesta

Cuestiones relacionadas