正则表达式之原理篇

一、正则表达式之原理篇

    最近公司规范出来后，关于字符串不提倡用“+” 进行拼接，于是自己写了个function，利用正则表达式来进行匹配。对于正则表达式，之前不了解原理，每次要用的时候查一下，很浪费时间。

1.占有字符：正则表达式匹配过程中，如果子表达式匹配到东西，而并非是一个位置，并最终保存到匹配的结果当中

2.零宽度：只匹配一个位置，或者是匹配的内容并不保存到匹配结果中

一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配

3.控制权：正则表达式由左到右依次进行匹配，通常情况下是由一个表达式取得控制权，从字符串的的某个位置进行匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的（例如：（表达式一）（表达式二）意思就是表达式一匹配完成后才能匹配表达式二，而匹配表达式二的位置是从表达式一的位置匹配结束后的位置开始）。如果表达式一是零宽度，那表达式一匹配完成后，表达式二匹配的位置还是原来表达式以匹配的位置。也就是说它匹配开始和结束的位置是同一个

6.转义字符：\ 使元字符失去它的意义，仅代表其输入中字符的意义

需要转义的字符列表\*+?|{ [() ^$.#和空白

7.重复限定符：匹配优先量词，忽略优先量词，即：贪婪与非贪婪

{n,}、{n, m}、{, m}、’+’、‘?’、'*'

10.分组：（）指定子表达式，可限制多选项的范围、将若干字符组合为一个单元、受问号或星号之类的量词作用，例：(\d{1,3}){3}\d{3}

11.括号及反向引用：（子表达式一）（子表达式二）\1   此时括号作用为分组，它具有记忆的功能，即在正则表达式内部仍然能回忆上次匹配到的是什么；\1、\2、\n是用在正则表达式的匹配环节。在正则表达式的替换环节，则要使用像$1、$2、$n这样的语法

1.默认贪婪匹配；（贪婪匹配与非贪婪匹配）

针对简单的正则匹配进行分析，例：

    当把cat应用到“He captured a catfish for his cat”，引擎先比较c和“H”，结果失败了。于是引擎再比较c和“e”，也失败了。直到第四个字符，c匹配了“c”。a匹配了第五个字符。到第六个字符t没能匹配“p”，也失败了。引擎再继续从第五个字符重新检查匹配性。直到第十五个字符开始，cat匹配上了“catfish”中的“cat”，正则表达式引擎急切的返回第一个匹配的结果，而不会再继续查找是否有其他更好的匹配

Rubular:基于 Web的 Ruby正则表达式编辑器

贪婪与非贪婪（又称惰性、懒惰等）模式

两者影响的是被量词修饰的子表达式的行为。

贪婪模式在整个表达式匹配成功的前提下，尽可能多的匹配；而非贪婪模式（只被部分NFA引擎支持）在整个表达式匹配成功的前提下，尽可能少的匹配。

匹配优先量词（属于贪婪模式的量词）：

“{m,n}”、“{m,}”、“?”、“*”和“+”。

忽略优先量词（匹配优先量词后加上“?”：非贪婪模式的量词）：

“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”

DFA与NFA引擎（JS的正则引擎是NFA：非确定型有限自动机）

DFA引擎：在线性时状态下执行，不要求回溯（因此永远不测试相同的字符两次）；确保匹配最长的可能的字符串；因为只包含有限的状态（？），所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式

传统的NFA引擎：运行匹配回溯算法——以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。但传统 NFA的回溯使它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现

POSIX NFA引擎：与传统 NFA引擎类似，不同点：在可以确保已找到了可能的最长的匹配之前，它们将继续回溯（更慢）；并且在使用 POSIX NFA时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索

字符串： this is yansen’s dog

正则表达式：/ya(msen|nsen|nsem)/

NFA工作方式：先在字符串中查找 y，然后匹配其后是否为 a； 如果是 a则继续查找其后是否为 m；如果不是则匹配其后是否为 n(此时淘汰 msen支分支)；然后继续看其后是否依次为 s,e；接着测试是否为 n，是 n则匹配成功，不是则测试是否为 m。为什么是 m？因为 NFA工作方式是以正则表达式为标准，反复测试字符串，这样同样一个字符串有可能被反复测试了很多次！

DFA：从 this中 t开始依次查找 y，定位到 y，已知其后为 a，则查看表达式是否有 a，此处正好有 a；然后字符串 a后为 n，DFA依次测试表达式，此时 msen不符合要求淘汰。 nsen和 nsem符合要求，然后DFA依次检查字符串，检测到 sen中的 n时只有 nsen分支符合，则匹配成功！

由此两种引擎是完全不同的工作方式：NFA以表达式为主导，更容易操纵；DFA以文本为主导（搜索更快）

引擎是如何来处理那些模糊的条件匹配？

从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”

本质上就是深度优先搜索算法：尝试匹配失败时的下一步通常就是回溯

JS中正则表达式会产生回溯的地方都有哪些呢？

1.没有回溯的匹配：当目标字符串是"abbbc"时

2.有回溯的匹配：当目标字符串是“abbc”时

上图第5步有红颜色（仅表示匹配不成功）：此时b{1,3}已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式c，去匹配字符“c”。当然，此时整个表达式匹配成功了；上图的第6步，就是“回溯”

即：尝试可能的顺序是“从多往少”的方向去尝试：首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。如果还不行呢？只能说明匹配失败了

省略了尝试匹配双引号失败的匹配过程

其实“.*”最简单但也是非常影响效率的

虽然惰性量词不贪，但也会有回溯的现象（为了整体匹配成）

分支也是惰性的，比如/Java|JavaScript/，去匹配字符串"JavaScript"，得到的结果是"Java"，因为分支会一个一个尝试，如果前面的满足了，后面就不会再试验了。

分支结构中可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分支。这种尝试也可以看成一种回溯：

虽然第五步没有回到之前的状态，但仍然回到了分支结构，尝试下一种可能

总结：有回溯的过程，那么匹配效率肯定比DFA相对低一些；别看匹配慢，但是编译快而且还挺有趣

二、在正则表达式中\\.和.有什么区别

1.在Java中，反斜杠（\）是一个特殊的字符，被称为转义字符，它的作用是用来转义后面一个字符。转义后的字符通常用于表示一个不可见的字符或具有特殊含义的字符，例如换行（\n）、回车符(\r)、制表符(\t)。

2.在Java中以下字符都有特殊意义，无法直接表示

单引号：char c='a';表示字符类型的数据时需要使用单引号将字符左右括起来。所以要表示字符'则需要使用\'

双引号：String str="abc";表示字符串类型的数据时需要使用双引号将字符串左右括起来。要表示字符串"则需要\"

反斜杠：String regex="你好\n\t阿";在Java代码中\表示转义字符，所以如果要表示字面意思的\，则需要使用\\

所以用反斜杠加上本身字符来进行表示。

\表示将下一字符标记为特殊字符。如\d表示数字字符匹配，等效于 [0-9]。\w表示匹配任何字类字符（字母数字下划线），注意包括下划线。与"[A-Za-z0-9_]"等效。

在其他语言中，\\表示：我想要在正则表达式中插入一个普通的（字面上的）反斜杠，请不要给它任何特殊的意义。

在 Java中，\\表示：我要插入一个正则表达式的反斜线，所以其后的字符具有特殊的意义。

在 Java中，\\表示：我要插入一个正则表达式的反斜线，所以其后的字符具有特殊的意义。

在 Java中，\\表示：我要插入一个正则表达式的反斜线，所以其后的字符具有特殊的意义。

\\中的第一个\表示java的转义字符\由编译器解析，第二个\是正则表达式\由正则表达式引擎解析。

所以，在其他的语言中（如Perl），一个反斜杠\就足以具有转义的作用，而在 Java中正则表达式中则需要有两个反斜杠才能被解析为其他语言中的转义作用。也可以简单的理解在 Java的正则表达式中，两个\\代表其他语言中的一个\，这也就是为什么表示一位数字的正则表达式是\\d，而表示一个普通的反斜杠是\\\\。

所以Java正则表达式中匹配一个普通的反斜杠是\\\\。

所以如果在[]内表示一个]，要写两个\，即[\\]]。

