正则表达式

1. 学习目标

本章节对标 MIT 6.006 算法导论、Stanford CS143 编译原理、CMU 15-150 函数式程序设计等顶级高校课程对正则语言的教学水准，系统讲解 Python re 模块的工程化使用与底层理论。完成本章节学习后，读者应能够：

1.1 Bloom 认知层级目标

1.2 知识地图

[理论基础] 形式语言 → 正则文法 → NFA/DFA → 自动机理论
    ↓
[语法体系] 字符类 | 量词 | 锚点 | 分组 | 断言 | 反向引用
    ↓
[Python 实现] re 模块 | Match 对象 | Pattern 对象 | 编译标志
    ↓
[工程实战] 日志解析 | 数据清洗 | 表单验证 | 爬虫抽取
    ↓
[高级话题] 灾难性回溯 | 性能优化 | regex 第三方库 | Unicode 支持

1.3 前置知识检查

学习本章节前，请确认你已掌握：

1. Python 字符串基础操作（切片、转义、原始字符串 r""）；
2. 可迭代对象与迭代器协议；
3. 字符编码基础（Unicode、UTF-8、码点）；
4. 集合论基本概念（并集、补集）；
5. 自动机理论初步（DFA、NFA 的概念，可选）。

2. 历史动机与发展脉络

正则表达式起源于 1956 年数学家 Stephen Cole Kleene 在 Representation of Events in Nerve Nets and Finite Automata 一文中提出的”正则集合”（regular sets）代数。这一数学理论在 60 余年里演化为程序员每日使用的工具。

2.1 数学起源（1956-1968）

• 1956：Kleene 提出正则语言代数，定义了并（|）、连接（·）、Kleene 闭包（*）三种运算；
• 1959：Michael Rabin 与 Dana Scott 证明正则表达式等价于有限状态自动机（FSA），获 1976 年图灵奖；
• 1968：Ken Thompson 在 QED 文本编辑器中首次实现正则表达式匹配算法，论文 “Regular Expression Search Algorithm” 发表于 CACM。

2.2 Unix 时代（1970s-1980s）

• 1974：Thompson 在 Unix V6 实现 grep（Global Regular Expression Print）；
• 1975：awk 集成正则表达式；
• 1979：ed → ex → vi 编辑器全面支持正则；
• 1986：POSIX 标准化 BRE（Basic Regular Expression）与 ERE（Extended Regular Expression）；
• 1987：Perl 1.0 引入 PCRE（Perl Compatible Regular Expression），扩展大量语法。

2.3 Python re 模块演进

2.4 替代引擎

• PCRE（Perl Compatible Regular Expression）：C 库，被 PHP、nginx 等使用；
• RE2（Google）：基于 Thompson NFA，保证线性时间，不支持反向引用；
• Hyperscan（Intel）：基于 SIMD 加速，单核每秒匹配 10 GB 文本；
• Oniguruma：Ruby、PHP 默认引擎，功能丰富；
• Rust regex：基于 lazy DFA，性能与正确性兼顾；
• regex（Python 第三方库）：支持重叠匹配、可变长度反向引用。

3. 形式化定义

3.1 正则语言的代数定义

设 $\Sigma$ 为有限字母表，$\epsilon$ 为空字符串，$\emptyset$ 为空集，则正则表达式 $R$ 递归定义为：

其中：

• $a \in \Sigma$ 表示匹配单字符 $a$；
• $\epsilon$ 匹配空串；
• $\emptyset$ 不匹配任何串；
• $R_1 \cup R_2$（Python 写作 R1|R2）匹配 $R_1$ 或 $R_2$ 的并集；
• $R_1 \cdot R_2$（Python 写作 R1R2）匹配 $R_1$ 后接 $R_2$ 的连接；
• $R^*$（Python 写作 R*）匹配 $R$ 的 Kleene 闭包（零次或多次重复）。

派生运算：

3.2 自动机等价定理

Kleene 定理（1956）：语言 $L$ 是正则的当且仅当存在有限自动机 $M$ 接受 $L$。

形式化地：

其中：

• DFA（Deterministic Finite Automaton）：$M = (Q, \Sigma, \delta, q_0, F)$
• NFA（Nondeterministic Finite Automaton）：转移函数 $\delta : Q \times (\Sigma \cup \{\epsilon\}) \to 2^Q$

3.3 Python re 的执行模型

Python re 模块采用 回溯式 NFA（backtracking NFA）：

1. 将正则编译为抽象语法树（AST）；
2. AST 转换为 NFA 状态图；
3. 匹配时使用回溯搜索，尝试所有可能的路径直到匹配成功或所有路径失败。

设正则 $R$ 长度为 $m$，输入字符串 $s$ 长度为 $n$，则：

• 最坏时间复杂度 $O(2^{m+n})$（灾难性回溯）；
• 最优时间复杂度 $O(mn)$（无回溯的简单模式）；
• 空间复杂度 $O(m)$（AST + NFA 状态）。

RE2（Google）采用 Thompson NFA 算法，保证 $O(mn)$ 最坏复杂度，但放弃反向引用。

3.4 字符类的形式化

字符类 [...] 表示一个字符集，匹配其中任意一个字符：

• [abc] 等价于 $a \cup b \cup c$；
• [^abc] 等价于 $\Sigma \setminus \{a, b, c\}$；
• [a-z] 等价于 $\{x \in \Sigma \mid a \le x \le z\}$；
• \d 等价于 [0-9]，即 $\{0, 1, \ldots, 9\}$；
• \w 等价于 [A-Za-z0-9_]（默认）；
• \s 等价于 [ \t\n\r\f\v]。

3.5 量词的贪婪策略

Python 量词默认采用 最左最长匹配（leftmost-longest with backtracking）：

注意：Python re 不支持 *+、++，但第三方库 regex 支持。

4. 理论推导与原理解析

4.1 回溯机制详解

考虑正则 a*b 在输入 aaaab 上匹配：

1. 尝试 a* 匹配 aaaab（贪婪）
2. 尝试 b 匹配 "" 失败
3. 回溯：a* 匹配 aaa
4. 尝试 b 匹配 "b" 成功
5. 返回匹配 "aaaab"

形式化地，设 $f(i, j)$ 表示在状态 $i$、输入位置 $j$ 时是否匹配：

回溯即按 $\delta$ 中的顺序依次尝试，遇失败则回退。

4.2 灾难性回溯的成因

正则 (a+)+b 在输入 aaaaaaaaaaaaaaaaaaaaaaaaa（25 个 a，无 b）上：

• 每个 a+ 可以匹配 1 到 25 个字符；
• (a+)+ 的嵌套量词导致 $2^{25}$ 种分割方式；
• 每种都失败，但回溯机制会逐一尝试。

时间复杂度退化为 $O(2^n)$。

防御方法：

1. 使用 possessive 量词 (a++)+b（需 regex 库）；
2. 改写为 a+b（去除冗余嵌套）；
3. 使用原子组 (?>(a+)+)b；
4. 设置匹配超时（Python re 不支持，需 regex 库）。

4.3 锚点的语义

4.4 反向引用的形式化

反向引用 \1 引用第一个捕获组的内容：

例如 (\w+)\s+\1 匹配重复的单词（如 “the the”）。

形式化地，反向引用使正则表达式的能力超出正则语言范畴，进入上下文相关文法（context-sensitive grammar）的领域。Python re 支持反向引用但不支持递归模式（需 regex 库的 (?R)）。

