什么是正则表达式？

正则表达式（Regular Expression：在代码中常简写为regex、regexp或RE）他由普通字符（代表字符本身含义比如a代表字符a）、元字符（有特殊含义的特殊字符,比如\d代表0~9任意一位数字）构成的字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑

正则表达式能做什么？

实现两个功能：①搜索②替换

按某种逻辑规则组合定义的正则表达式（它原本就是一段字符串，有的书上称之为这段字符串为一个模式）用它来对一段文本进行快速检索出我们规则定义的内容，或者替换符合某个规则的文本为其他内容，当然我们用各种编程语言都能实现这个目的，所有正则表达式仅仅代表一个规范，语言无关性。

正则引擎实现：怎么实现字符串匹配的?

我们首先引入几个概念：FA、NFA、DFA 参考资料

• FA(Finite Automate有限自动机) 有限自动机 (Finite Automata) 是一个识别器 (recognizer)，从起始状态开始，一个字符接一个字符地读入一个字符串，并根据给定的转移函数一步一步地转移至下一个状态，直至读完该字符串，并根据自动机的当前状态决定是否接受该字符串。
• DFA（Deterministic Finite Automata) 确定型有限自动机，文本主导的匹配，DFA从匹配文本入手，从左到右，每个字符不会匹配两次，它的时间复杂度是多项式的，所以通常情况下，它的速度更快，但支持的特性很少，不支持捕获组、各种引用等等；
• NFA（非确定型有限自动机） Nondeterministic Finite Automata 正则表达式主导的匹配，NFA则是从正则表达式入手，不断读入(cousume)字符，尝试是否匹配当前正则，不匹配则吐出(回溯)字符重新尝试，通常它的速度比较慢，最优时间复杂度为多项式的，最差情况为指数级的。但NFA支持更多的特性，因而绝大多数编程场景下（包括java，js，c#），我们面对的是NFA

一个正则表达式可以表示为一个有限自动机，模拟运行该有限自动机进行字符串识别，即可实现正则表达式匹配，其中分三个过程：

• Parser: 正则表达式解析器，即将正则表达式字符串解析为正则表达式抽象语法树，方便后续处理。
• Compiler: 正则表达式编译器，即将正则表达式转换为等效的 NFA，再根据情况是否将 NFA 转换为 DFA。
• Matcher: 正则表达式匹配器，运行该正则表达式的等效 NFA 或 DFA，对输入字符串进行识别匹配。我们用两种模式来分析下面这个例子

final String reg = "abd";
final String str = "abcabdf";
final Pattern pattern = Pattern.compile(reg);
final Matcher matcher = pattern.matcher(str);
// 提取匹配文本
List<String> result = RegexUtils.groupExtract(pattern, str);
log.debug("替换结果: {}", result);

DFA:（正则不回退，一条道路走到黑）

• 从str[0]开始匹配正则表达式reg[0]位置开始第一次匹配，匹配成功，正则表达式还未结束，继续
• str[1]和reg[1]匹配成功，继续匹配
• str[2]和reg[2]匹配失败，字符串未消费完，继续匹配
• str[3]和reg[0]匹配成功，字符串未消费完，继续匹配
• str[4]和reg[1]匹配成功，字符串未消费完，继续匹配
• str[5]和reg[2]匹配成功，正则表达式结束，匹配成功一次，字符串未消耗完成，继续下一次匹配
• str[6]和reg[0]，匹配失败，字符串消耗完成，结束匹配

NFA:(正则回退，条条大道通罗马，总有一个妹纸属于哥的)

• 开始匹配：str[0]匹配reg[0]位置开始第一次匹配，匹配成功，正则表达式还未结束，继续
• 继续匹配：str[1]和reg[1]匹配成功，
• 继续匹配str[2]和reg[2]匹配失败，字符串回溯到最先匹配成功的下一位str[1]
• 继续匹配str[1]匹配reg[0],匹配失败，字符串未消费完，继续匹配
• 继续匹配str[2]和reg[0]，匹配失败，字符串未消费完，继续匹配
• 继续匹配str[3]和reg[0]，匹配成功，字符串未消费完，继续匹配
• 继续匹配str[4]和reg[1]，匹配成功，字符串未消费完，继续匹配
• 继续匹配str[5]和reg[2]，匹配成功，正则表达式结束，匹配成功一次，字符串未消耗完成，继续下一次匹配
• 继续匹配str[6]和reg[0]，匹配失败，字符串消耗完成，结束匹配

通过两种方式可以实现一个正则表达式的引擎来解析字符串

学习实现目标：

1. 如何解析一个html文档标签元素？
2. 如何解析动态脚步，比如sql语句，where语句，计算公式等?