正则表达式历史
最初想法在 20 世纪 40 年代,Warren McCulloch 和 Walter Pitts(两位神经生理方面的科学家)研究出了一种用数学方式来描述神经网络的新方法,创造性地将神经系统中的神经元描述成了小而简单的自动控制元。
1951 年,一位名叫 Stephen Kleene 的数学科学家在 Warren McCulloch 和 Walter Pitts 早期工作的基础之上,发表了一篇题目是《神经网事件的表示法》的论文,利用称之为正则集合的数学符号来描述此模型,引入了正则表达式的概念。正则表达式被作为用来描述其称之为“正则集的代数”的一种表达式,因而采用了“正则表达式”这个术语。
之后,Ken Thompson(Unix 的主要发明人)把这一成果应用于计算搜索算法的一些早期研究,他将此符号系统引入编辑器 QED,然后是 Unix 上的编辑器 ed,并最终引入 grep。
现在,正则表达式的身影出现在各种开发语言中...
应用案例
1 . 匹配特殊内容:/\"([^\"\.]*)\"/g
'he said "yes" and she said "no"'.match(/\"(?:[^\"\.]*)\"/g);
// output yes 和 no
2 . 匹配符合条件的文件
ls -l | grep -E "node|ts"
# drwxr-xr-x 28 no staff 896 Feb 27 11:34 node_modules
# -rw-r--r-- 1 no staff 616 Feb 27 14:28 tsconfig.json
3 . 去除首尾空格:/^\s|\s$/g
" hello ".replace(/^\s|\s$/g, "");
// output "hello"
4 . 货币转换:/(?<=\d)(?=(\d{3})+$)/g
"123456789".replace(/(?<=\d)(?=(\d{3})+$)/g, ",");
// output 123,456,789
RegExp in JavaScript
1 . 分组匹配操作
(pattern) 分组(获取)匹配
/\d(abc)/.exec("3abc"); // 获取到 3abc 和 abc
(?:pattern)非获取匹配
/\d(?:abc)/.exec("3abc"); // 获取到 3abc
(?=pattern)非获取,正向肯定预查
/\d(?=abc)/.test("3abc"); // output true
/\d(?=abc)/.test("3acb"); // output false
(?!pattern)非获取,正向否定预查
/\d(?!abc)/.test("3abc"); // output false
/\d(?!abc)/.test("3acb"); // output true
(?<=pattern)非获取,反向肯定预查
/(?<=abc)\d/.test("abc3"); // output true
/(?<=abc)\d/.test("abd3"); // output false
(?<!pattern)非获取,反向否定预查
/(?<!abc)\d/.test("abc3"); // output false
/(?<!abc)\d/.test("abd3"); // output true
2 . RegExp.prototype.test 方法受 lastIndex 属性的关联
var str = "abcabc";
var regexp = /a/g;
console.log(regexp.test(str)); // output true
console.log(regexp.lastIndex); // output 1
console.log(regexp.test(str)); // output true
console.log(regexp.lastIndex); // output 4
console.log(regexp.test(str)); // output false
console.log(regexp.lastIndex); // output 0
test 方法在执行后将 lastIndex 属性值置为匹配到的结果索引值,并返回匹配结果;下一次执行 test 方法时从 lastIndex 位置开始匹配,并返回匹配结果;以此类推;最后一次执行 test 方法,索引重置为 0,匹配结果为 false
正则引擎(DFA & TRANDITIONAL NFA & POSIX NFA)
DFA(确定型有穷自动机) 文本主导:以文本为掌控者逐字匹配。
大概过程如:
/to(nite|knight|night)/.exec('aaatonightbbb')
手里握着文本,眼睛看着表达式,逐个字符匹配,当匹配到 n 的时候,发现 nite|knight|night 之中 knight 的 k 不匹配,舍弃 knight,匹配 nite 和 night,当匹配到 g 的时候发现 nite 的 t 不匹配,舍弃 nite,匹配 night..直到输出匹配结果 tonight。
NFA(非确定型有穷自动机) 表达式主导:以表达式为掌控者,表达式中的控制权可在不用元素间转换。
大概过程如:
/to(nite|knight|night)/.exec('aaatonightbbb')
手里握着正则表达式,眼睛看着文本,逐个字符匹配,当匹配到 t 后,匹配紧随其后的文本是否是 o,接着存在 3 种可能(nite|knight|night),先取第一个子表达式 nite,匹配到 t 的时候,发现文本是 g,不匹配,放弃 nite,进行 knight...以此类推,直到匹配到第三个 night 子表达式完成匹配,输出结果 tonight。
POSIX NFA 是符合 POSIX 标准的 NFA 引擎,其特点是尽可能的再回溯过程中匹配最长的结果。
各语言应用:
使用 DFA 引擎的程序主要有:awk,egrep,flex,lex,MySQL,Procmail 等
使用传统型 NFA 引擎的程序主要有:GNU Emacs,Java,ergp,less,more,.NET 语言,PCRE library,Perl,PHP,Python,Ruby,sed,vi
使用 POSIX NFA 引擎的程序主要有:mawk,Mortice Kern Systems’ utilities,GNU Emacs
使用 DFA/NFA 混合的引擎:GNU awk,GNU grep/egrep,Tcl
差异对照
回溯/贪婪与非贪婪/捕获型括号
1 . 回溯(DFA 不支持)
/to(nite|knight|night)/.exec("aaatoknightbbb");
在搜索尝试过程中寻找问题的解,当在分歧点时,选择一条路径并记住另一/多条路径供之后使用,在选择路径后的探索过程中发现不满足求解条件时,就返回到分歧点,尝试其他路径(回溯遵循后进先出原则/LIFO-last in first out)
2 . 贪婪与非贪婪(仅传统型 NFA 支持)
/fo{1,5}/.exec('fooooo') // output fooooo 即贪婪模式、匹配优先量词
/fo{1,5}?/.exec('fooooo') // output fo 即非贪婪模式、忽略优先量词
注意:这里的关键字在于量词,单独的?符号属于匹配优先,而??双问号符号属于忽略优先,js 不支持??双问号。
3 . 捕获型括号(DFA 不支持)
/\d(abc)/.exec("3abc"); // 获取到 3abc 和 abc
正则优化思路
通过正则表达式执行匹配过程的理论,可得出的总结:
- 减少回溯次数
- 减少不必要的匹配或者状态存储
- 根据需求进行精准且合理的匹配(如贪婪和非贪婪的选择)
- 从编译方面优化(正则书写规范和表达式存储)
- 详细到操作:
- 减少或者优化判断分支,如[abcd]优于(a|b|c|d)、th(is|at)优于(this|that);
- 明确匹配条件(体现在字符组和量词上),又如/\d\d\d/和/\d{3}/在不同的正则表达式具体实现上效率是有区别的;
- 限制匹配优先的作用范围,如+和*的区别,+减少了多选结构的回溯次数;
- 使用非获取匹配以节省结果或者状态存储(同时也优化了回溯分支);
- 将复杂的多条件正则拆分成多个简单的单条件正则(这条不行... 至少在 JavaScript 里拆分后反而慢);
- 锚点的优化,如/regex(es)?$/匹配只可能从字符串末尾倒数第 8 个字符开始,从而略过前面很多内容;
- 使用变量存储正则表达式(减少正则编译过程);
- 使用固化分组加快匹配失败的速度(js 中并不支持固化分组);
参考
《精通正则表达式》