¿Por qué esta expresión regular mata al motor de expresiones regulares de Java?

Question

Tengo esta expresión ingenua "< ([\ s] | [^ <]) +?>" (Sin incluir las comillas). Parece tan sencillo pero de hecho es malo cuando funciona contra el texto HTML a continuación. Envía el motor de expresiones regulares de Java a un bucle infinito.

Tengo otra expresión regular ("<. +?>"), Que hace más o menos lo mismo, pero no mata nada. ¿Sabes por que pasa esto?

<script language="JavaScript" type="text/javascript"> 
     var numDivs, layerName; 
     layerName = "lnavLayer"; 
     catLinkName = "category"; 
     numDivs = 2; 
     function toggleLayer(layerID){ 
      if (!(navigator.appName == "Netscape" && navigator.appVersion.substr(0, 1) < 5)){ 
       thisLayer = document.getElementById(layerName + layerID); 
       categoryLink = document.getElementById(catLinkName + layerID); 
       closeThem(); 
       if (thisLayer.className == 'subnavDefault'){ 
        thisLayer.className = 'subnavToggled'; 
        categoryLink.className = 'leftnavLinkSelectedSection'; 
       } 
      } 
     } 
     function closeThem(){ 
      for(x = 0; x < numDivs; x++){ 
       theLayer = document.getElementById(layerName + (x 
+ 1)); 
       thecategoryLink = document.getElementById(catLinkName + (x + 1)); 
       theLayer.className = 'subnavDefault'; 
       thecategoryLink.className = 'leftnavLink'; 
      } 
     } var flag = 0; var lastClicked = 0 
    //--> 
    </script> 

aún mantiene un bucle con una herramienta de expresiones regulares de Java en línea (como www.fileformat.info/tool/regex.htm) o una utilidad como RegexBuddy.

Answer 1

La razón por la que el motor de expresiones regulares de Java se bloquea es que esta parte de su expresión regular provoca un desbordamiento de pila (de verdad!):

[\s]|[^<] 

Lo que sucede aquí es que cada personaje acompañado de \ s también puede ir acompañada de [^ <]. Eso significa que hay dos formas de unir cada personaje de espacio en blanco. Si representamos las dos clases de personajes con A y B:

A|B 

A continuación, una serie de tres espacios podría ser igualado como AAA, AAB, ABA, ABB, BAA, BAB, BBA, o BBB. En otras palabras, la complejidad de esta parte de la expresión regular es 2^N. Esto matará cualquier motor regex que no tenga ninguna protección contra lo que yo llamo catastrophic backtracking.

Al usar la alternancia (barra vertical) en una expresión regular, siempre asegúrese de que las alternativas sean mutuamente excluyentes. Es decir, como máximo se puede permitir que una de las alternativas coincida con cualquier bit de texto dado.

Answer 2

La expresión regular ([\s]|[^<]) en términos simples significa cualquier carácter individual que ES de espacio en blanco o NO ES un carácter <, que es redundante porque los caracteres de espacio en blanco NO son un carácter <. Me parece que lo que realmente quiere decir es:

`"<([^<])+?>"` 

No estoy seguro de si esto va a resolver el bucle infinito, pero pensé que me gustaría señalar esto.

Answer 3

Otro problema (además de lo que dijo Jan) es que estás a juego un carácter a la vez dentro de los paréntesis, equivalente a este ejemplo simplificado:

(.)+ 

Cada vez que esta parte de la expresión regular es ejecutado, el motor de expresiones regulares tiene que guardar las posiciones de inicio y final de lo que fue igualado por la subexpresión dentro de los parens, en caso de que necesite retroceder. Esto sería cierto incluso si se tratara de un grupo sin fines de captura, es decir,

(?:.)+ 

... sino porque se trata de un grupo de captura, aún más información tiene que ser salvado. Pasar por todo eso por un personaje a la vez se vuelve realmente costoso. Casi nunca es correcto hacer coincidir un único carácter dentro de un grupo entre paréntesis con un cuantificador * o + en el grupo. Además, debe usar grupos de captura solo cuando necesite capturar algo; de lo contrario, use la variedad que no captura.