为什么这个正则表达式会杀死Java正则表达式引擎？

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]|[^<]

这里发生的是每个匹配的字符也可以匹配[^ <].这意味着有两种方法可以匹配每个空白字符.如果我们用A和B表示两个字符类:

A|B

然后可以将三个空格的串匹配为AAA,AAB,ABA,ABB,BAA,BAB,BBA或BBB.换句话说,这部分正则表达式的复杂性是2 ^ N. 这会杀死任何没有任何保护措施的正则表达式引擎,这些保护措施不会对我称之为灾难性的回溯.

在正则表达式中使用交替(垂直条)时,请始终确保备选方案是互斥的.也就是说,最多可以允许一个替代方案匹配任何给定的文本位.