正则表达式是一种用于描述字符串中字符组合模式的表达式，起源于形式语言理论中的正则集合概念。它通过定义字符字面量、元字符、量词及分组等语法规则，实现对文本的搜索、匹配、替换和提取操作。正则表达式广泛应用于编程语言、文本编辑器、数据库查询和网络爬虫等领域，是数据处理与模式识别的基础工具。

1 历史与起源

1.1 形式语言理论背景

形式语言理论是计算机科学的基础分支，研究符号串的集合及其文法描述。20世纪50年代，诺姆·乔姆斯基提出了乔姆斯基谱系，将语言分为四类，其中正则语言（3型语言）是最简单的一类，可由有限自动机识别。正则表达式正是描述正则语言的简洁符号系统。

1.2 Stephen Kleene与正则集合

1951年，美国数学家斯蒂芬·科尔·克莱尼（Stephen Cole Kleene）在研究神经网络的数学基础时，提出了“正则集合”（regular sets）的概念，并引入正则表达式作为描述正则集合的代数形式。克莱尼定义了闭包、并集和连接三种基本运算，奠定了正则表达式的理论基础。

1.3 早期在计算领域的应用

20世纪60年代，正则表达式被引入Unix系统。Ken Thompson在编辑器ed和qed中实现了正则表达式的搜索功能，随后成为了Unix工具grep（Global Regular Expression Print）的核心。1970年代，正则表达式逐步被集成到awk、sed等文本处理工具中，并在编程语言如Perl（1987年）中得到强化，推动了其广泛传播。

2 基本语法与概念

2.1 字符字面量与元字符

字符字面量指字符串中表示自身字符的符号，如字母a、数字1。元字符是具有特殊含义的符号，如.匹配任意单个字符（除换行符），^匹配行首，$匹配行尾，*表示前一个元素零次或多次重复，+表示一次或多次，?表示零次或一次，\用于转义元字符或引入特殊序列（如\d表示数字）。

2.2 字符类与预定义类

字符类用方括号[ ]定义一组待匹配字符，例如[abc]匹配a、b或c。可在其中使用连字符表示范围（如[0-9]），或用^表示取反（如[^0-9]匹配非数字）。预定义类是常见字符类的简写：\d（数字，等价于[0-9]）、\w（单词字符，含字母、数字和下划线）、\s（空白字符）、\D、\W、\S为对应取反。

2.3 量词

量词用于指定前一个元素重复的次数。

2.3.1 贪婪量词

默认情况下，量词*、+、?、{m,n}是贪婪的，即尽可能匹配更多的字符。例如\d+在字符串"123"中会匹配整个"123"而非仅"1"。

2.3.2 懒惰量词

在量词后添加?变为懒惰模式，如\d+?，尽可能匹配最少的字符。对"123"，\d+?会先匹配"1"，并在后续尝试重复时逐步增加。

2.3.3 占有量词

在量词后添加+变为占有模式，如\d++。占有量词忽略回溯，匹配之后不再放弃字符，通常用于提高性能并防止灾难性回溯。

2.4 分组与反向引用

圆括号( )用于将部分表达式分组，可捕获匹配内容供后续引用。反向引用通过\1、\2等引用之前捕获组的内容，例如(ab)\1匹配"abab"。非捕获分组使用(?: )避免保存捕获结果。

2.5 零宽断言

零宽断言匹配位置而非字符，消耗零宽度。

2.5.1 正向先行断言

(?=pattern)匹配其后紧跟pattern的位置。例如\d(?=px)匹配后面有"px"的数字。

2.5.2 正向后行断言

(?<=pattern)匹配其前紧邻pattern的位置。例如(?<=\$)\d+匹配美元符号后的数字。

2.5.3 负向先行断言

(?!pattern)匹配其后不跟随pattern的位置。

2.5.4 负向后行断言

(?<!pattern)匹配其前不紧邻pattern的位置。

3 引擎与实现

3.1 NFA与DFA引擎

正则表达式引擎分为两类：非确定有限自动机（NFA）和确定有限自动机（DFA）。NFA引擎基于回溯，支持捕获分组和反向引用，但可能性能不稳定。DFA引擎一次遍历确定所有匹配，速度快且性能可预测，但不支持捕获与反向引用。大多数编程语言（如Perl、Python、Java）使用NFA引擎。

3.2 回溯机制与性能陷阱

NFA引擎的匹配过程涉及尝试、失败和回溯。当模式存在多个分支或量词时，引擎可能尝试大量路径，导致指数级时间复杂度。典型陷阱包括`(aaa)*b`在长字符串上匹配失败时产生灾难性回溯。避免方法包括使用占有量词、原子分组或重写模式。