4.5 命名分组的语义

(?P<name>...) 为分组命名，等价于 (?:...) 但同时记录捕获：

import re

pattern = r"(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})"
match = re.match(pattern, "2026-07-21")
print(match.group("year"))   # "2026"
print(match.groupdict())     # {'year': '2026', 'month': '07', 'day': '21'}

命名分组通过 (?P=name) 反向引用：

import re

# 匹配重复单词
pattern = r"\b(?P<word>\w+)\s+(?P=word)\b"
text = "I saw the the cat cat"
print(re.findall(pattern, text))  # ['the', 'cat']

5. 代码示例

5.1 基础匹配方法

"""re 模块基础匹配方法示例。Python 3.12+。"""
from __future__ import annotations

import re

# re.search：搜索第一个匹配（返回 Match 对象或 None）
match = re.search(r"\d+", "abc123def")
if match:
    print(f"匹配: {match.group()}")     # 123
    print(f"位置: {match.start()}-{match.end()}")  # 3-6
    print(f"span: {match.span()}")     # (3, 6)

# re.match：从字符串开头匹配
match = re.match(r"Hello", "Hello World")
print(match.group() if match else "No match")  # Hello

match = re.match(r"World", "Hello World")
print(match)  # None（不在开头）

# re.fullmatch：完全匹配整个字符串
match = re.fullmatch(r"\d{3}", "123")
print(bool(match))  # True

match = re.fullmatch(r"\d{3}", "1234")
print(bool(match))  # False

# re.findall：找到所有匹配，返回列表
numbers = re.findall(r"\d+", "a1b22c333")
print(numbers)  # ['1', '22', '333']

# re.finditer：找到所有匹配，返回迭代器（节省内存）
for m in re.finditer(r"\d+", "a1b22c333"):
    print(f"Match: {m.group()} at {m.start()}")
# Match: 1 at 1
# Match: 22 at 3
# Match: 333 at 6

5.2 替换与分割

"""替换与分割示例。"""
from __future__ import annotations

import re

# re.sub：替换
result = re.sub(r"\d+", "NUM", "a1b22c333")
print(result)  # aNUMbNUMcNUM

# 使用回调函数替换（高级用法）
def double_match(m: re.Match[str]) -> str:
    """将匹配的数字翻倍。"""
    return str(int(m.group()) * 2)

result = re.sub(r"\d+", double_match, "a1b22c333")
print(result)  # a2b44c666

# 限制替换次数
result = re.sub(r"\d+", "NUM", "a1b22c333", count=2)
print(result)  # aNUMbNUMc333

# 使用反向引用替换
result = re.sub(r"(\w+)@(\w+)", r"\2.\1", "user@example")
print(result)  # example.user

# re.split：分割
parts = re.split(r"[,;|]", "one,two;three|four")
print(parts)  # ['one', 'two', 'three', 'four']

# 保留分隔符（使用捕获组）
parts = re.split(r"([,;|])", "one,two;three|four")
print(parts)  # ['one', ',', 'two', ';', 'three', '|', 'four']

# 限制分割次数
parts = re.split(r"\s+", "a b c d e", maxsplit=2)
print(parts)  # ['a', 'b', 'c d e']

5.3 字符类与量词

"""字符类与量词示例。"""
from __future__ import annotations

import re

# 字符类
print(re.findall(r"[aeiou]", "Hello World"))      # ['e', 'o', 'o']
print(re.findall(r"[^aeiou\s]", "Hello World"))   # ['H', 'l', 'l', 'W', 'r', 'l', 'd']

# 预定义字符类
# \d  数字    \D  非数字
# \w  单词字符 \W  非单词字符
# \s  空白    \S  非空白
# \b  单词边界

# 量词
print(re.findall(r"a{2,4}", "a aa aaa aaaa aaaaa"))
# ['aa', 'aaa', 'aaaa', 'aaaa']

# 贪婪 vs 非贪婪
html = '<div>content1</div><div>content2</div>'
greedy = re.findall(r"<div>.*</div>", html)
print(greedy)  # ['<div>content1</div><div>content2</div>']（贪婪）

non_greedy = re.findall(r"<div>.*?</div>", html)
print(non_greedy)  # ['<div>content1</div>', '<div>content2</div>']（非贪婪）

# Unicode 字符类（需要 re.UNICODE，Python 3 默认开启）
chinese = re.findall(r"[\u4e00-\u9fa5]+", "Hello世界，Python编程123")
print(chinese)  # ['世界', '编程']

5.4 分组与捕获

"""分组与捕获示例。"""
from __future__ import annotations

import re

# 基本分组
match = re.search(r"(\d{4})-(\d{2})-(\d{2})", "Date: 2026-07-21")
if match:
    print(match.group())    # 2026-07-21（完整匹配）
    print(match.group(0))   # 2026-07-21（同上）
    print(match.group(1))   # 2026
    print(match.group(2))   # 07
    print(match.group(3))   # 21
    print(match.groups())   # ('2026', '07', '21')

# 命名分组
match = re.search(r"(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})", "2026-07-21")
if match:
    print(match.group("year"))   # 2026
    print(match.group("month"))  # 07
    print(match.groupdict())     # {'year': '2026', 'month': '07', 'day': '21'}

# 非捕获分组（性能优化）
result = re.findall(r"(?:https?://)?(\w+\.\w+)", "Visit example.com or https://google.com")
print(result)  # ['example.com', 'google.com']

# 前瞻断言
# (?=...)  正向前瞻：后面匹配
# (?!...)  负向前瞻：后面不匹配
prices = re.findall(r"\d+(?=元)", "苹果5元，香蕉3元，橙子4斤")
print(prices)  # ['5', '3']

# 后顾断言（Python 支持）
names = re.findall(r"(?<=用户：)\w+", "用户：Alice，用户：Bob")
print(names)  # ['Alice', 'Bob']

# 反向引用：匹配重复单词
text = "I saw the the cat and and dog"
duplicates = re.findall(r"\b(\w+)\s+\1\b", text)
print(duplicates)  # ['the', 'and']

5.5 编译标志详解

"""编译标志示例。"""
from __future__ import annotations

import re

# re.IGNORECASE (re.I)：忽略大小写
print(re.findall(r"hello", "Hello HELLO hello", re.I))
# ['Hello', 'HELLO', 'hello']

# re.MULTILINE (re.M)：多行模式（^和$匹配行首行尾）
text = "Line 1\nLine 2\nLine 3"
print(re.findall(r"^Line", text, re.M))  # ['Line', 'Line', 'Line']

# re.DOTALL (re.S)：. 匹配换行符
text = "Start\nMiddle\nEnd"
print(re.findall(r"Start.*End", text, re.S))  # ['Start\nMiddle\nEnd']

# re.VERBOSE (re.X)：允许注释和空白
pattern = re.compile(
    r"""
    ^                   # 字符串开头
    (?P<protocol>\w+)   # 协议名
    ://                 # 分隔符
    (?P<host>[\w.]+)    # 主机名
    (?::(?P<port>\d+))? # 可选端口
    (?P<path>/.*)?      # 可选路径
    $                   # 字符串结尾
    """,
    re.VERBOSE,
)

match = pattern.match("https://example.com:8080/path")
if match:
    print(match.groupdict())
    # {'protocol': 'https', 'host': 'example.com', 'port': '8080', 'path': '/path'}

