java - 为什么java的Regex有时会抛出stackoverflow异常？

Question

我正在尝试为 HTML 标签创建一个正则表达式。到目前为止我创建的正则表达式是 <(/?)(\w+?)(\s(.*?))*?((/>)|>) ，当我在线测试它时，它运行良好；但是当我使用 Java 正则表达式对其进行测试时，它有时会抛出 StackOverFlowError，有时则不会。

我正在使用这段代码进行测试:

public static void parseHtml(String urlString){
    new Thread(new Runnable() {
        @Override
        public void run() {
            int count = 0;
            int count2 = 0;
            String htmlScript = downloadWebPage(urlString);
            Matcher matcher = Pattern.compile("<(/?)(\\w+?)(\\s(.*?))*?((/>)|>)",
                                              Pattern.DOTALL).matcher(htmlScript);
            while(matcher.find()) {
                System.out.println(matcher.group());
            }
        }
    }).start();
}

所以，我的问题是: 为什么 Java 的正则表达式引擎有时会抛出 StackOverFlowError 而有时不会？

注意:我使用了相同的测试输入(相同的 URL)，它抛出了错误，稍后再次测试它并且运行良好。

Answer 1

我认为 Java 在某些情况下不喜欢交替
存在潜在回溯问题的地方。

所以，这部分(\s(.*?))*?在回溯上造成撤销负担
机制。

 (                             # (3 start)
      \s
      ( .*? )                       # (4)
 )*?                           # (3 end)

最终结果是一个嵌套的可选量词。
可以简化为([\S\s]*?)没有嵌套问题。

另外，这部分((/>)|>)可以减少到(/?>)消除需要
通过交替获取另一个堆栈框架。

总的来说，您并不真的需要捕获组。

---

如果只是需要解析标签，这是html的初始级别
解析，然后使用正则表达式就可以了。

如果您想做的不仅仅是解析单个标签，则需要 DOM 解析器。

我发现这个正则表达式将解析所有单独的 html/xml 标签。

https://regex101.com/r/YXhCxe/1

"<(?:(?:(?:(script|style|object|embed|applet|noframes|noscript|noembed)(?:\\s+(?>\"[\\S\\s]*?\"|'[\\S\\s]*?'|(?:(?!/>)[^>])?)+)?\\s*>)[\\S\\s]*?</\\1\\s*(?=>))|(?:/?[\\w:]+\\s*/?)|(?:[\\w:]+\\s+(?:\"[\\S\\s]*?\"|'[\\S\\s]*?'|[^>]?)+\\s*/?)|\\?[\\S\\s]*?\\?|(?:!(?:(?:DOCTYPE[\\S\\s]*?)|(?:\\[CDATA\\[[\\S\\s]*?\\]\\])|(?:--[\\S\\s]*?--)|(?:ATTLIST[\\S\\s]*?)|(?:ENTITY[\\S\\s]*?)|(?:ELEMENT[\\S\\s]*?))))>"

展开

 <
 (?:
      (?:
           (?:
                # Invisible content; end tag req'd
                (                             # (1 start)
                     script
                  |  style
                  |  object
                  |  embed
                  |  applet
                  |  noframes
                  |  noscript
                  |  noembed 
                )                             # (1 end)
                (?:
                     \s+ 
                     (?>
                          " [\S\s]*? "
                       |  ' [\S\s]*? '
                       |  (?:
                               (?! /> )
                               [^>] 
                          )?
                     )+
                )?
                \s* >
           )

           [\S\s]*? </ \1 \s* 
           (?= > )
      )

   |  (?: /? [\w:]+ \s* /? )
   |  (?:
           [\w:]+ 
           \s+ 
           (?:
                " [\S\s]*? " 
             |  ' [\S\s]*? ' 
             |  [^>]? 
           )+
           \s* /?
      )
   |  \? [\S\s]*? \?
   |  (?:
           !
           (?:
                (?: DOCTYPE [\S\s]*? )
             |  (?: \[CDATA\[ [\S\s]*? \]\] )
             |  (?: -- [\S\s]*? -- )
             |  (?: ATTLIST [\S\s]*? )
             |  (?: ENTITY [\S\s]*? )
             |  (?: ELEMENT [\S\s]*? )
           )
      )
 )
 >