Regular Expression In JavaScript

正则表达式历史

最初想法在 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

正则优化思路

通过正则表达式执行匹配过程的理论,可得出的总结:

  1. 减少回溯次数
  2. 减少不必要的匹配或者状态存储
  3. 根据需求进行精准且合理的匹配(如贪婪和非贪婪的选择)
  4. 从编译方面优化(正则书写规范和表达式存储)
  5. 详细到操作:
  6. 减少或者优化判断分支,如[abcd]优于(a|b|c|d)、th(is|at)优于(this|that);
  7. 明确匹配条件(体现在字符组和量词上),又如/\d\d\d/和/\d{3}/在不同的正则表达式具体实现上效率是有区别的;
  8. 限制匹配优先的作用范围,如+和*的区别,+减少了多选结构的回溯次数;
  9. 使用非获取匹配以节省结果或者状态存储(同时也优化了回溯分支);
  10. 将复杂的多条件正则拆分成多个简单的单条件正则(这条不行... 至少在 JavaScript 里拆分后反而慢);
  11. 锚点的优化,如/regex(es)?$/匹配只可能从字符串末尾倒数第 8 个字符开始,从而略过前面很多内容;
  12. 使用变量存储正则表达式(减少正则编译过程);
  13. 使用固化分组加快匹配失败的速度(js 中并不支持固化分组);

参考

《精通正则表达式》

POSIX-wikipedia

DFA-wikipedia

NFA-wikipedia

REGEXP_MDN

RegExpecma-262#sec-regexp-regular-expression-objects

博客文章

unicode-编码官网