# re.ASCII (re.A)：仅匹配 ASCII（关闭 Unicode 字符类）
print(re.findall(r"\w+", "hello 世界", re.A))   # ['hello']
print(re.findall(r"\w+", "hello 世界"))          # ['hello', '世界']

# re.DEBUG：输出编译后的 NFA 信息（调试用）
# re.compile(r"\d{3}-\d{4}", re.DEBUG)

# 组合标志
pattern = re.compile(r"^hello", re.I | re.M)

5.6 预编译正则与性能优化

"""预编译正则表达式示例。"""
from __future__ import annotations

import re
import timeit

# 预编译正则表达式（提升重复使用的性能）
EMAIL_PATTERN = re.compile(
    r"^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$"
)

# 使用编译后的对象
emails = ["user@example.com", "invalid-email", "test@test.org"]
valid_emails = [e for e in emails if EMAIL_PATTERN.match(e)]
print(valid_emails)  # ['user@example.com', 'test@test.org']

# 编译时指定标志
PHONE_PATTERN = re.compile(r"^1[3-9]\d{9}$")
print(bool(PHONE_PATTERN.match("13800138000")))  # True

# 性能对比
text = "user@example.com"
uncompiled_time = timeit.timeit(
    lambda: re.match(r"^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$", text),
    number=100_000,
)
compiled_time = timeit.timeit(
    lambda: EMAIL_PATTERN.match(text),
    number=100_000,
)
print(f"未编译: {uncompiled_time:.3f}s")
print(f"已编译: {compiled_time:.3f}s")
print(f"加速比: {uncompiled_time / compiled_time:.1f}x")

5.7 数据提取与清洗

"""数据提取与清洗示例。"""
from __future__ import annotations

import re


def extract_urls(text: str) -> list[str]:
    """从文本中提取所有 URL。"""
    pattern = re.compile(r"https?://[^\s<>\"']+")
    return pattern.findall(text)


def strip_html_tags(html: str) -> str:
    """去除 HTML 标签，保留文本内容。"""
    # 使用非贪婪匹配
    cleaned = re.sub(r"<[^>]+>", "", html)
    # 压缩多余空白
    return re.sub(r"\s+", " ", cleaned).strip()


def extract_chinese(text: str) -> list[str]:
    """提取所有中文字符片段。"""
    return re.findall(r"[\u4e00-\u9fa5]+", text)


def format_thousands(n: int | str) -> str:
    """千分位格式化数字。"""
    return re.sub(r"(?<=\d)(?=(\d{3})+$)", ",", str(n))


def camel_to_snake(name: str) -> str:
    """驼峰命名转下划线命名。"""
    s1 = re.sub(r"(.)([A-Z][a-z]+)", r"\1_\2", name)
    return re.sub(r"([a-z0-9])([A-Z])", r"\1_\2", s1).lower()


def check_password_strength(password: str) -> tuple[int, dict[str, bool]]:
    """检查密码强度。

    :param password: 待检查的密码
    :return: (分数 0-5, 各项检查结果)
    """
    checks = {
        "length": len(password) >= 8,
        "lower": bool(re.search(r"[a-z]", password)),
        "upper": bool(re.search(r"[A-Z]", password)),
        "digit": bool(re.search(r"\d", password)),
        "special": bool(re.search(r"[!@#$%^&*(),.?\":{}|<>]", password)),
    }
    score = sum(checks.values())
    return score, checks


# 使用示例
text = "Visit https://example.com and http://test.org for info."
print(extract_urls(text))
# ['https://example.com', 'http://test.org']

html = '<p>Hello <b>World</b></p>'
print(strip_html_tags(html))  # Hello World

text = "Hello世界，Python编程123"
print(extract_chinese(text))  # ['世界', '编程']

print(format_thousands(1234567890))  # 1,234,567,890

print(camel_to_snake("myVariableName"))  # my_variable_name
print(camel_to_snake("HTTPResponseCode"))  # http_response_code

score, details = check_password_strength("MyP@ss123")
print(f"强度分数: {score}/5, 详情: {details}")

5.8 日志解析实战

"""Apache/Nginx 日志解析示例。"""
from __future__ import annotations

import re
from collections import defaultdict
from datetime import datetime
from pathlib import Path
from typing import NamedTuple


class LogEntry(NamedTuple):
    """日志条目结构。"""
    ip: str
    timestamp: datetime
    method: str
    path: str
    protocol: str
    status: int
    size: int


# Apache combined log format
APACHE_LOG_PATTERN = re.compile(
    r"""
    ^
    (?P<ip>\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3})  # IP 地址
    \s+-\s+-\s+
    \[(?P<datetime>[^\]]+)\]                     # 时间戳
    \s+
    "(?P<method>\w+)\s+
    (?P<path>\S+)\s+
    (?P<protocol>HTTP/[\d.]+)"                   # 请求行
    \s+
    (?P<status>\d{3})                            # 状态码
    \s+
    (?P<size>\d+|-)                              # 响应大小
    """,
    re.VERBOSE,
)


def parse_apache_log_line(line: str) -> LogEntry | None:
    """解析一行 Apache 日志。

    :param line: 日志行
    :return: 解析后的 LogEntry，解析失败返回 None
    """
    match = APACHE_LOG_PATTERN.match(line)
    if not match:
        return None

    dt = datetime.strptime(match.group("datetime"), "%d/%b/%Y:%H:%M:%S %z")
    size_str = match.group("size")
    size = 0 if size_str == "-" else int(size_str)

    return LogEntry(
        ip=match.group("ip"),
        timestamp=dt,
        method=match.group("method"),
        path=match.group("path"),
        protocol=match.group("protocol"),
        status=int(match.group("status")),
        size=size,
    )


def analyze_log_file(filepath: str | Path) -> dict[str, int]:
    """分析日志文件，统计各状态码出现次数。

    :param filepath: 日志文件路径
    :return: 状态码 -> 出现次数
    """
    status_counts: dict[str, int] = defaultdict(int)
    ip_counts: dict[str, int] = defaultdict(int)

    with open(filepath, encoding="utf-8", errors="replace") as f:
        for line in f:
            entry = parse_apache_log_line(line)
            if entry:
                status_counts[str(entry.status)] += 1
                ip_counts[entry.ip] += 1

    return dict(status_counts)


# 示例日志行
sample_log = (
    '192.168.1.1 - - [21/Jul/2026:14:30:00 +0800] '
    '"GET /api/users HTTP/1.1" 200 1234'
)
entry = parse_apache_log_line(sample_log)
if entry:
    print(entry)
    # LogEntry(ip='192.168.1.1', timestamp=datetime.datetime(2026, 7, 21, 14, 30, ...),
    #          method='GET', path='/api/users', protocol='HTTP/1.1', status=200, size=1234)

5.9 表单验证

"""表单字段验证示例。"""
from __future__ import annotations

import re
from dataclasses import dataclass


@dataclass
class ValidationResult:
    """验证结果。"""
    is_valid: bool
    message: str


# 邮箱验证（RFC 5322 简化版）
EMAIL_PATTERN = re.compile(
    r"^[a-zA-Z0-9.!#$%&'*+/=?^_`{|}~-]+@[a-zA-Z0-9]"
    r"(?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?"
    r"(?:\.[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)+$"
)

# 中国手机号验证
PHONE_PATTERN = re.compile(r"^1[3-9]\d{9}$")

