Почему это регулярное выражение убивает механизм регулярных выражений Java?

У меня есть это наивное регулярное выражение "< ([\ s] | [^ <]) +? > " (исключая кавычки). Кажется так но это действительно зло, когда оно работает против текста ниже HTML. Он отправляет механизм регулярного выражения Java в бесконечный цикл.

У меня есть другое регулярное выражение ( "<. +? > " ), которое делает что-то одно и то же, но оно ничего не убивает. Вы знаете, почему это происходит?

<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>

он даже продолжает цикл с онлайн-инструментом Java regex (например, www.fileformat.info/tool/regex.htm) или утилитой вроде RegexBuddy.

Ответ 1

Причина, по которой запускается механизм Java regex, состоит в том, что эта часть вашего регулярного выражения вызывает переполнение стека (действительно!):

[\s]|[^<]

Что здесь происходит, так это то, что каждый символ, сопоставляемый \s, также может быть сопоставлен [^ <]. Это означает, что есть два способа сопоставления каждого символа пробела. Если мы представляем два символьных класса с A и B:

A|B

Затем строка из трех пространств может быть сопоставлена как AAA, AAB, ABA, ABB, BAA, BAB, BBA или BBB. Другими словами, сложность этой части регулярного выражения равна 2 ^ N. Это убьет любой механизм регулярных выражений, который не имеет каких-либо гарантий против того, что я называю катастрофический откат.

При использовании чередования (вертикальная полоса) в регулярном выражении всегда убедитесь, что альтернативы являются взаимоисключающими. То есть, по крайней мере, одна из альтернатив может быть разрешена для соответствия любому заданному биту текста.

Ответ 2

Регулярное выражение ([\s]|[^<]) в простых выражениях означает любой одиночный символ, который является белым пространством или не является символом <, который является избыточным, поскольку символы пробела не являются символами <. Мне кажется, что вы действительно имеете в виду:

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

Я не уверен, что это решит бесконечный цикл, но я подумал, что хочу указать на это.

Ответ 3

Другая проблема (в дополнение к тому, что сказал Ян) заключается в том, что вы сопоставляете один символ за раз внутри скобок, что эквивалентно этому упрощенному примеру:

(.)+

Каждый раз, когда эта часть регулярного выражения выполняется, движок регулярных выражений должен сохранять начальную и конечную позиции того, что соответствовало подвыражению внутри парнеров, в случае, если ему нужно отступить. Это было бы правдой, даже если бы это была не захватывающая группа, то есть

(?:.)+

... но поскольку это группа захвата, необходимо сохранить еще больше информации. Прохождение всего того, что для одного персонажа за один раз становится действительно дорогим. Он почти никогда не подходит для соответствия одному символу внутри группы в скобках с квантором * или + в группе. Кроме того, вы должны использовать группы захвата только тогда, когда вам нужно что-то захватить; в противном случае используйте неконвертируемый сорт.