正则表达式(Regular Expressions)
章节大纲
-
什么是正则表达式？
正则表达式（Regular Expression，简称 regex 或 regexp）是一种用于表示字符串匹配模式的方法。它可以用于查找、选择或修改文本数据记录中的特定字符串。由于其强大的功能，正则表达式被广泛应用于各种文本处理工具和编程语言中。
示例应用
许多软件应用程序都使用正则表达式来查找、选择或修改特定文本。例如：
- 替换：使用正则表达式将文本中的
"snake"替换为"serpent"。 - 搜索：查找同时包含
"fox"和"sheep"的行。
正则表达式的组成
正则表达式由以下三种组件构成：
- 锚点（Anchors）：用于指定匹配模式在文本行中的位置。
- 字符集（Character Sets）：用于匹配某个位置上的一个或多个字符。
- 修饰符（Modifiers）：用于指定字符集的重复次数。
不同应用程序的正则表达式语法
不同的应用程序对正则表达式的语法有不同的实现方式。例如：
- Shell 使用了一种受限的正则表达式（Shell Regular Expressions），用于文件名匹配（通配符）。
- AWK 使用的是扩展正则表达式（Extended Regular Expressions, ERE）的超集，比 Shell 更强大。
支持正则表达式的软件
正则表达式被许多软件工具所支持，包括命令行工具、文本编辑器和编程语言，且适用于 Linux、Windows 和 macOS 等操作系统。
命令行工具 纯文本编辑器 编程语言 greped.NETegrepviAWKsedEmacsJavaNotepad++JavaScriptPerlPHPPythonRubyTcl
正则表达式的本质
可以把正则表达式看作一个迷你计算机程序，它的任务是查找或提取文本中的某个子集。就像计算机程序需要计算机才能执行一样，正则表达式需要特定的软件应用程序来解析并执行它，从而赋予它实际的意义。
例如：
- 在文本编辑器中，可以使用正则表达式查找**"Chapter"** 后面跟着多个空格和数字的文本。
- 在 UNIX 命令行中，使用
grep命令只显示包含 "Wiki" 后面跟着 "Books" 或 "pedia" 的行。
在下一章中，我们将详细讨论正则表达式的具体语法。
- 替换：使用正则表达式将文本中的
-
正则表达式的不同变体
正则表达式有多个变体，它们不仅在具体的语法上有所不同，在功能上也各具特色。支持正则表达式的工具和编程语言通常也会有自己独特的实现方式。
常见的正则表达式变体
-
简单正则表达式（Simple Regular Expressions）
- 主要用于向后兼容，但在符合 POSIX 标准的系统上已被弃用。
-
基本正则表达式（Basic Regular Expressions，BRE）
- 由一些 Unix Shell 工具（如
grep和sed）使用。
- 由一些 Unix Shell 工具（如
-
Perl 兼容正则表达式（Perl-Compatible Regular Expressions，PCRE）
- 由 Perl 及一些应用程序使用，功能非常强大。
-
POSIX 基本正则表达式（POSIX Basic Regular Expressions，POSIX BRE）
- 旨在增强不同工具间的一致性，但某些传统的 Unix 工具不支持这些扩展。
-
POSIX 扩展正则表达式（POSIX-Extended Regular Expressions，POSIX ERE）
- 通过
-E选项在某些 Unix 工具（如grep -E、sed -E）中启用。
- 通过
-
非 POSIX 基本正则表达式（Non-POSIX Basic Regular Expressions）
- 提供 POSIX 不支持的额外字符类，例如
\w（匹配字母和数字）。
- 提供 POSIX 不支持的额外字符类，例如
-
Emacs 正则表达式（Emacs Regular Expressions）
- 主要用于 Emacs 编辑器 的文本搜索和替换。
-
Shell 正则表达式（Shell Regular Expressions）
- 用于 模式匹配（Pattern Matching）和文件名替换（Filename Substitution），功能较有限。
贪婪匹配（Greedy Expressions）
在正则表达式中，
*和+等量词（Quantifiers）默认是贪婪的（Greedy），它们会尽可能多地匹配字符。这种特性在某些情况下可能会导致不符合预期的匹配结果。示例：
假设我们希望匹配第一个用双引号
"括起来的字符串，例如：These words include "cat", "mat", and "pat".使用正则表达式
"*"会匹配：These words include "cat", "mat", and "pat".错误匹配部分（斜体部分）：
These words include *"cat", "mat", and "pat".*它匹配了整个
"cat", "mat", and "pat"，而我们只想匹配第一个 "cat"。修正方案
- 使用非贪婪匹配（Non-Greedy Matching）
- 一些正则表达式变体支持非贪婪运算符：
*?+?}?
- 例如，在 PHP 中，可以使用
U修饰符使量词变为非贪婪匹配：/".*"/U
- 一些正则表达式变体支持非贪婪运算符：
- 使用排除匹配法
- 在不支持
*?的环境中，我们可以使用排除字符来控制匹配范围："[^"]*" - 这个表达式确保
"内部的内容不能包含双引号，从而正确匹配："cat"
- 在不支持
正则表达式特性对比
不同工具和编程语言对正则表达式的支持不同。想要了解哪些功能或变体适用于特定工具或语言，可以参考 regular-expressions.info 提供的对比表格（Comparison Table）。
-
-
正则表达式的实现及运行时间
在决定一个字符串是否匹配某个正则表达式时，通常有三种不同的算法。这些算法基于正则表达式作为有限自动机（Finite Automaton, FA） 的不同表示方式，并且根据匹配器的功能不同，其实现方式也有所不同。
1. 基于 NFA（非确定性有限自动机）的匹配器（无回溯）
- 特点：
- 该算法不支持回溯（back-references）以及前瞻/后顾（lookahead/lookbehind）。
- 通过汤普森（Thompson）算法模拟 NFA 进行匹配。
- 时间复杂度：
- 输入长度 O
，正则表达式大小 O(m)，匹配时间为 O(nm)。
- 若需要记录 c 个子匹配（sub-match capture groups），则时间复杂度增至 O(nm log c)。
- 额外的空间需求为 O(m)。
- 输入长度 O
2. 基于 NFA 的匹配器（带回溯）
- 特点：
- 该算法支持回溯（back-references）以及前瞻/后顾（lookahead/lookbehind）。
- 采用**回溯（backtracking）**方式进行匹配，遍历可能的匹配路径。
- 需要特别处理避免进入无限循环，否则可能会在同一条路径上重复测试。
- 时间复杂度：
- 输入长度 O
- 由于回溯的存在，最坏情况下可能出现指数级的运行时间。
- 输入长度 O
3. 基于 DFA（确定性有限自动机）的匹配器
- 特点：
- DFA 匹配器不支持回溯（back-references）、子匹配（sub-match captures）、前瞻/后顾（lookahead/lookbehind）。
- 该算法基于形式语言理论中的一个结果，即：任何 NFA 都可以转换为等价的 DFA。
- 通过转换为 DFA，再逐个字符进行匹配。
- 时间复杂度：
- 正则表达式大小 O(m)，输入字符集大小 S：
- DFA 构建时间：O(2^m S)（指数级）
- DFA 匹配时间：O
- 优点：匹配速度快，与输入字符串长度成正比。
- 缺点：
- 无法支持回溯（如
\1引用之前的匹配）。 - 无法记录子匹配（如提取括号中的内容
(\w+)）。 - 可能导致 DFA 状态爆炸（即状态数呈指数增长）。
- 无法支持回溯（如
- 正则表达式大小 O(m)，输入字符集大小 S：
4. DFA + NFA 混合匹配器
- 特点：
- 结合DFA 的高效性和NFA（回溯）的灵活性。
- 第一阶段：使用 DFA 快速判断字符串是否匹配正则表达式。
- 第二阶段：若匹配成功，则使用回溯法执行更复杂的匹配（例如子匹配、回溯引用）。
- 适用场景：
- 需要高效匹配的同时，也支持复杂功能（如
\1引用）。 - 一些现代正则表达式引擎（如 Perl、Python、PCRE）使用该策略。
- 需要高效匹配的同时，也支持复杂功能（如
性能分析
匹配算法 支持功能 时间复杂度 优点 缺点 NFA（无回溯） 基本匹配 O(nm) 实现简单，空间占用低 不支持回溯、前瞻/后顾 NFA（带回溯） 回溯引用、前瞻/后顾 O(2^mn)（最坏情况） 适用于复杂匹配 可能出现指数级回溯，影响性能 DFA 高效匹配 O 运行速度快 无法支持子匹配、回溯引用 DFA + NFA（混合） 结合两者优势 先 O 既快又灵活 需要额外的实现成本
5. 回溯（Backtracking）算法的潜在问题
-
最坏情况下可能出现指数级时间复杂度：
- 例如对于正则表达式
(a|aa)*b，输入字符串aaaaaaaaaaaaaaaaaaaaaa可能导致 指数级回溯。 - 这个问题被称为 灾难性回溯（Catastrophic Backtracking），会导致程序运行缓慢甚至崩溃。
- 例如对于正则表达式
-
优化策略：
- 改进匹配器：如 PCRE 等现代正则表达式引擎通过分析模式来避免回溯。
- DFA + NFA 组合：优先使用 DFA 进行快速匹配，仅在必要时回溯。
- 避免非必要的回溯结构：
- 避免
(a|aa)*b这种重复分支 - 尽量使用懒惰匹配（
*?、+?）
- 避免
6. 结论
- DFA 是最快的匹配算法，适用于简单匹配，但不支持回溯、子匹配。
- NFA（无回溯）适用于普通匹配，但不支持回溯、前瞻等高级功能。
- NFA（带回溯）支持复杂的正则匹配，但可能会导致指数级回溯，影响性能。
- DFA + NFA 混合策略能兼顾速度和灵活性，现代正则引擎（如 PCRE、Perl、Python）多采用此方法。
在实际应用中，应根据需求和性能要求选择合适的匹配算法。
- 特点：
-
术语表（Glossary）
符号
- \A 在某些正则表达式风格中，表示字符串的开头（但不是行的开头）。
- \b 在某些正则表达式风格中，表示单词边界。
- \B 在某些正则表达式风格中，表示非单词边界（\b 的补集）。
- \d 在某些正则表达式风格中，表示数字字符。
- \D 在某些正则表达式风格中，表示非数字字符（\d 的补集）。
- \s 在某些正则表达式风格中，表示空白字符（空格、制表符、换行符、换页符）。
- \s- 在 Emacs 中，表示空白字符。
- \S 在某些正则表达式风格中，表示非空白字符（\s 的补集）。
- \w 在某些正则表达式风格中，表示字母数字字符（包括 _）。
- \W 在某些正则表达式风格中，表示非字母数字字符（\w 的补集）。
- \Z 在某些正则表达式风格中，表示字符串的结尾（但不是行的结尾）。
- < 在某些正则表达式风格中，表示单词的开头。
- > 在某些正则表达式风格中，表示单词的结尾。
- \u13F 在某些正则表达式风格中，表示 Unicode 十六进制值 13F 对应的字符。
- \xF7 在某些正则表达式风格中，表示 ASCII 十六进制值 F7 对应的字符。
- \x{13F} 在某些正则表达式风格中，表示 Unicode 十六进制值 13F 对应的字符。
元字符（Metacharacters）
- ^ 表示行的开头。
- $ 表示行的结尾。
- . 匹配任意单个字符（通常不包括换行符）。
- [ 表示字符类的开始。
- ] 表示字符类的结束。
- ( 在某些风格中，表示分组的开始。
- ) 在某些风格中，表示分组的结束。
- ( 在某些风格中，表示分组的开始（转义版）。
- ) 在某些风格中，表示分组的结束（转义版）。
- { 在某些风格中，表示匹配次数限定符的开始。
- } 在某些风格中，表示匹配次数限定符的结束。
- { 在某些风格中，表示匹配次数限定符的开始（转义版）。
- } 在某些风格中，表示匹配次数限定符的结束（转义版）。
- | 在某些风格中，表示或运算（alternation）。
- | 在某些风格中，表示或运算（alternation）（转义版）。
- \1 在某些风格中，表示对第 1 组的反向引用。
- \2 在某些风格中，表示对第 2 组的反向引用。
量词（Quantifiers）
- * 匹配零次或多次前面的元素。
- + 在某些风格中，匹配一次或多次前面的元素。
- + 在某些风格中，匹配一次或多次前面的元素（转义版）。
- ? 在某些风格中，匹配零次或一次前面的元素。
- ? 在某些风格中，匹配零次或一次前面的元素（转义版）。
- *? 在某些风格中，表示
*的**非贪婪（lazy）**版本。 - +? 在某些风格中，表示
+的**非贪婪（lazy）**版本。 - }? 在某些风格中，表示
}的**非贪婪（lazy）**版本。
术语（Terminology）
- BRE（Basic Regular Expressions）：基本正则表达式。
- ERE（Extended Regular Expressions）：扩展正则表达式。
- GNU：一个旨在创建自由操作系统的项目，为
grep、sed等工具提供正则表达式扩展。 - Greedy（贪婪匹配）：表示运算符匹配尽可能多的字符。
- Metacharacter（元字符）：具有特殊含义的字符或字符序列，如
.或\+。 - PCRE（Perl-Compatible Regular Expressions）：Perl 兼容正则表达式。
- Regex：正则表达式的缩写。
- Regular Expression（正则表达式）：包含特殊字符的字符串模式，用于匹配文本中的模式。
相关软件和工具（Supporting Software）
- Grep：用于查找匹配正则表达式的文本行的命令行工具。
- Sed：非交互式流编辑器，以
s命令（substitution 替换）著称。 - AWK：支持正则表达式的文本处理工具，使用 ERE 语法。
- Emacs：可编程文本编辑器，支持正则表达式。
- Vim：可编程文本编辑器，支持正则表达式。
- Java：从 1.4 版开始，标准库内置正则表达式支持。
- JavaScript：支持正则表达式的 Web 脚本语言。
- Perl：以强大的正则表达式支持而著称的解释型脚本语言。
- PHP：支持正则表达式的解释型脚本语言。
这份术语表涵盖了正则表达式的主要符号、量词、术语及相关软件，便于查阅和理解不同正则表达式风格及其适用范围。