# 中国身份证号验证（18 位）
ID_CARD_PATTERN = re.compile(
    r"^[1-9]\d{5}"
    r"(?:19|20)\d{2}"
    r"(?:0[1-9]|1[0-2])"
    r"(?:0[1-9]|[12]\d|3[01])"
    r"\d{3}"
    r"[\dXx]$"
)

# URL 验证
URL_PATTERN = re.compile(
    r"^https?://"
    r"(?:\w+:\w+@)?"  # 可选认证
    r"(?:[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?\.)+"
    r"[a-zA-Z]{2,}"
    r"(?::\d+)?"  # 可选端口
    r"(?:/[^\s]*)?$"  # 可选路径
)

# IPv4 验证
IPV4_PATTERN = re.compile(
    r"^(?:25[0-5]|2[0-4]\d|1\d\d|[1-9]\d|\d)"
    r"(?:\.(?:25[0-5]|2[0-4]\d|1\d\d|[1-9]\d|\d)){3}$"
)


def validate_email(email: str) -> ValidationResult:
    """验证邮箱格式。"""
    if not email:
        return ValidationResult(False, "邮箱不能为空")
    if len(email) > 254:
        return ValidationResult(False, "邮箱过长")
    if EMAIL_PATTERN.match(email):
        return ValidationResult(True, "邮箱格式正确")
    return ValidationResult(False, "邮箱格式不正确")


def validate_phone(phone: str) -> ValidationResult:
    """验证中国手机号格式。"""
    if not phone:
        return ValidationResult(False, "手机号不能为空")
    if PHONE_PATTERN.match(phone):
        return ValidationResult(True, "手机号格式正确")
    return ValidationResult(False, "手机号格式不正确")


def validate_id_card(id_card: str) -> ValidationResult:
    """验证中国身份证号格式。"""
    if not ID_CARD_PATTERN.match(id_card):
        return ValidationResult(False, "身份证号格式不正确")

    # 校验位验证
    weights = [7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2]
    check_codes = "10X98765432"
    total = sum(int(d) * w for d, w in zip(id_card[:17], weights))
    expected = check_codes[total % 11]
    if id_card[-1].upper() != expected:
        return ValidationResult(False, "身份证校验位错误")

    return ValidationResult(True, "身份证号格式正确")


# 使用示例
print(validate_email("user@example.com"))     # is_valid=True
print(validate_email("invalid-email"))        # is_valid=False
print(validate_phone("13800138000"))          # is_valid=True
print(validate_phone("1234567890"))           # is_valid=False

5.10 高级用法：原子组与递归

"""高级正则用法（部分需 regex 第三方库）。"""
from __future__ import annotations

import re

try:
    import regex  # 第三方库，支持更多特性
    HAS_REGEX = True
except ImportError:
    HAS_REGEX = False


# 1. 原子组（atomic group）：避免回溯
# Python re 不支持原子组，使用 regex 库
if HAS_REGEX:
    # 防止灾难性回溯
    pattern = regex.compile(r"(?>a+)b")
    # 一旦 a+ 匹配完成，不会回退重试

# 2. 重叠匹配
# re.findall 不支持重叠，使用 lookahead 技巧
text = "abcabcabc"
# 普通匹配：不重叠
print(re.findall(r"abc", text))  # ['abc', 'abc', 'abc']

# 匹配所有位置（包括重叠）
overlapping = re.findall(r"(?=(abc))", text)
print(overlapping)  # ['abc', 'abc', 'abc']

# 3. 平衡组（仅 regex 库支持）
if HAS_REGEX:
    # 匹配配对的括号
    balanced = regex.compile(r"\((?:[^()]|(?R))*\)")
    text = "(a(b(c)d)e)"
    print(balanced.findall(text))

# 4. 递归模式（仅 regex 库支持）
if HAS_REGEX:
    # 匹配嵌套结构
    nested = regex.compile(r"\{(?:[^{}]|\{(?:[^{}]|\{[^{}]*\})*\})*\}")
    json_like = "{a: {b: {c: 1}}}"
    print(nested.findall(json_like))

# 5. 可变长度反向引用（仅 regex 库支持）
if HAS_REGEX:
    pattern = regex.compile(r"(\w+)\1")  # 反向引用可变长度
    print(pattern.findall("hellohello world world"))

6. 对比分析

6.1 re 与 regex 库对比

6.2 与其他语言正则对比

6.3 Python re 与字符串方法对比

6.4 re 与专用解析器对比

7. 常见陷阱与最佳实践

7.1 陷阱清单

陷阱 1：忘记使用原始字符串

import re

# 反例：未使用 r 前缀，需要双重转义
print(re.findall("\\\\d+", "a1b2"))  # 匹配 \d 字面量，匹配失败

# 正确：使用 r 前缀
print(re.findall(r"\d+", "a1b2"))  # ['1', '2']

陷阱 2：贪婪匹配导致意外

import re

# 反例：贪婪匹配跨过多个标签
html = '<a>link1</a><a>link2</a>'
result = re.findall(r"<a>(.*)</a>", html)
print(result)  # ['link1</a><a>link2']（错误）

# 修复：使用非贪婪
result = re.findall(r"<a>(.*?)</a>", html)
print(result)  # ['link1', 'link2']（正确）

陷阱 3：忘记 re.escape 处理用户输入

import re

# 反例：用户输入包含正则元字符
user_input = "1+1"
# re.findall(user_input, "1+1=2")  # 报错或行为异常

# 修复：转义
safe_pattern = re.escape(user_input)
print(re.findall(safe_pattern, "1+1=2"))  # ['1+1']

陷阱 4：灾难性回溯

import re

# 反例：嵌套量词导致灾难性回溯
# bad_pattern = re.compile(r"(a+)+b")
# bad_pattern.match("a" * 30)  # 可能挂起

# 修复：简化模式
good_pattern = re.compile(r"a+b")
good_pattern.match("a" * 30)  # 立即失败

陷阱 5：混淆 ^ 与 \A

import re

text = "line1\nline2"

# 反例：使用 ^ 但期望仅匹配字符串开头
print(re.findall(r"^\w+", text))         # ['line1']（仅第一行）
print(re.findall(r"^\w+", text, re.M))   # ['line1', 'line2']

# 修复：明确使用 \A 或 \Z
print(re.findall(r"\A\w+", text))  # ['line1']（始终字符串开头）

陷阱 6：分组捕获导致 findall 返回元组

import re

# 反例：findall 返回分组而不是完整匹配
text = "2026-07-21"
result = re.findall(r"(\d{4})-(\d{2})-(\d{2})", text)
print(result)  # [('2026', '07', '21')]

# 修复：使用非捕获分组
result = re.findall(r"(?:\d{4})-(?:\d{2})-(?:\d{2})", text)
print(result)  # ['2026-07-21']

陷阱 7：re.sub 替换字符串中的反斜杠

import re

# 反例：替换字符串中 \1 被解释为反向引用
result = re.sub(r"a", r"\1b", "aaa")
# 报错：组 1 不存在

# 修复：使用函数避免转义问题
result = re.sub(r"a", lambda m: r"\1b", "aaa")
print(result)  # \1b\1b\1b

7.2 最佳实践

1. 始终使用原始字符串：r"pattern" 避免双重转义问题。

2. 预编译常用正则：在模块级定义 PATTERN = re.compile(...)。

3. 使用命名分组：(?P<name>...) 提高可读性。

