probar - extraer cadenas con expresiones regulares java

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

Question

Tengo esta expresión ingenua "<([/ s] | [^ <]) +?>" (Sin incluir las comillas). Parece muy sencillo, pero en verdad es malo cuando funciona en contra del 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 algo parecido, 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>

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

Answer 1

El regex ([/s]|[^<]) en términos simples significa cualquier carácter individual que ES de espacio en blanco o IS NOT un carácter < , que es redundante porque los caracteres de espacio en blanco NO son un < carácter. Me parece que lo que realmente quieres decir es:

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

No estoy seguro si esto resolverá el ciclo infinito, pero pensé en señalarlo.

Answer 2

Otro problema (además de lo que Jan dijo) es que estás haciendo coincidir un personaje a la vez dentro del paréntesis, equivalente a este ejemplo simplificado:

(.)+

Cada vez que se ejecuta esta parte de la expresión regular, el motor de expresiones regulares tiene que guardar las posiciones de inicio y final de lo que haya correspondido con la subexpresión dentro de los parens, en caso de que necesite retroceder. Esto sería cierto incluso si fuera un grupo no capturante, es decir,

(?:.)+

... pero como se trata de un grupo de captura, se debe guardar aún más información. Pasar por todo eso por un personaje a la vez se vuelve realmente costoso. Casi nunca es correcto hacer coincidir un solo 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.

Answer 3

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

[/s]|[^<]

Lo que ocurre aquí es que cada carácter coincidente con / s también puede coincidir con [^ <]. Eso significa que hay dos formas de unir cada personaje de espacio en blanco. Si representamos las dos clases de caracteres con A y B:

A|B

Entonces, una cadena de tres espacios podría coincidir 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 de expresiones regulares que no tenga ninguna protección contra lo que llamo retroceso catastrófico .

Cuando utilice 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.