整体已整理成思维导图:
字母[a-zA-Z],数字[0-9],下划线[_],汉字。标点符号等
用 NFA 自动机实现的比较复杂的正则表达式,在匹配过程中经常会引起回溯问题。大量的回溯会长时间地占用 CPU,从而带来系统性能开销。
下面以如下为例:
// 待匹配字符串
text = "abbc";
// 正则表达式
regex = "ab{1,3}c";
NFA 自动机对其解析如下:
a
和字符串第一个字符 a
进行比较,a
对 a
,匹配。b{1,3}
和字符串的第二个字符 b
进行比较,匹配。b{1,3}
表示 1-3 个 b 字符串,NFA 自动机又具有贪婪特性,所以此时不会继续读取正则表达式的下一个匹配符,而是依旧使用 b{1,3}
和字符串的第三个字符b
进行比较,结果还是匹配。b{1,3}
和字符串的第四个字符 c
进行比较,发现不匹配了,此时就会发生回溯,已经读取的字符串第四个字符 c
将被吐出去,指针回到第三个字符 b 的位置。c
,和字符串中的第四个字符 c
进行比较,结果匹配,结束。在数量匹配中,如果单独使用 +、 ? 、* 或{min,max} 等量词,正则表达式会匹配尽可能多的内容
对于如下实例:
// 待匹配字符串
text = "abbc";
// 正则表达式
regex = "ab{1,3}?c";
在网上搜到一篇[《藏在正则表达式里的陷阱》,里面说懒惰模式也会有回溯,具体如下:
a
与 字符串第一个字符 a 匹配,匹配成。b{1,3}?
和 字符串第二个字符 b 匹配,匹配成功。c
与字符串第三个字符 b
匹配,发现不匹配。b{1,3}?
和字符串第三个字符 b
匹配,匹配成功。c
与字符串第四个字符 c
匹配,匹配成功。于是结束。询问《Java性能调优实战》专栏的老师被告知与贪婪模式的区别在于它不会使用b{1,3}
与c
匹配,在匹配完成abb
之后,会使用regex中的c
匹配text中的c
。
贪婪模式会引起回溯问题,可用独占模式避免
分支选择类型“(X|Y|Z)”的表达式会降低性能,尽量减少使用。
()
就是一个捕获组,捕获组可以进行嵌套。(?:exp)
组成。public static void main( String[] args ){
String text = "<input high=\"20\" weight=\"70\">test</input>";
// reg有三个捕获组:(<input.*?>)、(.*?)、(</input>)
String reg="(<input.*?>)(.*?)(</input>)";
// regOfNot有两个非捕获组:(?:<input.*?>)和(?:</input>),一个捕获组:(.*?)
String regOfNot="(?:<input.*?>)(.*?)(?:</input>)";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while(m.find()) {
// group用来提取()分组截获的字符串
System.out.println(m.group(0));// 整个匹配到的内容
System.out.println(m.group(1));//(<input.*?>)
System.out.println(m.group(2));//(.*?)
System.out.println(m.group(3));//(</input>)
}
}
最后推荐个可以检查写的正则表达式和对应的字符串匹配时会不会有问题的网站: Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript 。