4. 复杂正则用 VERBOSE：添加注释和换行。

5. 明确选择贪婪/非贪婪：根据需求选择 * 或 *?。

6. 使用 re.escape 处理动态输入：避免注入风险。

7. 避免嵌套量词：(a+)+ 容易导致灾难性回溯。

8. 优先考虑专用解析器：HTML 用 BeautifulSoup，JSON 用 json 模块。

9. 添加超时保护：处理不可信输入时使用 signal.alarm 或 regex 库的 timeout 参数。

10. 测试覆盖边界情况：空字符串、空匹配、回溯路径。

"""生产级正则工具集。"""
from __future__ import annotations

import re
from dataclasses import dataclass


@dataclass
class RegexPattern:
    """封装预编译的正则表达式，提供类型安全的接口。"""
    pattern: re.Pattern[str]
    name: str

    @classmethod
    def compile(cls, pattern: str, name: str = "", flags: int = 0) -> RegexPattern:
        """编译正则表达式。"""
        return cls(pattern=re.compile(pattern, flags), name=name)

    def find_all(self, text: str) -> list[str]:
        """查找所有匹配。"""
        return self.pattern.findall(text)

    def find_all_groups(self, text: str) -> list[tuple[str, ...]]:
        """查找所有匹配的分组。"""
        return [m.groups() for m in self.pattern.finditer(text)]

    def match(self, text: str) -> re.Match[str] | None:
        """从头匹配。"""
        return self.pattern.match(text)

    def search(self, text: str) -> re.Match[str] | None:
        """搜索第一个匹配。"""
        return self.pattern.search(text)

    def sub(self, replacement: str, text: str) -> str:
        """替换。"""
        return self.pattern.sub(replacement, text)


# 预定义的常用模式
EMAIL_REGEX = RegexPattern.compile(
    r"^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$",
    name="email",
)
URL_REGEX = RegexPattern.compile(
    r"https?://[^\s<>\"']+",
    name="url",
)
PHONE_REGEX = RegexPattern.compile(
    r"^1[3-9]\d{9}$",
    name="phone",
)
IPV4_REGEX = RegexPattern.compile(
    r"^(?:25[0-5]|2[0-4]\d|1\d\d|[1-9]\d|\d)"
    r"(?:\.(?:25[0-5]|2[0-4]\d|1\d\d|[1-9]\d|\d)){3}$",
    name="ipv4",
)

8. 工程实践

8.1 性能优化技巧

"""正则性能优化技巧。"""
from __future__ import annotations

import re
import timeit


# 1. 预编译正则
PATTERN_COMPILED = re.compile(r"\d+")

def with_compile(text: str) -> list[str]:
    return PATTERN_COMPILED.findall(text)

def without_compile(text: str) -> list[str]:
    return re.findall(r"\d+", text)


# 2. 使用非捕获分组提升性能
def use_non_capturing(text: str) -> list[str]:
    # 使用 (?:...) 避免捕获开销
    return re.findall(r"(?:\d{4})-(?:\d{2})-(?:\d{2})", text)

def use_capturing(text: str) -> list[str]:
    return re.findall(r"(\d{4})-(\d{2})-(\d{2})", text)


# 3. 锚定提升性能
def with_anchors(text: str) -> bool:
    # 使用 ^ 和 $ 提前失败
    return bool(re.match(r"^\d+$", text))

def without_anchors(text: str) -> bool:
    return bool(re.search(r"\d", text))


# 4. 字符类优于选择
def with_charclass(text: str) -> list[str]:
    # 使用 [abc] 比 (a|b|c) 快
    return re.findall(r"[abc]", text)

def with_alternation(text: str) -> list[str]:
    return re.findall(r"(a|b|c)", text)


# 5. 避免灾难性回溯
def safe_pattern(text: str) -> bool:
    # 简化嵌套量词
    return bool(re.match(r"a+b", text))

def unsafe_pattern(text: str) -> bool:
    # 危险的嵌套量词
    return bool(re.match(r"(a+)+b", text))


# 性能基准
text = "2026-07-21 abc 123 def"
print("with_compile:", timeit.timeit(lambda: with_compile(text), number=100_000))
print("without_compile:", timeit.timeit(lambda: without_compile(text), number=100_000))

8.2 调试正则表达式

"""调试正则表达式。"""
from __future__ import annotations

import re


def debug_pattern(pattern: str, text: str) -> None:
    """调试正则表达式。

    :param pattern: 正则模式
    :param text: 待匹配文本
    """
    print(f"模式: {pattern}")
    print(f"文本: {text}")

    # 编译时输出 NFA 信息
    compiled = re.compile(pattern, re.DEBUG)
    print()

    # 显示所有匹配
    matches = list(compiled.finditer(text))
    print(f"匹配数: {len(matches)}")
    for i, m in enumerate(matches, 1):
        print(f"  [{i}] {m.group()!r} at {m.span()}")
        if m.groupdict():
            print(f"      groups: {m.groupdict()}")

    # 显示高亮
    highlighted = compiled.sub(
        lambda m: f"\033[31m{m.group()}\033[0m", text
    )
    print(f"高亮: {highlighted}")


if __name__ == "__main__":
    debug_pattern(r"\d{4}-\d{2}-\d{2}", "Date: 2026-07-21")

8.3 单元测试

"""正则表达式的单元测试示例。"""
from __future__ import annotations

import re
import unittest


class TestEmailRegex(unittest.TestCase):
    """邮箱正则的单元测试。"""

    PATTERN = re.compile(
        r"^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$"
    )

    def test_valid_emails(self) -> None:
        """测试合法邮箱。"""
        valid_emails = [
            "user@example.com",
            "test.user@example.co.uk",
            "user+tag@example.org",
            "user-name@example.io",
        ]
        for email in valid_emails:
            with self.subTest(email=email):
                self.assertIsNotNone(self.PATTERN.match(email))

    def test_invalid_emails(self) -> None:
        """测试非法邮箱。"""
        invalid_emails = [
            "",
            "plainaddress",
            "@example.com",
            "user@",
            "user@example",
            "user@example..com",
            "user name@example.com",
        ]
        for email in invalid_emails:
            with self.subTest(email=email):
                self.assertIsNone(self.PATTERN.match(email))


class TestPhoneRegex(unittest.TestCase):
    """手机号正则的单元测试。"""

    PATTERN = re.compile(r"^1[3-9]\d{9}$")

    def test_valid_phones(self) -> None:
        """测试合法手机号。"""
        valid_phones = [
            "13800138000",
            "15012345678",
            "18600000000",
            "19912345678",
        ]
        for phone in valid_phones:
            with self.subTest(phone=phone):
                self.assertIsNotNone(self.PATTERN.match(phone))

    def test_invalid_phones(self) -> None:
        """测试非法手机号。"""
        invalid_phones = [
            "",
            "1234567890",      # 不以 1 开头
            "1380013800",      # 少一位
            "138001380000",    # 多一位
            "abc12345678",     # 含字母
        ]
        for phone in invalid_phones:
            with self.subTest(phone=phone):
                self.assertIsNone(self.PATTERN.match(phone))


if __name__ == "__main__":
    unittest.main()

8.4 集成到生产代码

"""生产环境中的正则使用模式。"""
from __future__ import annotations

import logging
import re
from dataclasses import dataclass
from typing import Final

logger = logging.getLogger(__name__)

