Z3 TypeScript API 正则表达式（Regular Expression）支持完全指南
【免费下载链接】z3The Z3 Theorem Prover项目地址: https://gitcode.com/gh_mirrors/z3/z3
本文以 Z3 官方 TypeScript 绑定（npm 包z3-solver）新增的正则表达式支持为主题，系统讲解如何在符号求解场景下创建正则表达式、组合各类正则操作符（Star、Plus、Union、Range、Loop、Complement 等），并将正则约束与字符串长度等其他 Z3 约束混合求解。读完本文，你将掌握 Z3 TS API 中完整、可运行的正则表达式建模方法，并理解其"符号约束而非执行匹配"的底层原理。本文的示例出自仓库文档 src/api/js/examples/regex-example.md，底层实现与测试分别位于 src/api/js/src/high-level/high-level.ts 与 src/api/js/src/high-level/high-level.test.ts。
一、前提：环境与基本概念
Z3 的 TypeScript 绑定通过 Emscripten 将 Z3 编译为 WebAssembly，以z3-solver发布。构建与测试方法可参考 src/api/js/README.md。在代码中，所有 API 均从Context('main')解构获得：
const { Re, String: Str, InRe, Solver } = Context('main');几个关键约定：
Re是正则表达式的工厂命名空间：负责创建正则排序与基础正则（对应源码中ReCreation类型，见 src/api/js/src/high-level/types.ts）。InRe(seq, re)是归属判定：返回一个布尔约束，表达"序列/字符串seq匹配正则re"，底层调用 C API 的Z3_mk_seq_in_re（见 src/api/js/src/high-level/high-level.ts）。Solver用于求解：把InRe约束加入 solver 后调用check()，结果为'sat'（可满足）或'unsat'（不可满足）。由于 API 基于 WebAssembly，check()返回 Promise，需要await。
二、基础用法：创建正则与首次求解
2.1 由字符串创建正则
Re.toRe(seq)接受一个字符串或序列表达式，返回只匹配该字符串本身的单个正则：
const { Re, String: Str, InRe, Solver } = Context('main'); // Create a regex from a string const hello = Re.toRe('hello'); // Check if a string matches const solver = new Solver(); solver.add(InRe('hello', hello)); await solver.check(); // sat从实现看，toRe会把传入的字符串先转换为序列表达式（String.val(seq)），再调用底层Z3_mk_seq_to_re（见 src/api/js/src/high-level/high-level.ts），因此字符串与Seq两种入参都支持。
2.2 创建正则排序
若需要显式声明正则的类型（例如为AllChar、Empty、Full提供排序参数），使用Re.sort(seqSort)：
const { Re, String: Str, eqIdentity } = Context('main'); const reSort = Re.sort(Str.sort()); // 底层为 Z3_mk_re_sort，其 basis 就是字符串排序 eqIdentity(reSort.basis(), Str.sort()); // trueReSort类型通过basis()返回底层序列排序，源码见 src/api/js/src/high-level/types.ts。仓库测试 src/api/js/src/high-level/high-level.test.ts 验证了这一点。
三、核心正则操作符逐个击破
以下操作符均以顶层函数形式提供，对应 SMT-LIB2 正则理论中的标准构造。仓库中每个操作符都有独立测试（见 src/api/js/src/high-level/high-level.test.ts 的regular expressions测试套件）。
3.1 Star：零次或多次重复（*）
const { Re, InRe, Star } = Context('main'); const a = Re.toRe('a'); const aStar = Star(a); // Empty string matches a* InRe('', aStar); // true // Multiple 'a's match InRe('aaa', aStar); // true实现上Star(re)对应Z3_mk_re_star，对参数数量没有额外要求（见 high-level.ts）。
3.2 Plus：一次或多次重复（+）
const { Re, InRe, Plus } = Context('main'); const a = Re.toRe('a'); const aPlus = Plus(a); // Empty string does NOT match a+ InRe('', aPlus); // false // One or more 'a's match InRe('aa', aPlus); // true注意+与*的唯一区别是至少要求一次重复，因此空串不满足。对应源码Z3_mk_re_plus（high-level.ts）。
3.3 Option：零次或一次（?）
const { Re, InRe, Option } = Context('main'); const a = Re.toRe('a'); const aOpt = Option(a); // Both empty and 'a' match a? InRe('', aOpt); // true InRe('a', aOpt); // true InRe('aa', aOpt); // false对应Z3_mk_re_option（high-level.ts）。测试用例分别验证了空串与"a"均为sat（high-level.test.ts）。
3.4 Union：并（或，|）
const { Re, InRe, Union } = Context('main'); const a = Re.toRe('a'); const b = Re.toRe('b'); const aOrB = Union(a, b); // Either 'a' or 'b' match InRe('a', aOrB); // true InRe('b', aOrB); // true InRe('c', aOrB); // falseUnion是变参函数，接受一个或多个正则；单参数时直接返回该正则，多个参数时映射到Z3_mk_re_union（high-level.ts）。测试对'a'、'b'断言sat，对'c'断言unsat（high-level.test.ts）。
3.5 Intersect：交（与，&）
const { Re, InRe, Intersect, Star } = Context('main'); const a = Re.toRe('a'); const b = Re.toRe('b'); const both = Intersect(Star(a), Star(b)); // Only empty string matches both a* and b* InRe('', both); // true InRe('a', both); // false交集的语言是两个正则语言的重叠部分。Star(a) ∩ Star(b)中唯一同时属于两者的串是空串。实现为Z3_mk_re_intersect，同样是变参（high-level.ts）。
3.6 Range：字符区间
const { Range, InRe } = Context('main'); const azRange = Range('a', 'z'); // Lowercase letters match InRe('m', azRange); // true // Others don't InRe('1', azRange); // false InRe('Z', azRange); // falseRange(lo, hi)接受两个单字符串或序列，对应Z3_mk_re_range（high-level.ts）。测试验证'm'为sat、'1'为unsat（high-level.test.ts）。
3.7 Loop：有界重复（{lo,hi}）
const { Re, InRe, Loop } = Context('main'); const a = Re.toRe('a'); // Between 2 and 3 repetitions const a2to3 = Loop(a, 2, 3); InRe('aa', a2to3); // true InRe('aaa', a2to3); // true InRe('a', a2to3); // false InRe('aaaa', a2to3); // false // At least 2 repetitions (hi=0 or omitted means unbounded) const a2Plus = Loop(a, 2, 0); // or Loop(a, 2) InRe('aa', a2Plus); // true InRe('aaa', a2Plus); // true InRe('aaaa', a2Plus); // true InRe('a', a2Plus); // false关键约定：hi为0或省略时表示"至少lo次、上界不设限"。函数签名Loop(re, lo, hi = 0)与 JSDoc 注释在源码中有明确说明，底层调用Z3_mk_re_loop（high-level.ts）。测试对Loop(a, 2, 3)的四种输入逐一断言（high-level.test.ts）。
3.8 Power：精确重复（{n}）
const { Re, InRe, Power } = Context('main'); const a = Re.toRe('a'); const a3 = Power(a, 3); // Exactly 3 repetitions match InRe('aaa', a3); // true // Others don't InRe('aa', a3); // false InRe('aaaa', a3); // falsePower(re, n)等价于精确重复n次，实现为Z3_mk_re_power（high-level.ts），测试见 high-level.test.ts。
3.9 Complement：补（否定，~）
const { Re, InRe, Complement } = Context('main'); const a = Re.toRe('a'); const notA = Complement(a); // Everything except 'a' matches InRe('a', notA); // false InRe('b', notA); // true InRe('', notA); // true注意补运算作用在"语言"上：Complement(a)的语言是整个字母表上所有不是"a"的字符串（含空串），而非仅排除单个字符。实现为Z3_mk_re_complement（high-level.ts）。
3.10 Diff：集合差（a \ b）
const { Re, InRe, Diff, Star } = Context('main'); const a = Re.toRe('a'); const b = Re.toRe('b'); const diff = Diff(Star(a), b); // a* except 'b' InRe('aaa', diff); // true InRe('b', diff); // falseDiff(a, b)表示语言a减去语言b，实现为Z3_mk_re_diff（high-level.ts）。测试中a*减b后，'aaa'仍满足而'b'不满足（high-level.test.ts）。
3.11 ReConcat：连接
const { Re, InRe, ReConcat } = Context('main'); const hello = Re.toRe('hello'); const world = Re.toRe('world'); const helloworld = ReConcat(hello, world); // Concatenated strings match InRe('helloworld', helloworld); // true InRe('hello', helloworld); // falseReConcat为变参连接，单参数直接返回，多参数映射到Z3_mk_re_concat（high-level.ts）。测试验证'helloworld'为sat、'hello'为unsat（high-level.test.ts）。
四、方法链式调用：面向对象的正则写法
除了顶层函数，Re表达式对象自身也暴露同名方法（类型定义见 src/api/js/src/high-level/types.ts），支持链式组合：
const { Re, InRe } = Context('main'); const a = Re.toRe('a'); // Using methods const aStar = a.star(); const aPlus = a.plus(); const aOpt = a.option(); const notA = a.complement(); // Chaining const complex = a.plus().union(Re.toRe('b').star());可用的实例方法包括：
re.plus()、re.star()、re.option()、re.complement()re.union(other)、re.intersect(other)、re.diff(other)、re.concat(other)re.loop(lo, hi?)、re.power(n)
两种写法（顶层函数 vs 实例方法）构造的是同一类底层表达式。仓库测试同时覆盖了两种风格（high-level.test.ts），例如a.plus()生成的表达式在空串上必须返回unsat。
五、综合实战：约束求解生成匹配字符串
正则表达式的真正威力在于与求解器结合：不仅判断"某个固定字符串是否匹配"，还能让求解器找出满足约束的字符串。下面的例子约束变量x是长度恰好为 5、且只含'a'/'b'的字符串：
const { Re, String: Str, InRe, Union, Star, Solver } = Context('main'); const x = Str.const('x'); const a = Re.toRe('a'); const b = Re.toRe('b'); // Pattern: any combination of 'a' and 'b' const pattern = Star(Union(a, b)); const solver = new Solver(); solver.add(InRe(x, pattern)); solver.add(x.length().eq(5)); if (await solver.check() === 'sat') { const model = solver.model(); const result = model.eval(x); // Result will be a 5-character string containing only 'a' and 'b' console.log(result.asString()); // e.g., "aabba" }这里展示了正则约束与其他 Z3 约束（x.length().eq(5)）的叠加能力。仓库对应的测试 high-level.test.ts 在得到sat后，会进一步断言模型求值出的字符串长度为 5，并且匹配/^[ab]+$/。这意味着你完全可以用同样的手法构造"邮箱格式 + 长度限制""密码复杂度规则"等字符串模式约束，交由求解器搜索或验证。
六、特殊模式：AllChar / Empty / Full
除操作符外，还有三个直接构造语言的特殊正则（实现见 high-level.ts），它们都需要一个ReSort参数：
| 函数 | 含义 | 底层 API |
|---|---|---|
AllChar(reSort) | 匹配任意单个字符 | Z3_mk_re_allchar |
Empty(reSort) | 空语言（不匹配任何串） | Z3_mk_re_empty |
Full(reSort) | 匹配所有字符串 | Z3_mk_re_full |
例如：
const { Re, String: Str, AllChar, InRe } = Context('main'); const reSort = Re.sort(Str.sort()); const anyChar = AllChar(reSort); InRe('x', anyChar); // true（任意单字符都匹配）七、API 参考速查表
工厂方法
Re.sort(seqSort)— 创建正则排序（ReSort），底层Z3_mk_re_sortRe.toRe(seq)— 将序列/字符串转换为恰好匹配该串的正则，底层Z3_mk_seq_to_re
操作符（顶层函数）
Star(re)— 零次或多次重复（*）Plus(re)— 一次或多次重复（+）Option(re)— 零次或一次（?）Union(...res)— 并（|），变参Intersect(...res)— 交（&），变参ReConcat(...res)— 连接，变参Complement(re)— 补（~）Diff(a, b)— 集合差（a \ b）Range(lo, hi)— 字符区间Loop(re, lo, hi?)— 有界重复{lo,hi}；hi=0或省略表示至少lo次Power(re, n)— 精确重复{n}
特殊模式
AllChar(reSort)— 匹配任意单个字符Empty(reSort)— 空语言Full(reSort)— 匹配所有字符串
归属判定
InRe(seq, re)— 判定序列是否匹配正则，底层Z3_mk_seq_in_re
八、原理与注意事项
- 符号式而非执行式：所有正则操作都是"构造约束"——
InRe(seq, re)生成的是一个 SMT 布尔约束，Z3 求解器通过底层正则理论（词项重写、自动机相关推理等）判断可满足性，而不是像 JS 原生RegExp那样直接执行匹配。因此传统正则引擎的"性能基准"在此不适用。 - 与序列/字符串理论同源：正则排序建立在序列排序之上（
Re.sort接受SeqSort），所以正则约束天然可以和其他字符串/序列约束（length()、contains、concat等）混用，实现跨约束联合求解。 - 实现遵循 SMT-LIB2 正则理论：所有构造都能映射到 SMT-LIB2 的
str.in.re、re.++、re.*、re.+、re.opt、re.union、re.inter、re.range、re.loop、re.comp、re.diff、re.allchar、re.empty、re.full等标准算子，便于与 SMT-LIB2 生态互操作。 - 异步求解：TS 绑定运行在 WebAssembly 之上，
solver.check()返回 Promise，务必await。 - 入参宽容：
toRe、InRe、Range等函数都接受"字符串或Seq表达式"两种形式，字符串会在内部经String.val转为序列表达式，使用时按需选择即可。
九、延伸阅读
- 本文示例原文：src/api/js/examples/regex-example.md
- 正则表达式相关源码实现（
Re命名空间、全部操作符）：src/api/js/src/high-level/high-level.ts 与 src/api/js/src/high-level/high-level.ts - 正则类型定义（
Re、ReSort、ReCreation）：src/api/js/src/high-level/types.ts - 完整测试用例（每个操作符逐一验证）：src/api/js/src/high-level/high-level.test.ts
- 构建与测试说明：src/api/js/README.md
- 其余 TS API 增强功能概览：src/api/js/TYPESCRIPT_API_ENHANCEMENTS.md
- 底层 C API 声明（
Z3_mk_seq_to_re等）：src/api/z3_api.h
【免费下载链接】z3The Z3 Theorem Prover项目地址: https://gitcode.com/gh_mirrors/z3/z3
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
