正则表达式优化

2019-08-04  本文已影响0人  林万程

正则表达式优化
——《精通正则表达式》总结

[TOC]

第4章:表达式的匹配原理

引擎

DFA (Deterministic Finite Automaton 确定有穷自动机):
常见的只有MySQL,文本主导,不支持反向引用和捕获括号,但快

传统型 NFA(Non-非):
大多数语言,表达式主导,编译快,内存少,写法不同有性能差异

标准 POSIX NFA:
leftmost-longest,尝试所有确保最长
golang leftmost-first和leftmost-first都支持

混合:Tcl 等

规则

最左优先,尽可能多(匹配优先)

回溯

NFA 有两个可能时会根据 匹配优先* 还是 忽略优先*?
走其中一个分支,并保存备用状态
如果不成功再回溯尝试另一个分支

第5章:正则表达式实用技巧

(多选|分支)排序可能影响匹配结果

第6章:打造高效正则表达式

减少测试和回溯

  1. 编译
  2. 传动(从第1个字符开始,从第2个字符开始...)
  3. 检测(相连 量词{m,n}+* (捕获))
  4. 成功/->2.传动
  5. 失败

常见措施

编译优化

传动优化

正则优化

诀窍

消除循环

"(\\.|[^\\"]+)*"

优化为:
"[^\\"]*(\\.[^\\"]*)*"

公式:
opening normal* (special normal*) closing
左 常规*(特殊 常规*)* 右
  1. 常规和特殊的开头不能重合
  2. 特殊部分必须匹配至少一个字符
  3. 特殊部分必须是固化的

方法2:[^\\"]匹配更多,如果是转义,后面继续,结果一样

方法3:匹配主机名

[a-z]+(\.[a-z]+)*

使用占有优先量词

"([^\\"]++|\\.)*+"

使用固化分组

"(?>(?>[^\\"]+|\\.)*)"
\G(?:^|,)(?:((?>[^"]*)(?>""[^"]*)*)|([^",]*))

消除注释

/\*.*?\*/
/\*([^*]|\*+[^/*])*\*+/

消除循环
/\*[^*]*\*+(?:[^/*][^*]*\*+)*/

流畅运转

块注释=/\*[^*]*\*+(?:[^/*][^*]*\*+)*/
行注释=//[^\n]*
双引号="[^\\"]*(?:\\.[^\\"]*)*"
单引号='[^\\']*(?:\\.[^\\']*)*'
(双引号|单引号)|块注释|行注释
替换为
$1

优化为:
开头集=[^"'/]
(双引号|单引号|开头集+)|块注释|行注释

优化为:
(开头集+|双引号|单引号)|块注释|行注释

优化为:
(开头集+|双引号 开头集*|单引号 开头集*)|块注释|行注释

([^"'/]+|
"[^\\"]*(?:\\.[^\\"]*)*"[^"'/]*|
'[^'\\]*(?:\\.[^'\\]*)*'[^"'/]*
)|
/\*[^*]*\*+(?:[^/*][^*]*\*+)*/|
//[^\n]*
上一篇 下一篇

猜你喜欢

热点阅读