# 模块级常量：所有正则表达式预编译
EMAIL_PATTERN: Final = re.compile(
    r"^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$"
)
URL_PATTERN: Final = re.compile(r"https?://[^\s<>\"']+")
PHONE_PATTERN: Final = re.compile(r"^1[3-9]\d{9}$")
SLUG_PATTERN: Final = re.compile(r"^[a-z0-9-]+$")


@dataclass(frozen=True)
class ValidationError(Exception):
    """验证错误。"""
    field: str
    message: str


def validate_user_input(email: str, phone: str, website: str) -> None:
    """验证用户输入。

    :param email: 邮箱
    :param phone: 手机号
    :param website: 网站 URL
    :raises ValidationError: 验证失败
    """
    if not EMAIL_PATTERN.match(email):
        raise ValidationError("email", "邮箱格式不正确")

    if not PHONE_PATTERN.match(phone):
        raise ValidationError("phone", "手机号格式不正确")

    if website and not URL_PATTERN.match(website):
        raise ValidationError("website", "URL 格式不正确")

    logger.info("用户输入验证通过")


# 使用示例
try:
    validate_user_input("user@example.com", "13800138000", "https://example.com")
except ValidationError as e:
    logger.error(f"验证失败: {e.field} - {e.message}")

9. 案例研究

9.1 案例一：Django URL 路由

Django 的 URL 路由系统大量使用正则表达式：

"""Django URL 路由示例（简化版）。"""
from __future__ import annotations

import re
from typing import Callable
from dataclasses import dataclass


@dataclass
class Route:
    """路由定义。"""
    pattern: re.Pattern[str]
    handler: Callable[..., str]


class Router:
    """简单的 URL 路由器。"""

    def __init__(self) -> None:
        self.routes: list[Route] = []

    def add(self, pattern: str, handler: Callable[..., str]) -> None:
        """添加路由。

        :param pattern: URL 模式（正则）
        :param handler: 处理函数
        """
        compiled = re.compile(f"^{pattern}$")
        self.routes.append(Route(compiled, handler))

    def dispatch(self, path: str) -> str:
        """分派请求。

        :param path: URL 路径
        :return: 处理结果
        :raises ValueError: 无匹配路由
        """
        for route in self.routes:
            match = route.pattern.match(path)
            if match:
                return route.handler(**match.groupdict())
        raise ValueError(f"No route for {path}")


# 使用
router = Router()

@router.add(r"/users/(?P<user_id>\d+)")
def get_user(user_id: str) -> str:
    return f"User {user_id}"

@router.add(r"/posts/(?P<year>\d{4})/(?P<month>\d{2})")
def get_posts_by_month(year: str, month: str) -> str:
    return f"Posts in {year}/{month}"

print(router.dispatch("/users/123"))       # User 123
print(router.dispatch("/posts/2026/07"))   # Posts in 2026/07

9.2 案例二：日志分析系统

Instagram 的日志分析系统使用大量正则解析日志：

"""生产级日志分析示例。"""
from __future__ import annotations

import re
from collections import Counter
from dataclasses import dataclass
from datetime import datetime
from pathlib import Path
from typing import Iterable


@dataclass
class AccessLog:
    """访问日志条目。"""
    ip: str
    timestamp: datetime
    method: str
    path: str
    status: int
    size: int
    duration_ms: float


# 复杂的日志模式
LOG_PATTERN = re.compile(
    r"""
    (?P<ip>\d+\.\d+\.\d+\.\d+)                    # IP
    \s+-\s+-\s+
    \[(?P<timestamp>[^\]]+)\]                       # 时间戳
    \s+
    "(?P<method>\w+)\s+(?P<path>\S+)\s+HTTP/[\d.]+" # 请求行
    \s+
    (?P<status>\d{3})                               # 状态码
    \s+
    (?P<size>\d+|-)                                 # 响应大小
    \s+
    "(?P<referer>[^"]*)"                            # Referer
    \s+
    "(?P<ua>[^"]*)"                                 # User-Agent
    \s+
    (?P<duration>[\d.]+)ms                          # 响应时间
    """,
    re.VERBOSE,
)


def parse_logs(filepath: str | Path) -> Iterable[AccessLog]:
    """解析日志文件。

    :param filepath: 日志文件路径
    :yield: 解析后的日志条目
    """
    with open(filepath, encoding="utf-8", errors="replace") as f:
        for line_no, line in enumerate(f, 1):
            match = LOG_PATTERN.match(line)
            if not match:
                continue
            try:
                yield AccessLog(
                    ip=match.group("ip"),
                    timestamp=datetime.strptime(
                        match.group("timestamp"),
                        "%d/%b/%Y:%H:%M:%S %z",
                    ),
                    method=match.group("method"),
                    path=match.group("path"),
                    status=int(match.group("status")),
                    size=int(match.group("size")),
                    duration_ms=float(match.group("duration")),
                )
            except (ValueError, TypeError) as e:
                # 跳过格式错误的行
                continue


def analyze_logs(logs: Iterable[AccessLog]) -> dict[str, object]:
    """分析日志，生成统计报告。"""
    status_counter: Counter[int] = Counter()
    ip_counter: Counter[str] = Counter()
    path_counter: Counter[str] = Counter()
    total_duration = 0.0
    count = 0

    for log in logs:
        status_counter[log.status] += 1
        ip_counter[log.ip] += 1
        path_counter[log.path] += 1
        total_duration += log.duration_ms
        count += 1

    return {
        "total_requests": count,
        "status_codes": dict(status_counter.most_common(10)),
        "top_ips": dict(ip_counter.most_common(10)),
        "top_paths": dict(path_counter.most_common(10)),
        "avg_duration_ms": total_duration / count if count else 0,
    }

9.3 案例三：BeautifulSoup 集成

爬虫项目通常组合使用正则与 BeautifulSoup：

"""正则与 BeautifulSoup 组合示例。"""
from __future__ import annotations

import re

try:
    from bs4 import BeautifulSoup
    HAS_BS4 = True
except ImportError:
    HAS_BS4 = False


def extract_emails_from_html(html: str) -> list[str]:
    """从 HTML 中提取所有邮箱。"""
    if not HAS_BS4:
        # 退化为纯正则
        return re.findall(r"[\w.+-]+@[\w.-]+\.\w+", html)

    soup = BeautifulSoup(html, "html.parser")
    text = soup.get_text()
    return re.findall(r"[\w.+-]+@[\w.-]+\.\w+", text)


def extract_links_by_pattern(html: str, pattern: str) -> list[str]:
    """提取匹配特定模式的链接。

    :param html: HTML 文本
    :param pattern: 链接路径的正则模式
    :return: 匹配的 URL 列表
    """
    if not HAS_BS4:
        return re.findall(r'href="([^"]+)"', html)

    soup = BeautifulSoup(html, "html.parser")
    regex = re.compile(pattern)
    return [
        a["href"]
        for a in soup.find_all("a", href=True)
        if regex.search(a["href"])
    ]


# 使用示例
html = """
<html>
<body>
    <a href="/users/123">User 123</a>
    <a href="/users/456">User 456</a>
    <a href="/posts/789">Post 789</a>
    <p>Contact: admin@example.com</p>
</body>
</html>
"""

print(extract_emails_from_html(html))
# ['admin@example.com']

print(extract_links_by_pattern(html, r"/users/\d+"))
# ['/users/123', '/users/456']

9.4 案例四：SQL 注入检测