例如，我要在前面不是0-9，也不是） ]}三个反括号的后面位置中，匹配-的后面是数字或者正括号( [{的-前面的位置，须写成:

(?<![0-9)}\\]])(?=-[0-9({\\[])。

若在该位置加0,可写成String s= str.replaceAll("(?<![0-9)}\\]])(?=-[0-9({\\[])","0");

^匹配输入字符串开始的位置。如果设置了 RegExp对象的 Multiline属性，^还会与"\n"或"\r"之后的位置匹配。

$匹配输入字符串结尾的位置。如果设置了 RegExp对象的 Multiline属性，$还会与"\n"或"\r"之前的位置匹配。

*零次或多次匹配前面的字符或子表达式。例如，zo*匹配"z"和"zoo"。*等效于{0,}。

+一次或多次匹配前面的字符或子表达式。例如，"zo+"与"zo"和"zoo"匹配，但与"z"不匹配。+等效于{1,}。

?零次或一次匹配前面的字符或子表达式。例如，"do(es)?“匹配"do"或"does"中的"do”。?等效于{0,1}。

{n} n是非负整数。正好匹配 n次。例如，"o{2}"与"Bob"中的"o"不匹配，但与"food"中的两个"o"匹配。

{n,} n是非负整数。至少匹配 n次。例如，"o{2,}“不匹配"Bob"中的"o”，而匹配"foooood"中的所有 o。"o{1,}“等效于"o+”。"o{0,}“等效于"o*”。

{n,m} m和 n是非负整数，其中 n<= m。匹配至少 n次，至多 m次。例如，"o{1,3}"匹配"fooooood"中的头三个 o。‘o{0,1}’等效于‘o?’。注意：您不能将空格插入逗号和数字之间。

[xyz]字符集。匹配包含的任一字符。例如，"[abc]“匹配"plain"中的"a”。

[ ^xyz]反向字符集。匹配未包含的任何字符。例如，"[^abc]“匹配"plain"中"p”，“l”，“i”，“n”。

[a-z]字符范围。匹配指定范围内的任何字符。例如，"[a-z]"匹配"a"到"z"范围内的任何小写字母。

\d数字字符匹配。等效于 [0-9]。

\D非数字字符匹配。等效于 [ ^0-9]。

\w匹配任何字类字符，包括下划线。与"[A-Za-z0-9_]"等效。

\W与任何非单词字符匹配。与"[ ^A-Za-z0-9_]"等效。

使用正则表达式需要引入 java.util.regex包，我们就从这里入手讲解：

java.util.regex包主要包括以下三个类：

pattern对象是一个正则表达式的编译表示。Pattern类没有公共构造方法。要创建一个 Pattern对象，你必须首先调用其公共静态编译方法，它返回一个 Pattern对象。该方法接受一个正则表达式作为它的第一个参数。

Matcher对象是对输入字符串进行解释和匹配操作的引擎。与Pattern类一样，Matcher也没有公共构造方法。你需要调用 Pattern对象的 matcher方法来获得一个 Matcher对象。

PatternSyntaxException是一个非强制异常类，它表示一个正则表达式模式中的语法错误

三、正则表达式的起源

1、正则表达式的“鼻祖”或许可一直追溯到科学家对人类神经系统工作原理的早期研究。美国新泽西州的Warren McCulloch和出生在美国底特律的Walter Pitts这两位神经生理方面的科学家，研究出了一种用数学方式来描述神经网络的新方法，他们创造性地将神经系统中的神经元描述成了小而简单的自动控制元，从而作出了一项伟大的工作革新。

2、在1956年,一位名叫Stephen Kleene的数学科学家，他在Warren McCulloch和Walter Pitts早期工作的基础之上，发表了一篇题目是《神经网事件的表示法》的论文，利用称之为正则集合的数学符号来描述此模型，引入了正则表达式的概念。正则表达式被作为用来描述其称之为“正则集的代数”的一种表达式，因而采用了“正则表达式”这个术语。

3、之后一段时间，人们发现可以将这一工作成果应用于其他方面。Ken Thompson就把这一成果应用于计算搜索算法的一些早期研究，Ken Thompson是 Unix的主要发明人，也就是大名鼎鼎的Unix之父。Unix之父将此符号系统引入编辑器QED，然后是Unix上的编辑器ed，并最终引入grep。Jeffrey Friedl在其著作《Mastering Regular Expressions(2nd edition)》（中文版译作：精通正则表达式，已出到第三版）中对此作了进一步阐述讲解，如果你希望更多了解正则表达式理论和历史，推荐你看看这本书。

4、自此以后，正则表达式被广泛地应用到各种UNIX或类似于UNIX的工具中，如大家熟知的Perl。Perl的正则表达式源自于Henry Spencer编写的regex，之后已演化成了pcre（Perl兼容正则表达式Perl Compatible Regular Expressions），pcre是一个由Philip Hazel开发的、为很多现代工具所使用的库。正则表达式的第一个实用应用程序即为Unix中的 qed编辑器。

5、然后，正则表达式在各种计算机语言或各种应用领域得到了广大的应用和发展，演变成为计算机技术森林中的一只形神美丽且声音动听的百灵鸟。

6、以上是关于正则表达式的起源和发展的历史描述，如今正则表达式在基于文本的编辑器和搜索工具中依然占据着一个非常重要的地位。

7、在最近的六十年中，正则表达式逐渐从模糊而深奥的数学概念，发展成为在计算机各类工具和软件包应用中的主要功能。不仅仅众多UNIX工具支持正则表达式，近二十年来，在WINDOWS的阵营下，正则表达式的思想和应用在大部分 Windows开发者工具包中得到支持和嵌入应用！从正则式在Microsoft Visual Basic 6或 Microsoft VBScript到.NET Framework中的探索和发展，WINDOWS系列产品对正则表达式的支持发展到无与伦比的高度，几乎所有 Microsoft开发者和所有.NET语言都可以使用正则表达式。如果你是一位接触计算机语言的工作者，那么你会在主流操作系统（*nix[Linux, Unix等]、Windows、HP、BeOS等）、主流的开发语言（delphi、Scala、PHP、C#、Java、C++、Objective-c、Swift、VB、Javascript、Ruby以及Python等）、数以亿万计的各种应用软件中，都可以看到正则表达式优美的舞姿。