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

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

本节摘要:前四节讲了理论与核心算法,这一节动手实现正则的基础语法:字符类([a-z])、量词(* + ? {m,n})、锚点(^ $)、通配符(.)。我们要把这些「语法糖」映射到前几节建立的 NFA 基本构造上——比如 [a-z] 就是「26 个单字符的选择」,a+ 等价于 aa*。理解这种「语法糖 ↔ 基本构造」的映射,你就能支持丰富的正则语法,而引擎内核仍是 Thompson 构造。

内容来源:基于正则语法与引擎实现整理的导读。

学习目标

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

1. 把字符类 [a-z]、[abc]、[^abc] 映射为选择构造(扩展到字符集转移)。
2. 把量词 +(一个或多个)、?(零或一)、{m,n} 映射为闭包构造的变体。
3. 实现锚点 ^(行首)、$(行尾)为「零宽断言」——不消耗字符,只检查位置。
4. 实现通配符 . 为「任意字符」的转移。
5. 理解这些语法都是「糖」,内核仍是第 03 节的四种基本 NFA 构造。

一、学习价值:语法糖与内核的分离

正则有几十种语法元素,看上去复杂。但本节的核心洞察是:绝大多数语法都是「糖」,内核仍是 Thompson 构造的四种基本模板(字符/连接/选择/闭包)。把语法糖翻译成基本构造,引擎内核不用改,只需扩展解析器。

这种「语法层丰富、内核层简洁」的设计,是优秀引擎的标志——也是第 9 章编译器「AST 优化」的预演(很多语法糖在 AST 层就被化简成基本构造了)。

二、子系统拆解:语法糖 → 基本构造

字符类 [...]

[abc]   等价于  a|b|c                (选择)
[a-z]   等价于  a|b|c|...|z          (选择, 扩展为范围)
[^abc]  等价于  "非 a 且非 b 且非 c"  (补集, 需特殊转移)
​

实现:把字符类展开成一个「字符集转移」——NFA 的转移不标单个字符,而标一个字符集(或补集)。

量词

a*      零个或多个   ← 闭包(基本构造)
a+      一个或多个   等价于  aa*     (连接 + 闭包)
a?      零个或一个   等价于  (a|ε)   (选择, 含空)
a{m}    恰好 m 个    等价于  aaa...a (m 次连接)
a{m,n}  m 到 n 个    等价于  aa...a a? a? ... (m 次连接 + (n-m) 个可选)
​

所有量词都能化简为「连接 + 闭包 + 选择」的组合。解析时把它们展开成这些基本构造即可。

通配符 .

. 匹配除换行外的任意字符。实现:标为「任意字符集」的转移(除 \n)。

锚点 ^ 与 $

^   行首   不消耗字符, 只在"位置是行首"时允许通过
$   行尾   不消耗字符, 只在"位置是行尾"时允许通过
​

锚点是「零宽断言」——不读字符,只检查位置。实现:特殊转移,匹配「位置」而非「字符」。这扩展了纯自动机模型(纯自动机只认字符),但实现简单:在匹配循环里特殊处理。

三、上手第一步:扩展解析器支持这些语法

1. 先让解析器识别这些新 token:[、]、{、}、^、$、. 等。
2. 在 AST 里为它们定义节点类型(字符集、量词、锚点)。
3. 在 Thompson 构造里为每种节点加处理分支(多数是「展开为基本构造」)。
4. 测试:[A-Z][a-z]+ 匹配单词、^error 匹配行首 error、.* 匹配任意行。

本节要点回顾

1. 语法糖 ↔ 基本构造:字符类=选择、量词=闭包变体、通配符=任意字符集,内核仍是 Thompson 四模板。
2. 字符类展开为字符集转移;量词(+ ? {m,n})化简为连接+闭包+选择。
3. 锚点(^ $)是零宽断言,不消耗字符只检查位置,需特殊转移。
4. 设计原则:语法层丰富、内核层简洁——解析时把糖展开成基本构造。

推荐上手顺序

1. 先支持字符类 [abc] [a-z](展开为选择)。
2. 加量词 + ? {m,n}(展开为连接+闭包)。
3. 加通配符 .(任意字符转移)。
4. 最后加锚点 ^ $(零宽,需匹配循环特殊处理)。
5. 测试:[A-Z]\w*、^From:、https?:// 等真实模式。

下一节讲分组、选择与捕获组——以及为什么捕获组让引擎倒退回回溯。