造轮子工程 · 第 4 章造正则引擎

文档摘要

造轮子工程 · 第 4 章造正则引擎章节摘要:正则表达式看起来像「玄学咒语」——一串看不出它是怎么工作的。但当你亲手造一个正则引擎,会发现它背后的原理出奇地优雅:把正则表达式翻译成一个「状态机」(有限自动机),然后用这个状态机去匹配文本。本章导读正则引擎的核心:从理论出发,讲清 NFA(非确定有限自动机)与 DFA(确定有限自动机)的差别、Thompson 构造法(把正则编译成 NFA)、子集构造法(NFA 转 DFA)、回溯式匹配(为什么很多引擎用回溯而非 DFA)、字符类与捕获组的实现。

造轮子工程 · 第 4 章造正则引擎

章节摘要:正则表达式看起来像「玄学咒语」——一串 ^[A-Z][a-z]+\d{2,3}$ 看不出它是怎么工作的。但当你亲手造一个正则引擎,会发现它背后的原理出奇地优雅:把正则表达式翻译成一个「状态机」(有限自动机),然后用这个状态机去匹配文本。本章导读正则引擎的核心:从理论出发,讲清 NFA(非确定有限自动机)与 DFA(确定有限自动机)的差别、Thompson 构造法(把正则编译成 NFA)、子集构造法(NFA 转 DFA)、回溯式匹配(为什么很多引擎用回溯而非 DFA)、字符类与捕获组的实现。造完之后,你会获得两层收益:一是彻底理解 grep/sed/awk 背后的机制(呼应《Linux 命令》第 3 章),二是理解「编译器前端」的核心思想——把一种语言(正则)翻译成另一种可执行的形式(状态机),这正是第 9 章(造编译器)的微缩预演。

学习目标

阅读完本章,你应当能够:

说清正则表达式与有限自动机(状态机)的对应关系:正则是描述,自动机是执行。
区分 NFA(非确定,一个状态可有多条出边)与 DFA(确定,一个状态一个输入一个去向),理解各自在「匹配速度」与「构建成本」上的取舍。
用 Thompson 构造法把一个正则表达式逐步编译成等价的 NFA。
实现两种匹配策略:DFA 式(快、不支持反向引用)与回溯式(慢、支持更丰富特性,多数引擎的选择)。
实现基础语法:字符类([a-z])、量词(* + ? {m,n})、锚点(^ $)、分组与选择((ab|cd))。
实现捕获组(记住 (...) 匹配到的文本),理解它为什么让引擎从 DFA 倒退回回溯式。
理解「正则不能匹配嵌套结构」(如配对的括号)的理论根源:有限自动机没有栈。

核心概念速览

正则引擎的本质是「编译 + 执行」:先把正则编译成状态机(这是「编译器前端」的微缩版),再用状态机跑文本。理解这条链路,既治好了正则玄学恐惧症,也为第 9 章的编译器打下了第一根桩。

子章节导航

01 理论起点:正则与有限自动机

正则表达式在数学上等价于「正则语言」,而正则语言等价于「有限自动机能识别的语言」。讲清这个理论对应——正则是「描述」,自动机是「执行」,两者等价。这一节是全章的认知地基。

02 NFA 与 DFA:两种自动机的取舍

NFA(非确定):一个状态对同一输入可有多条出边,需要「并行/猜测」;DFA(确定):一个状态一个输入一个去向,匹配快但状态可能爆炸。讲清两者在「构建成本」与「匹配速度」上的权衡,以及为什么没有「绝对更好」的一方。

03 Thompson 构造:把正则编译成 NFA

肯·汤普森(Ken Thompson)1968 年提出的经典算法:对正则的每个构造(连接、选择、闭包)给出对应的 NFA 片段,递归组合。这是把「正则」翻译成「可执行形式」的核心一步,也是全章最难也最美的部分。

04 匹配策略:DFA 式 vs 回溯式

两条匹配路线:DFA 式(把 NFA 转成 DFA,匹配快但不支持捕获组/反向引用)、回溯式(深搜尝试,支持丰富特性但最坏情况慢)。多数生产引擎(PCRE、Python re)选回溯式——支持反向引用是关键原因。

05 实现基础语法:字符类、量词、锚点

动手实现:[a-z](字符类)、* + ? {m,n}(量词)、^ $(锚点)、.(任意字符)。这一节从「会写正则」上升到「会让计算机理解正则」,呼应《Linux 命令》第 3 章 grep 的 -E 扩展正则。

06 分组、选择与捕获组

(ab|cd)(分组与选择)、(...)(捕获组,记住匹配文本以便回引)、\1(反向引用)。重点讲清捕获组为什么让引擎从 DFA 倒退回回溯——这是「正则从理论走向工程」的关键转折。

07 正则的边界:为什么不能匹配配对括号

正则不能匹配「配对的括号」「嵌套的 HTML 标签」这类结构,理论根因是「有限自动机没有栈」。讲清这个边界,以及为什么这类问题需要上下文无关文法(第 9 章编译器的领地)。

子章节之间的逻辑关系

本章遵循「理论 → 翻译 → 匹配 → 实现 → 边界」的递进路径,前两节是理论,中间三节是实现,最后是边界:


正则=自动机 (01) ── 认知地基
   │
   ▼
NFA vs DFA (02)  ── 两种自动机的取舍
   │
   ▼
Thompson 构造 (03) ── 把正则编译成 NFA(全章难点与美感)
   │
   ▼
DFA式 vs 回溯式 (04) ── 两条匹配路线
   │
   ▼
基础语法实现 (05) ── 字符类/量词/锚点
   │
   ▼
分组与捕获 (06)  ── 捕获组让引擎倒退回回溯
   │
   ▼
正则的边界 (07)  ── 为什么配对括号匹配不了
   │
   ▼
第 5 章:从"匹配文本"上升到"编辑文本"——造文本编辑器

这是一条「从理论到实现再到边界」的完整路线:01-02 是认知地基(不学这个,后续都是黑箱);03 是全章核心算法;04 是路线选择;05-06 是动手实现;07 则把视角拉到「正则的能力边界」,自然引出第 9 章的编译器——那里用「带栈的自动机(下推自动机)」突破了正则的限制。

前置知识与后续延伸

前置知识:

姊妹篇《Linux 命令实战》第 3 章(grep/sed/awk 与正则——你要先会用正则,再造引擎)
基本的数据结构(图、链表、栈、递归)

本章为后续章节奠定的基础:

「把一种语言编译成可执行形式(状态机)」是编译器前端的核心思想,第 9 章的深化
「NFA/DFA 状态机」的概念在词法分析(第 9 章)里再次出现
「有限自动机无栈,故不能匹配嵌套结构」的理论边界,自然引出第 9 章的「下推自动机/上下文无关文法」
造完正则引擎,你看待 grep/sed/awk 的眼光将彻底不同——它们不再是「玄学命令」,而是「一个状态机在跑」

造轮子工程 · 第 4 章 造正则引擎

文档摘要