"""SQL 注入检测示例。"""
from __future__ import annotations

import re


# SQL 注入常见模式
SQL_INJECTION_PATTERNS = [
    # 注释
    re.compile(r"--", re.IGNORECASE),
    re.compile(r"/\*.*?\*/", re.IGNORECASE | re.DOTALL),
    # UNION 注入
    re.compile(r"UNION\s+SELECT", re.IGNORECASE),
    # 时间盲注
    re.compile(r"SLEEP\s*\(", re.IGNORECASE),
    re.compile(r"BENCHMARK\s*\(", re.IGNORECASE),
    # 布尔盲注
    re.compile(r"OR\s+1\s*=\s*1", re.IGNORECASE),
    re.compile(r"AND\s+1\s*=\s*2", re.IGNORECASE),
    # 堆叠查询
    re.compile(r";\s*DROP\s+TABLE", re.IGNORECASE),
    re.compile(r";\s*DELETE\s+FROM", re.IGNORECASE),
    # 信息收集
    re.compile(r"INFORMATION_SCHEMA", re.IGNORECASE),
    re.compile(r"VERSION\s*\(\s*\)", re.IGNORECASE),
    # 编码绕过
    re.compile(r"0x[0-9a-fA-F]+"),
    re.compile(r"CHAR\s*\(", re.IGNORECASE),
]


def detect_sql_injection(input_str: str) -> list[str]:
    """检测输入是否包含 SQL 注入特征。

    :param input_str: 待检测的输入
    :return: 匹配到的模式列表
    """
    matches = []
    for pattern in SQL_INJECTION_PATTERNS:
        if pattern.search(input_str):
            matches.append(pattern.pattern)
    return matches


# 测试
test_inputs = [
    "1' OR '1'='1",
    "1; DROP TABLE users",
    "1 UNION SELECT username, password FROM users",
    "1' AND SLEEP(5)--",
    "normal text",
]

for inp in test_inputs:
    matches = detect_sql_injection(inp)
    print(f"输入: {inp!r}")
    print(f"  检测到: {len(matches)} 个模式")
    for m in matches:
        print(f"    - {m}")

9.5 案例五：YouTube 字幕解析

YouTube 字幕文件（.vtt）使用类似 XML 的格式，正则可以高效提取：

"""YouTube VTT 字幕解析示例。"""
from __future__ import annotations

import re
from dataclasses import dataclass


@dataclass
class Subtitle:
    """字幕条目。"""
    start: str  # 开始时间（HH:MM:SS.mmm）
    end: str    # 结束时间
    text: str


# VTT 时间戳模式
VTT_TIME_PATTERN = re.compile(
    r"(\d{2}:\d{2}:\d{2}\.\d{3})\s*-->\s*(\d{2}:\d{2}:\d{2}\.\d{3})"
)


def parse_vtt(content: str) -> list[Subtitle]:
    """解析 VTT 字幕文件。

    :param content: VTT 文件内容
    :return: 字幕列表
    """
    subtitles: list[Subtitle] = []
    lines = content.split("\n")
    i = 0

    while i < len(lines):
        line = lines[i].strip()
        match = VTT_TIME_PATTERN.search(line)
        if match:
            start, end = match.groups()
            # 收集字幕文本
            text_lines = []
            i += 1
            while i < len(lines) and lines[i].strip():
                text_lines.append(lines[i].strip())
                i += 1
            text = " ".join(text_lines)
            # 去除 HTML 标签
            text = re.sub(r"<[^>]+>", "", text)
            subtitles.append(Subtitle(start, end, text))
        else:
            i += 1

    return subtitles


# 示例
vtt_content = """WEBVTT

00:00:00.000 --> 00:00:02.500
Hello, welcome to the video.

00:00:02.500 --> 00:00:05.000
Today we will talk about
<c.colorE5E5E5>regular expressions</c>.

00:00:05.000 --> 00:00:08.000
Let's get started!
"""

subs = parse_vtt(vtt_content)
for sub in subs:
    print(f"[{sub.start} -> {sub.end}] {sub.text}")

10. 习题

10.1 选择题

题 1：正则表达式 a*b+ 匹配以下哪个字符串？

A. b
B. aaab
C. abbb
D. 以上都是

答案：D

解析：a* 匹配零个或多个 a，b+ 匹配一个或多个 b。所有选项都符合。

题 2：以下哪个正则可以匹配有效的 IPv4 地址？

A. \d+\.\d+\.\d+\.\d+
B. (?:25[0-5]|2[0-4]\d|1\d\d|[1-9]\d|\d)(?:\.\1){3}
C. \d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}
D. [0-9]{1,3}(\.[0-9]{1,3}){3}

答案：C（D 也可，但 C 更清晰）

解析：选项 C 匹配 1-3 位的数字四组，是简化版 IPv4 验证。严格版需要选项 B 的格式。

题 3：在 Python 中，re.findall(r"(\w+)(\d+)", "a1b22c333") 返回什么？

A. ['a1', 'b22', 'c333']
B. [('a', '1'), ('b', '22'), ('c', '333')]
C. ['a', 'b', 'c']
D. ['1', '22', '333']

答案：B

解析：当正则包含分组时，findall 返回元组列表，每个元组对应一个分组的捕获。

题 4：以下哪个标志让 . 匹配换行符？

A. re.IGNORECASE
B. re.MULTILINE
C. re.DOTALL
D. re.VERBOSE

答案：C

解析：re.DOTALL（别名 re.S）使 . 匹配包括换行符在内的任意字符。

题 5：正则 (?<=\$)\d+ 在文本 “$100 and$200” 中匹配什么？

A. ['100', '200']
B. ['$100', '$200']
C. ['$']
D. []

答案：A

解析：(?<=\$) 是后顾断言，匹配 $ 之后的位置但不消耗 $，所以只返回数字部分。

10.2 填空题

题 1：Python 正则模块的全名是 ______，正则表达式对应的自动机模型是 ______ 。

答案：re；NFA（Nondeterministic Finite Automaton，非确定性有限自动机）

题 2：要匹配任意一个空白字符，应使用预定义字符类 ______ ；要匹配单词边界，应使用 ______ 。

答案：\s；\b

题 3：使用 re.sub 时，反向引用第一个分组使用 ______ ；命名分组 (?P<year>\d{4}) 的反向引用使用 ______ 。

答案：\1 或 \g<1>；(?P=year) 或 \g<year>

题 4：正则 ^\d{4}-\d{2}-\d{2}$ 中，^ 表示 ______ ，$ 表示 ______ ，\d{4} 表示 ______ 。

答案：字符串开头；字符串结尾；连续 4 个数字

题 5：灾难性回溯通常由 ______ 引起，常见防御方法是 ______ 或 ______ 。

答案：嵌套量词（如 (a+)+）；改写为更简单的模式；使用原子组或 possessive 量词

10.3 编程题

题 1：编写一个函数，从文本中提取所有 URL。

参考答案：

"""URL 提取器。"""
from __future__ import annotations

import re
from urllib.parse import urlparse


URL_PATTERN = re.compile(
    r"""
    https?://                              # 协议
    (?:\w+:\w+@)?                          # 可选认证
    (?:[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?\.)+  # 域名
    [a-zA-Z]{2,}                           # 顶级域
    (?::\d+)?                              # 可选端口
    (?:/[^\s<>\"\'\)]*)?                   # 可选路径
    """,
    re.VERBOSE,
)