3.3 主流语言实现差异

3.3.1 Perl兼容正则表达式（PCRE）

PCRE是Perl语言的官方实现，也是广泛移植的库，支持丰富特性：递归正则、子程序调用、条件匹配、UTF-8等。其语法成为众多语言（如PHP、R、Delphi）的参考标准。

3.3.2 Python的re模块

Python的re模块基于PCRE的某些变体，提供基本匹配功能。默认使用贪婪量词，支持命名分组（(?P<name>...)），但缺少递归支持。Python 3.11引入了原子分组（(?>...)）以提高性能。

3.3.3 JavaScript的RegExp

JavaScript的RegExp对象遵循ECMAScript规范，支持正则表达式字面量（/pattern/flags）和构造函数。特性包括前瞻断言，但缺乏后行断言（ES2018引入）。量词默认贪婪，支持捕获组但未实现递归。

3.3.4 Java的java.util.regex

Java的java.util.regex库使用NFA引擎，支持完整的断言（包括后行断言）、独占量词和原子分组。提供Matcher类进行多次匹配，支持\p{InGreek}等Unicode属性。

4 实践应用

4.1 文本搜索与替换

正则表达式是文本编辑器和文本处理工具（如sed、awk）的核心功能。用户可通过简短的模式在文档中定位特定字符串，并使用捕获组进行动态替换。例如将(\d{4})-(\d{2})-(\d{2})替换为$2/$3/$1可转换日期格式。

4.2 数据验证（邮箱、电话号码、身份证等）

数据验证是正则表达式最常见的应用之一。例如邮箱格式验证：^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$。电话号码、身份证号、IP地址等都可以通过精心设计的模式进行格式校验，但需注意过度依赖正则可能无法覆盖所有合法变体。

4.3 日志分析与数据提取

系统日志常包含结构化或半结构化文本，正则表达式可快速提取关键字段。例如从Apache日志中提取IP、时间戳和请求路径：^(\S+) \S+ \S+ \[([^\]]+)\] "(\S+) (\S+) \S+"。结合脚本语言（如Python、Perl）可高效处理海量数据。

4.4 编译器中的词法分析

编译器的词法分析阶段使用正则表达式定义标记（token）的模式，如标识符、关键字、运算符。词法分析器生成器（如lex、flex）将正则表达式转换为有限自动机，从而高效扫描源代码字符串流。

5 高级主题

5.1 正则表达式与有限自动机的等价性

正则表达式与有限自动机在表达能力上等价。每个正则表达式都可以转换为一个非确定有限自动机（NFA），继而可转为确定有限自动机（DFA）。反之，每个有限自动机的语言都可以用正则表达式描述。这种等价性是正则表达式理论和实现的基石。

5.2 递归正则与扩展功能

部分正则引擎（如PCRE）支持递归匹配，通过(?R)或(?0)引用整个表达式，可用于处理嵌套结构（如括号匹配）。此外，平衡组（如.NET的(?<name1>...)和(?<-name1>...)）提供对堆栈的操控，实现复杂嵌套。这些能力超越了经典正则语言，属于上下文相关特性。

5.3 安全考虑：ReDoS（正则表达式拒绝服务）攻击

ReDoS攻击利用精心构造的输入触发正则表达式的极端回溯，消耗大量CPU资源，导致服务拒绝。典型脆弱模式包括(a+)+b、`(aaa)+b`等。防御措施包括：限制输入长度、使用超时机制、采用无回溯的引擎（如re2）、避免嵌套量词和交替。

6 常见误解与技巧

6.1 正则表达式能否解析HTML？

普遍建议避免用正则表达式解析HTML，因为HTML的语法上下文无关甚至更复杂。正则表达式无法可靠处理嵌套标签、非标准属性或复杂结构。应使用专用解析器（如HTML解析库）。然而，对于简单、受控的HTML片段（如无嵌套的标签提取），正则表达式仍可快速完成最小任务。

6.2 可读性与维护性建议

正则表达式常因短小精悍但晦涩难懂而被称为“只写语言”。提升可读性的方法包括：使用注释模式（/x标志或(?#comment)）、拆分条件为多个子表达式、命名捕获组、适当添加空格。同时，为复杂模式编写单元测试，并记录其预期行为。

6.3 调试与可视化工具

调试正则表达式可借助在线工具（如regex101、Regexr）实时显示匹配过程、分组捕获和错误信息。可视化工具（如Debuggex）可将表达式转换为铁路图，直观呈现分支与重复结构。许多IDE（如VS Code、JetBrains）也内置正则表达式测试面板，支持高亮匹配和替换预览。