• 欢迎来到Compiler网站,如果对网站内容感兴趣或者帮助到你,请为文章点赞,谢谢!

Java正则表达式

java 奔跑的蜗牛 2个月前 (04-21) 44次浏览 0个评论 扫描二维码

Java正则表达式使用的引擎实现是NFA自动机, 这种正则表达式引擎在进行字符匹配时会发生回溯(backtracking)。而一旦发生回溯, 那其消耗的时间就会变得很长, 有可能是几分钟,也有可能是几个小时, 时间取决于回溯的次数和复杂度.

正则表达式引擎

正则表达式引擎有两种实现方式: DFA自动机(Deterministic Final Automata 确定型有穷自动机)NFA自动机(Non Deterministic Finite Automation 不确定性有穷自动机)

  • DFA自动机

    • 时间复杂度是线性的, 更加稳定,但是功能有限

  • DFA自动机

    • 时间复杂度不稳定,有时候好,有时候坏。取决于正在则表达式的书写.

    • 功能强大

NFA自动机运行原理

text = "Today is a nice day"
regex = "day"

NOTE: NFA是以正则表达式为基准去匹配的。也就是说, NFA自动机读取正则表达式的一个一个字符, 然后拿去和目标字符串匹配, 匹配成功就换正则表达式的下一个字符, 否则继续和目标字符串的下一个字符比较。

  • 首先, 拿到正则表达式第一个匹配符d. 浴室拿去和字符串进行比较

    • 字符串第一个字符为T, 不匹配,换下一个

    • 第二个是o, 也不匹配

    • 第三个是d, 匹配了成功, 并读取匹配规则的第二个字符a

  • 读取到正则表达式的第二个匹配符:a, 拿着这个匹配符和字符串的第四个字符串a比较,匹配成功。紧接着读取正则表达式的第三个字符:y

  • 读取到正则表达式的第三个匹配符:y. 用匹配符和字符串的第五个字符y比较, 又匹配了。尝试读取正则表达式的下一个字符, 读取完毕, 匹配结束.

NFA自动机的回溯

text = "abbc";
regex="ab{1,3}c"

上面的例子中, 执行过程如下

  • 首先, 读取正则表达式第一个匹配符a和字符串第一个字符a进行比较, 匹配了。于是读取正则表达式第二个字符.

  • 读取正则表达式第二个匹配b{1,3}和字符串的第二个字符b比较, 匹配了。但因为b{1,3}表示1-3个b字符串,以及NFA自动机的贪婪特性(也就是说要尽可能多地匹配), 所以此时并不会再去读取下一个正则表达式的匹配符,而是依旧使用b{1,3}和字符串的第三个字符b比较, 发现还是匹配.于是继续使用b{1,3}和字符串的第四个字符串c比较, 发现不匹配了,此时就会发生回溯

  • 发生回溯后, 我们已经读取的字符串第四个字符c将被吐出去, 指针回到第三个字符串的位置。之后, 程序读取表达式下一个操作符c, 读取当前指针的下一个字符c进行对比, 发现匹配。 于是读取下一个操作符。

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\/])+$

需要匹配的url链接为:

http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf

这个正则表达式分为三个部分:

  • 第一部分: 检验协议. ^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)

  • 第二部分: 检验域名. (([A-Za-z0-9-~]+).)+

  • 第三部分: 检验参数. ([A-Za-z0-9-~\/])+$

通过上面正则表达式检验协议http://这部分是没有问题的, 但是在校验www.fapiao.com的时候, 使用了xxx.这种方式去校验,

  • 匹配到www.

  • 匹配到fapiao.

  • 匹配到com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf, 因为贪婪匹配的原因, 所以程序会一直读后面的字符串进行匹配, 最后发现没有点号, 于是就一个个字符回溯回去.

另外一个问题是正则表达式的第三部分, 我们发现出现问题的URL是有下划线(_)和百分号(%)的,但是第三部分的正则表达式里面却没有. 这样就会导致前面匹配了一长串的字符之后, 发现不匹配, 最后回溯回去。

解决上述问题

public static void main(String[] args) {
   String badRegex = "^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~_%\\/])+$";
   String bugUrl = "http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";
   if (bugUrl.matches(badRegex)) {
       System.out.println("match!!");
  } else {
       System.out.println("no match!!");
  }
}

正则表达式三种模式

正则表达式中有三种模式:贪婪模式,懒惰模式,独占模式

在关于数量匹配中, 有+,?,*,{min, max}四种, 如果只是单独使用, 默认使用贪婪模式

如果在他们之后多加一个?符号, 那么原先的贪婪模式就汇变成懒惰模式, 极可能少地匹配. 但是懒惰模式还是会发生回溯现象的。

text="abbc"
regex="ab{1,3}?c"
  • 正则表达式的第一个操作符a与字符串第一个字符a匹配, 匹配成功。

  • 正则表达式第二个操作符b{1,3}?和字符串第二个字符串b匹配, 匹配成功

  • 因为最小匹配原则, 所以拿正则表达式第三个操作符c与字符串第三个字符b匹配, 发现不匹配

  • 回溯操作, 拿正则表达式第二个操作符b{1,3}?和第三个字符b匹配, 匹配成功

  • 拿正则表达式第三个操作符c与字符串第三个字符b匹配, 匹配成功, 于是结束.

如果在他们之后多加一个+号, 那么原先的贪婪模式就变成独占模式, 尽可能多地匹配。但是不会素.

于是乎, 如果要彻底解决问题, 就要在保证功能的同事不发生回溯. 我将上面校验URL的正则表达式的第二部分多加了一个+号,

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)
(([A-Za-z0-9-~]+).)++   --->>> (这里加了个+号)
([A-Za-z0-9-~\/])+$

检测工具

可以通过regex debugger工具进行检测


Compiler编程笔记 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Java正则表达式
喜欢 (1)
[阳光路上]
分享 (0)
发表我的评论
取消评论
表情 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址