def extract_urls(text: str) -> list[str]:
    """从文本中提取所有 URL。

    :param text: 待处理的文本
    :return: URL 列表
    """
    return URL_PATTERN.findall(text)


# 测试
text = """
Visit https://example.com or http://test.org:8080/path for info.
Contact us at https://api.example.com/v1/users?key=abc123
"""
urls = extract_urls(text)
for url in urls:
    print(url)
    parsed = urlparse(url)
    print(f"  scheme: {parsed.scheme}")
    print(f"  host: {parsed.hostname}")
    print(f"  path: {parsed.path}")

题 2：编写一个函数，将驼峰命名转换为下划线命名。

参考答案：

"""命名转换工具。"""
from __future__ import annotations

import re


def camel_to_snake(name: str) -> str:
    """驼峰转下划线。

    >>> camel_to_snake("myVariableName")
    'my_variable_name'
    >>> camel_to_snake("HTTPResponseCode")
    'http_response_code'
    >>> camel_to_snake("getHTTPResponse")
    'get_http_response'
    """
    # 处理连续大写字母
    s1 = re.sub(r"(.)([A-Z][a-z]+)", r"\1_\2", name)
    # 处理小写或数字后的大写字母
    return re.sub(r"([a-z0-9])([A-Z])", r"\1_\2", s1).lower()


def snake_to_camel(name: str) -> str:
    """下划线转驼峰。

    >>> snake_to_camel("my_variable_name")
    'myVariableName'
    """
    parts = name.split("_")
    return parts[0] + "".join(p.title() for p in parts[1:])


def pascal_to_camel(name: str) -> str:
    """帕斯卡转驼峰。"""
    return name[0].lower() + name[1:] if name else name


# 测试
if __name__ == "__main__":
    import doctest
    doctest.testmod()

题 3：编写一个函数，验证密码强度（5 项检查：长度、小写、大写、数字、特殊字符）。

参考答案：

"""密码强度检查器。"""
from __future__ import annotations

import re
from dataclasses import dataclass


@dataclass
class PasswordStrength:
    """密码强度评估结果。"""
    score: int  # 0-5
    checks: dict[str, bool]
    level: str  # weak / medium / strong / very_strong


def check_password_strength(password: str) -> PasswordStrength:
    """检查密码强度。

    :param password: 待检查的密码
    :return: PasswordStrength 对象
    """
    checks = {
        "length": len(password) >= 8,
        "lower": bool(re.search(r"[a-z]", password)),
        "upper": bool(re.search(r"[A-Z]", password)),
        "digit": bool(re.search(r"\d", password)),
        "special": bool(re.search(r"[!@#$%^&*(),.?\":{}|<>]", password)),
    }
    score = sum(checks.values())

    if score <= 2:
        level = "weak"
    elif score == 3:
        level = "medium"
    elif score == 4:
        level = "strong"
    else:
        level = "very_strong"

    return PasswordStrength(score=score, checks=checks, level=level)


# 测试
test_passwords = [
    "123",                    # weak
    "abcdefgh",               # weak
    "Abc12345",               # medium
    "Abcdef123",              # strong
    "P@ssw0rd!",              # very_strong
]

for pwd in test_passwords:
    result = check_password_strength(pwd)
    print(f"密码: {pwd!r}")
    print(f"  强度: {result.level} ({result.score}/5)")
    print(f"  详情: {result.checks}")

10.4 思考题

题 1：为什么说 Python re 模块基于回溯 NFA 而非 DFA？这对性能有何影响？

参考答案要点：

1. 回溯 NFA 的优势：支持反向引用、零宽断言、可变长度分组，这些是 DFA 无法实现的；
2. 回溯 NFA 的劣势：最坏时间复杂度 $O(2^n)$，存在灾难性回溯风险；
3. DFA 的优势：线性时间 $O(mn)$，无回溯；
4. DFA 的劣势：不支持反向引用，状态空间可能爆炸；
5. 折中方案：RE2 在编译时分析模式，若不支持则回退；lazy DFA（Rust regex）按需构造状态；
6. 实践建议：可信输入用 re，不可信输入用 RE2 或设置超时。

题 2：何时应该使用正则表达式，何时应该改用专用解析器？

参考答案要点：

适合正则：

• 简单文本模式匹配
• 数据验证（邮箱、电话、URL）
• 日志解析（行级格式固定）
• 字符串替换

不适合正则：

• 嵌套结构（HTML、XML、JSON）
• 数学表达式（涉及优先级）
• 配置文件（TOML、YAML、INI）
• 语法分析（需要 AST）

判断标准：

• 是否涉及递归结构？是 → 解析器
• 是否需要错误恢复？是 → 解析器
• 是否需要 AST？是 → 解析器
• 是否只是模式匹配？是 → 正则

题 3：解释 \b 单词边界的精确语义，并说明在 Unicode 文本中的行为。

参考答案要点：

1. 定义：\b 匹配 \w 与 \W 之间的位置，或 \w 与字符串首尾之间的位置；
2. 示例：在 "hello world" 中，\b 匹配 4 个位置（每个单词前后）；
3. Python 3 默认行为：\w 等价于 [a-zA-Z0-9_] 加上 Unicode 字母数字；
4. re.ASCII 标志：将 \w 限制为 ASCII 范围；
5. 边界情况："_hello_" 中下划线视为单词字符，\b 仅在 _ 之外匹配；
6. 多字节字符：中文字符的边界由 Unicode 属性决定，需注意编码。

11. 参考文献

11.1 经典论文与书籍

• [1] S. C. Kleene, “Representation of events in nerve nets and finite automata,” in Automata Studies, C. E. Shannon and J. McCarthy, Eds. Princeton, NJ: Princeton University Press, 1956, pp. 3-42. doi: 10.1515/9781400882618-002
• [2] M. O. Rabin and D. Scott, “Finite automata and their decision problems,” IBM J. Res. Dev., vol. 3, no. 2, pp. 114-125, 1959. doi: 10.1147/rd.32.0114
• [3] K. Thompson, “Regular expression search algorithm,” Commun. ACM, vol. 11, no. 6, pp. 419-422, 1968. doi: 10.1145/363347.363387
• [4] J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed. Boston, MA: Pearson, 2006, ISBN 978-0321455369
• [5] M. Sipser, Introduction to the Theory of Computation, 3rd ed. Boston, MA: Cengage Learning, 2013, ISBN 978-1133187790
• [6] J. Friedl, Mastering Regular Expressions, 3rd ed. Sebastopol, CA: O’Reilly Media, 2006, ISBN 978-0596528126
• [7] D. E. Knuth, J. H. Morris, and V. R. Pratt, “Fast pattern matching in strings,” SIAM J. Comput., vol. 6, no. 2, pp. 323-350, 1977. doi: 10.1137/0206024

11.2 Python 文档

• [8] Python Software Foundation, “re — Regular expression operations,” Python 3.12 Documentation, 2024. [Online]. Available: https://docs.python.org/3/library/re.html
• [9] Python Software Foundation, “Regular Expression HOWTO,” 2024. [Online]. Available: https://docs.python.org/3/howto/regex.html
• [10] M. Kuchling, “re module source code,” CPython Repository. [Online]. Available: https://github.com/python/cpython/blob/main/Lib/re/
• [11] M. Barnett, “regex: Alternative regular expression module, to replace re,” 2024. [Online]. Available: https://pypi.org/project/regex/