Почему это регулярное выражение убивает движок Java regex?

У меня есть это наивное регулярное выражение "<([\ 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 (например, http://www.fileformat.info/tool/regex.htm) или утилитой вроде RegexBuddy.

Источник

3 ответа

Решение

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

[\s]|[^<]

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

A|B

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

При использовании чередования (вертикальная черта) в регулярном выражении всегда убедитесь, что альтернативы являются взаимоисключающими. That is, at most one of the alternatives may be allowed to match any given bit of text.

Источник

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

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

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

Источник

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

(.)+

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

(?:.)+

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

Источник
Другие вопросы по тегам