一句话：提出无回溯的正则匹配工具 RE#，基于符号导数支持交、补与受限环视，匹配复杂度对输入线性。
该论文针对正则表达式匹配中回溯引擎在扩展算子下易出现指数级开销的问题，提出了工具与理论 RE#。RE# 建立在符号导数（symbolic derivatives）之上，不依赖回溯，除经典算子外还支持补、交以及受限环视（restricted lookarounds）。作者对匹配理论进行了形式化开发，证明主匹配算法具有关于输入长度的线性复杂度，并在实验中验证了这一理论复杂度。在流行正则基准上，RE# 比 Rust 中第二快的正则引擎在基线场景下快 71% 以上；在这些基准的扩展版本（启用交、补、环视等算子）上，RE# 相比所有当前最先进引擎往往有数个数量级的性能优势。
We present a tool and theory RE # for regular expression matching that is built on symbolic derivatives, does not use backtracking, and, in addition to the classical operators, also supports complement, intersection and restricted lookarounds. We develop the theory formally and show that the main matching algorithm has input-linear complexity both in theory as well as experimentally. We apply thorough evaluation on popular benchmarks that show that RE # is over 71% faster than the next fastest regex engine in Rust on the baseline, and outperforms all state-of-the-art engines on extensions of the benchmarks often by several orders of magnitude.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{VarataluVE25,
title = {RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted Lookarounds},
author = {Ian Erik Varatalu and Margus Veanes and Juhan Ernits},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {POPL},
year = {2025},
doi = {10.1145/3704837}
}