【正则表达式入门】

1. 正则表达式简介

正则表达式是一种专注于匹配和提取的表达式，有关键字、语法，像是一门编程语言。最完美的正则表达式本质上是精巧的归纳法的集中体现和表达。

1.1 匹配

最基础的用法，观察字符串是否符合正则表达式的规则。

1.2 提取

使用 () 包裹的部分便为提取。

2. 基本语法

正则表达式手册
常见误区

1. 表达式中存在正则表达式的关键字，需要转义，比如 “.”，需要转义为 “.”。

3. 执行流程

正则表达式在匹配时有效率区别，对于对性能有较高要求的场景，需要注意正则表达式的编写。避免Catastrophic Backtracking（灾难性回溯）。

3.1 AST树

相信很多人在学习栈这种数据结构时，都尝试用回溯法来解析简单的数学表达式。正则表达式的解析也是类似的。当我们给出一个用来匹配的正则表达式和待匹配串时，系统首先将正则表达式编译成 AST 树。何为 AST 树？AST 树全称 abstract syntax tree，树的节点代表最基本的语法单元。

那么如何将代码转换为AST呢？分为两个过程，词法分析（Lexical Analysis）和语法分析（Parsing）。

那么树的边的含义呢？

3.2 状态机

得到了AST树之后，再将 AST 转换为状态机，状态机分为 DFA （Deterministic Finite Automation） 和 NFA （Non-deterministic Finite Automation）。DFA 为确定性状态机，每个状态对于每个输入的字符只有唯一的转移状态，改种状态机的匹配时间复杂度为O(n)，NFA为不确定状态机，每个状态对于每个输入的字符可以存在多种转移状态，该种状态机需要使用回溯法来遍历所有可能的输出。

3.3 处理特殊性

正则表达式一些特殊特性需要特别适配，单纯使用状态机无法完全覆盖。一些特殊性的机制，比如

1. 贪婪匹配策略和非贪婪匹配策略，贪婪匹配策略时，要求尽可能匹配更多的字符，当发现匹配时，状态机还会继续执行；非贪婪匹配策略，要求尽可能少地匹配字符，类似于广度遍历策略，发现最短匹配字符串时便停止搜索。

3.4 注意问题

3.4.1 避免灾难性回溯

何时会产生灾难性回溯呢？

4. 有效工具

正则表达式测试网站
这个测试网站如何使用呢？

5. 作者的案例

作者写本文的起因便是在编写正则表达式时，被系统提示产生了灾难性回溯。
缘起。
使用的场景是这样的，作者负责的服务器需要采集日志，在将日志采集到统一日志分析服务时，需要将平铺的日志转换为结构化的日志，日志采集器集成了正则日志转换器，于是便开始编写一些不入流的正则表达式，诸如 (.*)|(.*) ^(.*) ^(.*)|(.*)|(.*)每次编写到第九个(.*)时，正则日志转换器便报错（这里只是简单的报错，没有任何提示信息），作者非常地疑惑，开始从各种角度分析为何出现这种报错，当作者一度要找售后进行咨询时，发现了 4 中的网站，将本人的表达式和原文输入其中之后，便抛出了 Catastrophic Backtracking 异常。
原因反思。
最大的问题就在于作者使用了 (.*) 这种默认的贪婪模式，尽可能长地去匹配字符串。
但是为何就会出现这种问题呢？
让大厂服务器故障半小时的正则陷阱

如何调试正则表达式
阿里云SLS日志正则表达式入门
优化正则表达式性能