1. Inicio
  2. Pregunta y respuesta
  3. Peor análisis de casos para expresiones regulares

Peor análisis de casos para expresiones regulares

2011-01-19 19 views
48

¿Hay alguna herramienta que tome una expresión regular particular y devuelva el peor de los casos en términos del número de operaciones requeridas para un cierto número de caracteres con los que se compara la expresión regular?Peor análisis de casos para expresiones regulares

Entonces, por ejemplo, dado un (f|a)oo.*[ ]baz, ¿cuántos pasos podría hacer el motor para coincidir con 100 caracteres?

También me interesaría si hay una herramienta que puede tomar un montón de muestras de texto y mostrar las operaciones promedio para cada ejecución.

Me doy cuenta de que esto dependerá mucho del motor utilizado y de la implementación, pero ignoro qué tan común es esto. Entonces, si es común para muchos idiomas (lo que hace que mi pregunta sea demasiado vaga) estaría particularmente interesado en Perl y Python.

Fuente

2011-01-19 Kyle Brandt

+0

¡Excelente pregunta! Obviamente, dependerá de la expresión regular. Es bien sabido que las expresiones regulares puras (incluso el ejemplo '(x + x +) + y' al que se hace referencia más adelante) admiten un autómata de máquina de estado finito puro, pero que las bibliotecas de expresiones regulares comunes realmente implementan aquellas con retroceso, en gran parte para respaldar la fantasía cosas como el contexto. Una herramienta como usted describe sería excelente para atrapar http://en.wikipedia.org/wiki/Regular_expression_Denial_of_Service_-_ReDoS –

Respuesta

22

Regexbuddy's depurador muestra cuántos pasos tomará el motor para concluir la coincidencia o no en una muestra determinada. Más información en catastrophic backtracking y debugging regular expressions.

catastrophic backtracking shown in RegexBuddy

PS: No es gratuito pero ofrecen una garantía de devolución de 3 meses.

Fuente

2011-01-19 02:35:22 Himanshu

+1

Estaba jugando con eso, Jeff ha sido un fanático de esto: http://www.codinghorror.com /blog/2004/07/my-buddy-regex.html. Pero estaba pensando un poco más en programación y orientado a la optimización, si eso tiene sentido. –

11

Tenga en cuenta que depende del motor . Mientras que la teoría regex se basa en la teoría de autómatas rectos, la mayoría de los motores no son traducciones estrictas de esas teorías. Por esta razón, por ejemplo, algunos motores incurren en tiempo exponencial mientras que el procesamiento estricto de NFA no lo haría.

Fuente

2011-07-08 23:20:00

Cuestiones relacionadas

 Cuestiones relacionadas