Z3 TypeScript API 正则表达式（Regular Expression）支持完全指南

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 基于 WebAssemblycheck()返回 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 as 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 as match InRe(aa, aPlus); // true注意与*的唯一区别是至少要求一次重复因此空串不满足。对应源码Z3_mk_re_plushigh-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_optionhigh-level.ts。测试用例分别验证了空串与a均为sathigh-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_unionhigh-level.ts。测试对a、b断言sat对c断言unsathigh-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 dont InRe(1, azRange); // false InRe(Z, azRange); // falseRange(lo, hi)接受两个单字符串或序列对应Z3_mk_re_rangehigh-level.ts。测试验证m为sat、1为unsathigh-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 (hi0 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_loophigh-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 dont InRe(aa, a3); // false InRe(aaaa, a3); // falsePower(re, n)等价于精确重复n次实现为Z3_mk_re_powerhigh-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_complementhigh-level.ts。3.10 Diff集合差a \ bconst { 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_diffhigh-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_concathigh-level.ts。测试验证helloworld为sat、hello为unsathigh-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参数函数含义底层 APIAllChar(reSort)匹配任意单个字符Z3_mk_re_allcharEmpty(reSort)空语言不匹配任何串Z3_mk_re_emptyFull(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 \ bRange(lo, hi)— 字符区间Loop(re, lo, hi?)— 有界重复{lo,hi}hi0或省略表示至少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、ReCreationsrc/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），仅供参考