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

Question

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

Answer 1

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

[\s]|[^<]

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

A|B

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

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

Answer 2

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

(.)+

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

(?:.)+

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

Answer 3

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

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

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