性能实战——正则引擎NFA解读 正则 gi

本节开始，我们进入java性能实战的新章节-正则表达式。提到正则表达式，估计大家在平时的项目开发中都有用到，本节主要重点介绍正则表达式的构成和正则表达式引擎。

一、正则表达式简介及构成

正则表达式（Regular Expression，是一种文本模式。它使用单个字符串来描述、匹配一系列句法规则的字符串，通常被用来搜索和替换符合规则的文本。构造正则表达式语法的元字符，由普通字符、标准字符、限定字符（量词）、定位字符（边界字符）组成，详细见下图：

二、正则表达式引擎

正则表达式是一个用正则符号写出的公式，程序对这个公式进行语法分析，建立一个语法分析树，再根据这个分析树结合正则表达式的引擎生成执行程序（这个执行程序我们把它称作状态机，也叫状态自动机），用于字符匹配。而这里的正则表达式引擎就是一套核心算法，用于建立状态机。正则表达式引擎有DFA 自动机（Deterministic Final Automata 确定有限状态自动机）和 NFA 自动机（Non deterministic Finite Automaton 非确定有限状态自动机）两种，本节主要介绍NFA，下面我们举例说明：

假设存在文本text=“aabcab”，正则表达式为regex=“bc”

NFA 自动机会读取正则表达式的每一个字符，拿去和目标字符串匹配，匹配成功就换正则表达式的下一个字符，反之就继续和目标字符串的下一个字符进行匹配。分解一下过程。

首先，读取正则表达式的第一个匹配符和字符串的第一个字符进行比较，b 对 a，不匹配；继续换字符串的下一个字符，也是 a，不匹配；继续换下一个，是 b，匹配。

然后，同理，读取正则表达式的第二个匹配符和字符串的第四个字符进行比较，c 对 c，匹配；继续读取正则表达式的下一个字符，然而后面已经没有可匹配的字符了，结束。

以上就是NFA 的匹配过程，虽然在实际应用中，碰到的正则表达式都要比这复杂，但匹配方法是一样的。

三、总结

本节主要描述正则表达式的组成和介绍正则表达式引擎NFA的基本原理，属于入门级别的知识，因为篇幅限制，关于NFA的回溯问题，以及DFA的原理知识，我们会在下节进行详细的讲解，感兴趣的小伙伴可以关注作者，一起学习，共同进步！