目前，越来越多的网站、编辑器、编程语言都支持一种叫做“正则表达式”的字符串搜索“公式”。有编程经验的同学应该了解正则表达式（RegularExpression）什么是正则表达式，它是一种字符串匹配的模式，更像是一种逻辑公式。用正则表达式匹配字符串HelloWorld中的Hello伪代码：/Hello/,"HelloWorld"Output:Hello如何写一篇关于正则表达式的文章，想了一个星期，一直没有一个article文章能让猪哥这么麻烦。因为我觉得正则表达式：难记、难描述、广而深、不被重视，有人说正则表达式写起来既容易又难！好写：无非就是写一些常见的、实用的案例。说实话，你们每个人都可以写这样的文：在网上百度一下，结合自己的一点实践经验，一篇文章就出来了。难写：很多人觉得正则表达式很简单，不用死记硬背，想用就百度吧。但大多数人所了解的只是规律性的一小部分，很少关注到真正的本质！朱兄希望大家能够明白，正则表达式的知识点其实有很多，尤其是正则表达式的执行原理和正则优化。这个算是正则表达式的一个进阶知识点，面试的时候也可能会问到。一、起源与发展我们学习一门技术的时候，有必要了解它的起源和发展过程，这有助于我们了解技术本身！1940年代：正则表达式的最初想法来自两位神经科学家：WalterPitts和McCulloch，他们开发了一种模型，以数学方式描述神经网络。1956年：一位名叫StephenKleene的数学家发表了一篇名为《神经网事件的表示法》的论文，使用称为正则集的数学符号来描述模型，并引入了正则表达式的概念。正则表达式用于描述他们所谓的“正则集代数”，因此称为“正则表达式”。1968年：C语言之父、UNIX之父KenThompson利用这个“正则表达式”的理论成果，对搜索算法进行了一些研究。他描述了一个正则表达式的编译器，所以应该算是最早的正则表达式编译器qed（后来变成了grep编辑器）。Unix使用正则表达式后，正则表达式不断发展壮大，进而大规模地应用于各个领域。根据这些领域各自的条件和需要，正则表达式发展了很多版本，出现了很多分支。我们称这些分支为“流派”。1987年：Perl语言诞生。它综合了其他语言，并以正则表达式为基础，创造了一个新的流派，即Perl流派。后来很多编程语言如：Python、Java、Ruby、.Net、PHP等在设计正则表达式支持时都参考了Perl正则表达式。到这里我们也知道了为什么很多编程语言的正则表达式基本都是一样的，因为都是从Perl学来的。注意：Perl语言是一门擅长处理文本的语言，但是很多开发者并不喜欢它，因为晦涩难懂的语法和怪异的符号不利于理解和记忆。2.一个具有完整语法的正则表达式由两种字符组成：特殊字符（元字符）和普通字符。ps：元字符表示正则表达式函数的最小单位，如*^$\d等，语法部分猪哥不想过多解释，给大家做一个详细的总结，方便大家快速搜索将来！如果想系统的学习正则表达式的语法部分，朱哥推荐一个菜鸟教程：https://www.runoob.com/regexp...三、匹配原理匹配原理是朱哥要重点研究的，和希望同学们能够认真理解这部分的内容。很多人认为开车不一定要懂汽车的构造原理，但我们真的需要懂原理才能学编程。因为懂原理，所以会调，这往往是初级工程师和中高级工程师的区别之一！1.执行过程正则表达式就是执行，由正则表达式引擎编译执行。朱哥也拿了一张流程图给大家看下大概的执行流程。这里给大家提一点：pre-usecompile（预使用编译）朱哥推荐大家在生产环境使用预编译功能，为什么？以Python语言内置的re模块为例：通过re.compile(pattern)预编译并返回Pattern对象，在下面的代码中可以直接引用。使用re.match(pattern,text)立即编译。虽然Pattern对象会被缓存，但是每次使用都需要从缓存中取回，比预编译多了一步。猪哥也通过实际测试验证了预编译确实比即用编译要快！pattern=r'http:\/\/(?:.?\w+)+'text='xxx.com'2.引擎既然正则表达式是由执行引擎执行的，那我们就来说说正则表达式引擎。这是关键点。希望大家仔细看看，了解一下！正则引擎基本可以分为两大类：DFA（Deterministicfiniteautomaton）确定性有限自动机NFA（Non-deterministicfiniteautomaton）非确定性有限自动机ps：当然还有另外一个引擎：POSIXNFA，这个是基于规范的版本关于NFA引擎，但是因为用的少，这里就不重点说了。这里需要给大家解释一下deterministic,finite,automata这几个术语：deterministicandnon-deterministic：假设有一个字符串（text=abc）需要匹配，不写正则表达式，字符匹配序列可以直接确定的是确定性类型，不能确定字符匹配序列的是非确定性类型。Finite：Finite的意思是有限的，这里是指在有限的次数内可以得到结果。Automata：Automata是自动完成，是我们设置好匹配规则后由引擎自动完成，不需要人为干预！根据上面的解释，我们可以知道DFA引擎和NFA引擎的区别在于：是否可以不用写正则表达式就可以确定字符执行的先后顺序！DFA引擎执行原理：为了让大家清楚的了解DFA引擎执行原理，诸葛做了一个简单的动态执行流程图给大家看看。根据上面的动画，我们可以得到DFA引擎的一些特点：面向文本：按照文本的顺序执行，这也可以解释为什么DFA引擎是确定性的和稳定的！记录所有当前有效的可能性：我们看到当(d|b)被执行时，表达式中的d和b同时被比较，所以会需要更多的内存。每个字符只检查一次：这提高了执行效率，并且速度与正则表达式无关。不能使用backreferences等功能：因为每个字符只检查一次，而文本零宽（位置）只记录当前的比较值，所以不能使用backreferences、lookaround等功能！NFA引擎执行原理：朱哥还画了一个简单的NFA引擎执行流程图，方便大家理解。匹配继续匹配其他部分，直到表达式匹配完成。某个位置会被记录下来：我们看到当执行到(d|b)时，NFA引擎会记录字符的位置（零宽），然后选择其中一个先进行匹配。单个字符可能会被多次检查：我们看到在执行(d|b)时，比较d后发现不匹配，于是NFA引擎切换到表达式的另一个分支b，同时文本位置回滚以重新匹配字符“b”。这也是NFA引擎非确定性的原因，同时带来另一个问题，效率可能没有DFA引擎高。可以实现backreferences等功能：因为stepback，可以轻松实现一些backreferences，look-arounds等功能！针对这两种引擎的区别，朱哥对这两种引擎进行了比较总结。朱大哥引用了《精通正则表达式》书中的一句话来总结：DFA（电动机）和NFA（汽油机）历史悠久，但是，和汽油机一样，NFA的历史更久远。还有一些系统混合使用引擎，根据任务选择使用哪个引擎（或者甚至为同一表达式的不同部分使用不同的引擎以获得功率和速度的最佳平衡）。——《精通正则表达式》3.回溯是大多数编程语言都选择的引擎——NFA（非确定性有限自动机）引擎，当然我们要多了解一下它的本质——回溯。在动画中我们可以看到，当一个正则分支匹配失败时，需要回滚文本的位置，再匹配另一个分支。此步骤的技术术语是回溯。回溯的原理类似于在走迷宫时在我们走过的路径上设置标记。如果不正确，则返回原来的路径，换一条路径。回溯机制不仅需要重新计算正则表达式与文本对应的位置，还需要维护括号中子表达式匹配的文本状态（b匹配成功），保存在编号为by的组中内存中的编号，称为捕获组。将匹配结果保存在括号中后，我们就可以在后续的正则表达式中使用它们了。这就是我们所说的反向引用。在上面的例子中，只有一次捕获，所以$1=b。回溯陷阱：说到回溯，就不得不提到回溯陷阱。结果是机器的CPU占用满了（超过100%），机器卡死了。例如：text=aaaaa,pattern=/^(a*)b$/，匹配过程大致是(a*)：文本中匹配的aaaaa匹配正则模式中的b，但是失败，因为(a*)已经吃完所有文本后，引擎会要求（a*）吐出最后一个字符（a），但它无法匹配b。第二次吐出倒数第二个字符（或者a），还是匹配不上，所以引擎会要求（a*）把所有吃掉的字符一个一个吐出来，但是最后还是匹配不上。要倒退几万次，这对机器的CPU来说是一场灾难。一些复杂的正则表达式可能有多个部分需要回溯，回溯的次数呈指数级增长。如果文本长度是500，一个表达式有两部分要回溯，次数可能是500^2=250,000次，谁受得了！更详细的回溯介绍，推荐大家阅读本书《精通正则表达式》！4.优化编写巧妙的正则表达式不仅是一种技能，而且是一门艺术。上面我们了解到，绝大多数的编程语言都使用了NFA引擎，而NFA引擎的特点是：功能强大，但是由于有回溯机制，效率较慢。所以我们需要学习NFA引擎的一些优化技巧，减少引擎回溯的次数，更直接的匹配结果！NFA引擎可以优化的点其实挺多的。为了方便大家记忆，朱哥还总结了框架结构图，方便大家收藏仔细看看。面试过程中，可能会被问到正则表达式的优化，记住几点即可。5.推荐上面我们讲解了正则表达式、引擎、优化等知识的诞生和发展，但是关于正则表达式的知识点远不止这些，所以最后祝兄推荐一些不错的学习资料。了解它。1.书上推荐的正则表达式必须是《精通正则表达式》。目前本书第三版已经发行，豆瓣评分8.9。虽然内容有点啰嗦，但是对于一般的新手来说还是很友好的。唯一不足的是Python案例少。2.博客入口：菜鸟教程：https://www.runoob.com/regexp...3.在线测试工具https://regex101.com/，本站可以选择正则支持不同的编程语言，带语义分析、匹配测试、参考列表等，很有用。4.常见案例一些简单常用的小案例总结，菜鸟教程：http://c.runoob.com/front-end...最后祝大家处理正则表达式，处理文本游刃有余！更多优质教程，请关注朱哥微信公众号《裸睡猪》！
